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
blog comments powered by Disqus