sexta-feira, 16 de outubro de 2009

Oddwording de novo

Poliedro Em maio de 2007 publiquei um artigo sobre a implementação do algoritmo oddwording em diversas linguagens de programação.

Para relembrar, segue o código em Haskell:

module Main where

import IO


main = mainloop


mainloop :: IO ()
mainloop = do
ph <- readString
if ph == ""
then
return ()
else do
let nph = oddword ph
putStrLn nph
mainloop


readString :: IO String
readString = do
putStrLn "Digite uma frase: "
putStr "> "
hFlush stdout
s <- getLine
return s


oddword :: String -> String
oddword s = listToStr $ invodd $ strToList s


strToList :: String -> [String]
strToList "" = []
strToList s = (take spi s) : (strToList (drop (incr spi) s))
where spi = nextspace s


incr :: Int -> Int
incr = (+ 1)


nextspace :: String -> Int
nextspace "" = 0
nextspace (x:xs) =
if x == ' '
then
0
else
1 + (nextspace xs)


listToStr :: [String] -> String
listToStr [] = ""
listToStr (x:xs) = x ++ " " ++ (listToStr xs)


invodd :: Ord a => [[a]] -> [[a]]
invodd [] = []
invodd (x:xs) = x : (inveven xs)


inveven :: Ord a => [[a]] -> [[a]]
inveven [] = []
inveven (x:xs) = (inv x) : (invodd xs)


inv :: Ord a => [a] -> [a]
inv [] = []
inv (x:xs) = (inv xs) ++ [x]

<update ressaca>
Havia esquecido de forçar o flush de STOUT na função readString. Corrigido!
</update>

No entanto ficou faltando uma linguagem excepcionalmente importante, Lisp.

Lisp (LISt Processing) é uma família de linguagens funcionais concebida por John McCarthy em 1958, baseada no cálculo lambda. As principais linguagens da família Lisp são Common Lisp, Scheme e Emacs Lisp.

O código acima será reimplementado abaixo em Common Lisp.

Observação: os blocos de código deverão ser escritos em arquivo na ordem inversa em que aparecem aqui, ou seja, digite cada bloco no arquivo em linhas acima do bloco digitado anteriormente.

Ciclo principal


O ciclo principal será a função mainloop. Sua lógica de funcionamento é a seguinte:
  1. Pegar uma string digitada na entrada padrão;
  2. Se a string for vazia, sair do programa;
  3. Aplicar o algoritmo oddwording;
  4. Exibir na tela o resultado;
  5. Recomeçar o ciclo.


A função fica assim:
(defun mainloop ()
(loop do
(format t "~&~a~%"
(oddword (*exit-if-empty* (*read-string*))))))


Lendo uma linha da entrada padrão


Para ler uma linha da entrada padrão, devemos exibir um prompt, ler a entrada digitada pelo usuário e remover os espaços em branco do começo e do fim:
(defun *read-string* ()
(format t "~&Digite uma frase:~%> ")
(string-trim " " (read-line)))


Saindo caso a string esteja vazia


Caso nada tenha sido digitado, o programa encerra. Para isso é preciso avaliar a string, encerrando o processo se apropriado, caso contrário retornar a string:
(defun *exit-if-empty* ((a-string string))
(if (string= a-string "")
(exit)
a-string))


Descrição do algoritmo em alto nível


Podemos agora definir em alto nível o algoritmo oddwording:
  1. Transformar a string em uma lista de palavras;
  2. Inverter somente o conteúdo dos elementos de índice ímpar da lista;
  3. Transformar novamente a lista de palavras em uma string.

(defun oddword ((a-string string))
(list-to-str (invodd (str-to-list a-string))))


String para lista


Para transformar uma string em uma lista, basta quebrada em cada ocorrência de espaço (#\Space):
(defun str-to-list ((a-string string))
(loop
for i = 0 then (1+ j)
as j = (position #\Space a-string :start i)
collect (subseq a-string i j)
while j))


Lista para string


Para transformar uma lista de palavras em uma string única, é preciso concatenar todos os elementos da lista, sem esquecer de acrescentar espaços entre eles:
(defun list-to-str ((a-list list))
(string-trim " "
(apply #'concatenate 'string
(loop for e in a-list
collect (concatenate 'string e " ")))))


Inversão dos elementos ímpares


Só faltou inverter os elementos de índice ímpar da lista. Nada mais simples: pegar cada elemento, se o índice for ímpar, inverter:
(defun invodd ((a-list list))
(loop
for x in a-list
and i from 0
collect (if (oddp i)
(reverse x)
x)))


Fazendo funcionar


Para que tudo aconteça, no final do arquivo acrescente uma chamada à função principal:
(mainloop)


E execute o arquivo com o comando clisp (aconselho o uso dos parâmetros -K full e -q).


**

Lisp tem uma abordagem extremamente elegante e clara, aproveita o paradigma funcional perfeitamente e seus programas podem ser retroalimentados recursivamente para obter-se um comportamento de aprendizado, apreciado no desenvolvimento de IA.

[]'s
Cacilhas, La Batalema

<update 2009-10-20>
Adicionada tipagem aos argumentos das funções e removido código redundante.
</update>
blog comments powered by Disqus