Haskell/Visão geral

Haskell é uma linguagem de programação funcional de semântica não-estrita. Ela possui suporte a funções recursivas, novos tipos de dados, casamento de padrão e compreensão de listas. Combinando estas possibilidades, certas funções que seriam bastante difícies de serem escritas em linguagens procedurais tornam-se triviais em Haskell.

Para aqueles acostumados com outras linguagens de programação, os exemplos abaixo mostram um pouco de como Haskell funciona.

Exemplos

A definição clássica da função fatorial:

fac 0 = 1
fac n = n * fac (n - 1)

Uma outra definição usando a função nativa product:

fac n = product [1..n]

O compilador de Haskell é inteligente o bastante para compilar ambas as definoções num mesmo código resultante.

Uma implementação ingênua para calcular o n-ésimo número da sequência de Fibonnaci:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 2) + fib (n - 1)

Uma função que retorna a sequência de Fibonnaci de complexidade linear:

fibs = 0 : 1 : zipWith (+) fibs (tail fibs)

Essa última função define uma lista infinita, que é possível por que Haskell é uma linguagem "preguiçosa".

Agora podemos redefinir fib como sendo

fib n = fibs !! n

onde !! é o operador que retonra o n-ésimo elemento de uma lista. Vale notar que os índices das listas começam em zero.

O algorirtmo de ordenação "quicksort" pode ser escrito em Haskell como:

qsort []     = [] 
qsort (x:xs) = qsort [y | y<-xs, y < x ] ++ [x] ++
               qsort [y | y<-xs, y >= x]

Note que o "quicksort", na verdade, deveria ordenar o vetor original, mas as listas de Haskell são imutáveis e, portanto, elas devem ser copiadas.

"Merge sort" fica

mgsort less [] = []
mgsort less xs = head $ until (null.tail) pairs [[x] | x <- xs]
    where 
      pairs (x:y:xs)    = merge x y : pairs xs
      pairs xs          = xs
      merge (x:xs) (y:ys)
            | less y x  = y : merge (x:xs) ys 
            | True      = x : merge  xs (y:ys)
      merge  xs     ys  = xs ++ ys

onde: (.) é o operador para compor funções, (h . g) x = h (g x); a função nativa until cond fun aplica fun repetidamente até que a condição cond seja atendida; e where é uma palavra-chave que introduz definições de funções locais, onde também aparecem guardas e casamento de padrões (sendo que (x:xs) casa uma lista não-vazia, com x sendo a cabeça, e xs a cauda).

A sequência de números de Hamming fica sendo

hamm = 1 : map (2*) hamm `union` 
              (map (3*) hamm `union` map (5*) hamm)
-- a union of two ordered lists:
union (x:xs) (y:ys) = case (compare x y) of
          LT -> x : union  xs  (y:ys)
          EQ -> x : union  xs     ys 
          GT -> y : union (x:xs)  ys

que usa operadores parcialmente aplicados e a função nativa map operando sobre listas, sejam elas infinitas ou não. Aqui aparece também a possibilidade de cercar o nome de uma função por acentos graves para torná-la um operador infixo. Comentários também aparecem, e são demarcados por dois hífens.

E finalmente, a lista infinita de número primos obtida por tentativas de divisão:

primes = 2 : sieve [3..] primes   -- 2 : _Y ((3:) . sieve [5,7..])
             where
             sieve xs (p:ps) | (h,t) <- span (< p*p) xs =
                                h ++ sieve [n | n <- t, rem n p > 0] ps

Ou usando uma Peneira de Eratostenes ilimitada:

import Data.List.Ordered

primes = 2 : _Y ((3:) . minus [5,7..]   -- ps = [2..] \\ [[p*p, p*p+p..] | p <- ps]
                      . unionAll 
                      . map (\p -> [p*p, p*p+2*p..]))
  
_Y g = g (_Y g)       -- = g (g (g (g (g ... ))))

Ou usando arranjos (arrays):

import Data.Array
import Data.List (tails, inits)

ps = 2 : [n | (r:q:_, px) <- (zip . tails . (2:) . map (^2)) ps (inits ps),
              (n,True)    <- assocs (
                                accumArray (\_ _ -> False) True (r+1,q-1)
                     [(m,()) | p <- px, 
                               let s = div (r+p) p * p,  m <- [s,s+p..q-1]] )]