Introdução ao Haskell

A linguagem Haskell é uma linguagem do paradigma funcional. Este paradigma consiste em uma sintaxe para o lambda-cálculo. Neste paradigma, temos as seguintes propriedades: 

•  Os programas consistem em funções que manipulam dados e/ou funções gerando novos dados e/ou funções. A execução de um programa resume-se a avaliar uma expressão funcional.

• As funções são valores de primeira classe, ou seja, elas podem ser um parâmetro de uma função e/ou um retorno de uma função.

             Esquema de uma execução de um programa funcional

Os códigos escritos em uma linguagem funcional tende a ser mais fácil de entender, mais curto, reusável e com um menor gap semântico, ou seja, a distância entre o que o programador que fazer e o que ele realmente precisa fazer. Considere o seguinte exemplo quicksort:

Quicksort na linguagem C

Quicksort em Haskell 

Fácil de Entender e Curto

A definição recursiva do quicksort torna o código mais curto e elegante.  O casamento de padrões e a definição de lista por compreensão torna a operação com listas mais inteligível e natural.

• Se a lista é vazia (padrão []), então a lista ordenada será [].

• Se a lista não está vazia ( padrão (p:xs) onde p é a cabeça da lista e xs é cauda da lista),  então vamos ordenar a lista formada pelos números menores que p que estão na cauda [x | x <- xs, x < p ] e a lista formada pelos números maiores ou iguais a p que estão na cauda [x | x <- xs , x >= p ] e a lista ordenada será formada pela concatenação dessas listas.
  
  

      

Reusável

qsort :: Ord a => [a] -> [a]

A função qsort pode ser utilizada para qualquer lista formada por um tipo que pertença a classe de tipo Ord, ou seja, um tipo que admite uma ordenação dos seus membros.

A linguagem Haskell têm outras propriedades interessantes como a transparência referencial das funções , funções de alta ordem e a  avaliação preguiçosa.

Transparência Referencial das Funções

o   O único efeito de chamar uma função é o seu valor de retorno

o   Os únicos fatores que podem influenciar o valor de uma função são seus parâmetros.

A transparência referencial da funções facilita a prova da corretude de um programa, a identificação de computações independentes (paralelismo) e o compilador pode aplicar alguns tipos de otimizações memoization, common subexpression elimination, etc.

Funções de Alta Ordem

Uma função de alta ordem é  aquela cujos parâmetros e/ou resultado é uma função. Em geral,

este tipo de função permite um maior reuso.

Exemplos:

A função twice recebe uma função e um valor como parâmetro e retorna a função aplicada

duas vezes a partir do valor passado como parâmetro.

twice :: (a->a) -> a -> a

twice f x = f (f x)

dobro :: a -> a

dobro x = 2*x

Prelude> twice dobro 3

12

quadrado :: Int -> Int
quadrado x = x*x

Prelude> :t map
map :: (a -> b) -> [a] -> [b]

A função map recebe uma função a->b, uma lista [a] e devolve uma lista [b].

Main> map quadrado [1..5]
[1,4,9,16,25]

Avaliação Preguiçosa

Uma expressão só será avaliada quando o seu valor for necessário evitando também repetidas avaliações.

Benefícios:

o   Aumento da performance(computações não necessárias não são realizadas)

o   Capacidade de construir estruturas de dados infinitas.

o   Apenas aquelas partes da lista que são necessárias para a avaliação da expressão serão calculadas explicitamente.

Prelude> :t zipWith
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]

Função zipWith : Recebe uma função (a -> b -> c) com dois parâmetros a e b e retorna c, duas listas [a]  e [b] e devolve uma lista [c]. A função zipWith combina elementos de duas listas com uma operação dada.
 Prelude> zipWith (*) [2,3] [4,5]
[8,15]

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

Considere o seguinte exemplo da definição da sequência de Fibonacci utilizando a função zipWith:

Dois primeiros elementos da lista são 0 e 1. Os próximos elementos é definido como a soma dos elementos da lista com os elementos da cauda.

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

fib   = 0 : 1 : [ a+b | (a,b) <- zip fib (tail fib) ]

Cálculo do Fibonacci

0 : 1 : zipWith (+) (0 : 1 : ...) (1 : ...)

0 : 1 : (0 + 1) : zipWith (+) (1 :1 : ...) (1 : ...)

0 : 1 : 1 : (1 + 1) : zipWith (+) (1 : 2 : ...) (2 : ...)

0 : 1 : 1 : 2 : (1 + 2) : zipWith (+) (2 : 3 : ...) (3 : ...)

Prelude> :t take
take :: Int -> [a] -> [a]
Prelude> take 3 [1..]
[1,2,3]
Prelude> take 40 fibs
[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,1771
1,28657,46368,75025,121393,196418,317811,514229,832040,1346269,2178309,3524578,5
702887,9227465,14930352,24157817,39088169,63245986]

Também podemos definir estruturas de dados complexas sem precisar recorrer aos ponteiros e/ou referências.

Modelando Estrutura de Dados Complexos

Observe a definição de uma árvore binária de busca em Haskell e a funções de inserção, maior e a altura da árvore sem utilização de ponteiros e/ou referências.

data ArvoreBinBusca t = Nulo | No t (ArvoreBin t) (ArvoreBin t) deriving (Eq, Ord, Show)        

insereArv :: Ord t => ArvoreBinBusca t -> t -> ArvoreBinBusca t

insereArv Nulo x = No x Nulo Nulo

insereArv (No t esq dir) x

 | x <= t    = (No t (insereArv esq x) dir )

 | otherwise = (No t esq (insereArv dir x) )

maiorArv :: Ord t => ArvoreBinBusca t -> t

maiorArv Nulo = error "arvore nula"

maiorArv (No t esq dir) | dir == Nulo = t | otherwise = maiorArv dir

alturaArv ::  Ord t => ArvoreBinBusca t -> Int

alturaArv Nulo = 0

alturaArv (No t esq dir) = 1 + max (alturaArv esq) (alturaArv dir)