quarta-feira, 21 de outubro de 2009

Mais sobre programação funcional

Paradigma funcional

Aproveitando o ensejo do artigo anterior sobre programação funcional, gostaria de puxar mais este artigo sobre três algoritmos tradicionais: sequência de Fibonacci, fatorial e quick sort.


Fatorial


Fatorial é um dos algoritmos recursivos mais tradicionais da Matemática. É também um dos algoritmos mais simples:
0!=1 n!=n*(n-1)!


Sua implementação tanto em Haskell quanto em Common Lisp descreve exatamente esse algoritmo.

Em Haskell:
factorial :: Integer -> Integer
factorial 0 = 1
factorial n = n * (factorial (n - 1))


Em Common Lisp:
(defun factorial ((n integer))
(if (zerop n)
n
(* n (factorial (- n 1)))))


Já em Scheme a coisa pode complicar… se o interpretador (uso guile) tiver sido compilado com suporte a bignum, tudo bem, se não, é preciso fazer uma pequena mágica, multiplicando os resultados do maior para o menor:
(define (factorial n)
(define (loop k l)
(if (zero? k)
l
(loop (- k 1) (* k l))))
(loop n 1))


Sequência de Fibonacci


A Sequência de Fibonacci é uma progressão natural iniciando por 1, 1 e progredindo ao passo de que cada elemento é a soma dos dois anteriores:
a0=1 a1=1 an=a(n-2)+a(n-1)


É uma sequência recursiva em árvore binária, o pesadelo dos programadores. =D

Mas como já foi muito estudada, há diversas formas de implementá-la sem usar código recursivo, como algoritmo reiterativo, potência de matrizes e função fechada.

A seguinte implementação em Haskell utiliza recursão e lista infinita:
fib :: [Integer]
fib = 1 : 1 : zipWith (+) fib (tail fib)


Já em Common Lisp foi uma boa ideia usar reiteração, muito mais elegante do que seria possível em qualquer linguagem imperativa:
(defun fib (index)
(check-type index (integer 0 *))
(loop
for a = 1 then b
and b = 1 then (+ a b)
repeat index
finally (return a)))


Quick sort


O algoritmo de ordenação quick sort é a exceção das exceções: um algoritmo de ordenação recursivo em árvore binária, o que deveria ser o pior dos casos, no entanto é um dos métodos de ordenação mais rápidos e eficientes que conhecemos.

O princípio é o seguinte: toma-se um elemento qualquer da lista, tradicionalmente o primeiro, então separa-se a lista em duas, uma de elementos menores que o tomado e outra de elementos maiores. Aplica-se a mesma ordenação quick sort a cada uma das novas listas e concatena-as com o elemento tomado no meio.

Em Haskell isso pode ser descrito assim:
qsort :: Ord a => [a] -> [a]
qsort [] = []
qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
where
lesser = [e | e <- xs, e < x]
greater = [e | e <- xs, e >= x]


Em Common Lisp o princípio é o mesmo, mas com aquele monte de parêntesis característicos de Lisp:
(defun qsort ((a-list list))
(if (< (length a-list) 2)
a-list
(let ((x (pop a-list)))
(concatenate 'list
(qsort
(loop for e in a-list
if (< e x)
collect e))
(list x)
(qsort
(loop for e in a-list
if (>= e x)
collect e))))))



**

Espero que este artigo tenha sido interessante e cause curiosidade aos leitores sobre programação funcional.

[]'s
Cacilhas, La Batalema

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>

terça-feira, 6 de outubro de 2009

IDEs em ambiente GNU/Linux

Poliedro Semana passada escrevi um artigo sobre alguns ambientes de desenvolvimento integrado e editores de texto, alguns deles RAD. No entanto o artigo ficou muito longo, daí tive a ideia de quebrá-lo em três partes.

Publiquei em meu blog Reflexões de Monte Gasppa e Giulia C., mas agora, pensando bem, acho que cabe pelo menos uma referência aqui no Kodumaro.

As três partes do artigo são:
  1. Editores de texto
  2. IDEs focadas em projeto
  3. RAD


A quem se interessar, boa leitura!

[]'s
Cacilhas, La Batalema