Mais sobre programação 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:


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:


É 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