Haskell/Visão geral: diferenças entre revisões

 

A definição clássica da função [[w:Fatorial|fatorial]]:

fac 0 = 1

fac n = n * fac (n - 1)

 

Uma outra definição usando a função nativa <code>product</code>:

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 [[w:Sequência Fibonnaci|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 [[w:Estratégia de avaliação#Chamada por necessidade|"preguiçosa"]].

 

Agora podemos redefinir <code>fib</code> como sendo

fib n = fibs !! n

onde <code>!!</code> é 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]

| True = x : merge xs (y:ys)

merge xs ys = xs ++ ys

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

EQ -> x : union xs ys

GT -> y : union (x:xs) ys

que usa operadores parcialmente aplicados e a função nativa <code>map</code> 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 [[w:Peneira de Eratostenes|Peneira de Eratostenes]] ilimitada:

import Data.List.Ordered

 

_Y g = g (_Y g) -- = g (g (g (g (g ... ))))

Ou usando arranjos (''arrays''):

import Data.Array

import Data.List (tails, inits)

[(m,()) | p <- px,

let s = div (r+p) p * p, m <- [s,s+p..q-1]] )]