Introdução a Haskell
Published:
Listas
Conforme visto anteriormente, em Haskell uma lista é definida recursivamente como:
data [a] = [] | a : [a]
Ou seja, uma lista pode ser ou uma lista vazia ou um elemento do tipo a seguido de outra parte da lista.
Uma lista no Haskell pode conter quantos elementos você desejar (até mesmo uma quantidade infinita) contanto que todos sejam do mesmo tipo.
Listas em Haskell são implementadas como Listas Ligadas, esse tipo de lista é eficiente quando precisamos acessar rapidamente o primeiro elemento, inserir novos elementos e economia de memória de alocação, porém o acesso aleatório a um elemento é mais lento do que as tradicionais arrays de outras linguagens.
Vamos relembrar três das quatro formas de criar uma lista em Haskell e aprender a quarta forma:
Listas explícitas
A forma explícita é talvez a mais intuitiva para um iniciante em programação em que você escreve diretamente os valores contidos na lista separados por vírgula e entre colchetes:
lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
Sequências
Também é possível criar uma lista implicitamente indicando uma sequência entre colchetes no formato [primeiro..ultimo], sendo primeiro o primeiro valor da sequência e ultimo o último valor. Alternativamente podemos informar o segundo elemento para que a linguagem infira a razão da sequência, finalmente, o último número pode ser omitido gerando assim uma lista infinita:
lista1 = [1..10] -- [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
lista2 = [0,2..10] -- [0, 2, 4, 6, 8, 10]
lista3 = [0,2..] -- [0, 2, 4, 6, 8, 10,..]
Compreensão de listas
Utilizando a notação matemática para conjuntos:
\[\{ 2 \cdot x | x \in [1..10] \}\]utilizando compreensão de listas temos:
lista = [ 2*x | x <- [1..10] ]
Da mesma forma:
\[\{ 2 \cdot x | x > 0 \}\]pode ser escrita em Haskell como:
lista = [ 2*x | x <- [0..] ]
Uma expressão do tipo:
\[\{ x | x \in [1..100], x mod 5 = 0 \}\]pode ser escrita como:
lista = [x | x <- [1..100], x `mod` 5 == 0]
Em resumo temos que a compreensão de listas possui o seguinte formato:
[ f x | x <- lista, condição1, condição2, ... ]
onde f é uma expressão matemática de x, lista é uma lista de onde x irá receber seus valores e condiçãoX são as condições de x que devem ser verdadeiras para que x seja avaliada pela expressão.
Exercício 01: Crie uma lista dos elementos x de 1 a 100 apenas quando x for divisível por 3 e por 5.
Funções geradoras
Uma outra forma de gerar uma lista é através de uma função geradora. Considere a seguinte função:
lista1 = 1 : prox lista
where
prox (x:resto) = (x+1) : prox resto
A lista é definida pelo elemento 1 e, o restante, definido pela função prox que recebe a lista atual como parâmetro.
Na definição da função o parâmetro de entrada (x:resto) significa que a função recebe uma lista como parâmetro de tal forma que o primeiro elemento da lista está armazenado em x e o restante da lista em resto.
Ao executar o comando take 4 lista a função será executada da seguinte forma:
1 : prox (1:[])
1 : (1+1) : prox [1+1]
1 : 2 : prox (2:[])
1 : 2 : (2+1) : prox [2+1]
1 : 2 : 3 : prox (3:[])
1 : 2 : 3 : (3+1) -- não requisitou mais do que quatro
1 : 2 : 3 : 4
Além da notação (x:resto) podemos também referenciar o segundo elemento da lista com (x1:t@(x2:resto)), na lista [1, 2, 3, 4, 5] esse padrão faz com que x1 = 1, t = [2,3,4,5], x2 = 2, resto = [3, 4, 5].
Exercício 02: O que o comando take 6 lista retornará na seguinte lista? Que sequência é essa? Tente responder sem utilizar o computador.
lista = 1 : 2 : prox lista
where
prox (x:t@(y:resto)) = (x+y) : prox t
Trabalhando com Listas
As funções associadas a manipulação de listas no Haskell podem ser vistas em List.lsh, vamos detalhar algumas dessas funções em seguida alteradas para simplificar.
length :: [a] -> Int
length l = len l 0
where
len :: [a] -> Int -> Int
len [] x = x
len (_:xs) x = len xs (x + 1)
A função length determina o tamanho de uma lista finita, a assinatura dela indica que recebe uma lista e retorna um tipo Int. A função define internamente a função len que recebe a lista e um valor inicial.
A função len é uma função recursiva que, caso a lista esteja vazia, ela retorna o valor x, caso contrário ela acrescenta 1 em x e chama a função recursivamente com a lista sem o primeiro elemento.
Note que a função retorna um tipo Int, caso o valor retornado deva ser combinado com um valor do tipo Integer deve ser convertido com a função toInteger.
head :: [a] -> a
head (x:_) = x
head [] = error "Lista vazia"
A função head recebe uma lista do tipo genérico a e retorna um elemento do tipo a. A função possui dois padrões, no primeiro, com uma lista não-vazia, ela retorna o primeiro elemento, no segundo padrão, caso a lista esteja vazia, ela retorna uma mensagem de erro.
tail :: [a] -> [a]
tail (_:xs) = xs
tail [] = error "Lista vazia"
De forma similar, a função ` tail` recebe uma lista, porém retorna outra lista. No primeiro padrão da função ela retorna a lista sem o primeiro elemento (a cauda), e no segundo padrão ela emite uma mensagem de erro de lista vazia.
Exercício 03: Descreva o que as duas funções abaixo fazem.
last [x] = x
last (_:xs) = last xs
last [] = error "Lista vazia"
init [x] = []
init (x:xs) = x : init xs
init [] = error "Lista vazia"
Uma outra função bastante útil é a função null descrita a seguir:
null :: [a] -> Bool
null [] = True
null (_:_) = False
Se a lista for vazia, retorna True, caso contrário False.
Recuperando elemento(s) da lista
Conforme visto em outra aula, o operador !! permite recuperar o elemento da i-ésima posição da lista. Por exemplo, se tivermos a seguinte lista de números ímpares:
impares = [1,3..999]
print (impares !! 5)
A instrução impares !! 5 retornará o quinto número ímpar. Da mesma forma podemos recuperar os n primeiros elementos com a seguinte função:
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
A função take n lista retorna uma lista com os n primeiros valores de lista. Essa função possui três padrões, o primeiro padrão, quando o valor de n for menor ou igual a 0, retorna a lista vazia, no segundo padrão ela retorna vazio caso a lista já esteja vazia e, no terceiro padrão, ele retorna o primeiro elemento concatenado com o retorno da chamada recursiva com n-1.
Como exemplo, considere a chamada take 3 [1,2..], a função realizará os seguintes passos:
take 3 (1:[2..]) = 1 : take 2 [2..]
take 3 (1:[2..]) = 1 : 2 : take 1 [3..]
take 3 (1:[2..]) = 1 : 2 : 3 : take 0 [4..]
take 3 (1:[2..]) = 1 : 2 : 3 : []
take 3 (1:[2..]) = [1,2,3]
Da mesma forma, podemos pular os n primeiros elementos com a função drop:
drop :: Int -> [a] -> [a]
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
Ao chamar drop 3 [1,2,3,4,5,6,7], a função realizará os seguintes passos:
drop 3 (1:[2,3,4,5,6,7]) = drop 2 [2,3,4,5,6,7]
drop 2 (2:[3,4,5,6,7]) = drop 1 [3,4,5,6,7]
drop 1 (3:[4,5,6,7]) = drop 0 [4,5,6,7]
drop 0 [4,5,6,7] = [4,5,6,7]
Finalmente, podemos dividir a lista em duas partes com a função splitAt:
splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs = (take n xs, drop n xs)
Como exemplo, temos que a chamada splitAt 3 [1,2,3,4,5,6,7] retornará ([1,2,3], [4,5,6,7]).
Exercício 04: Crie a função mediana que recebe uma lista de valores ordenados e retorna a mediana. A mediana de uma sequência de valores é o valor do meio, quando a lista contém um número ímpar de elementos, ou a média entre os dois valores do meio, quando a lista possui um número par de elementos.
mediana :: Num a => [a] -> a
Exercício 05: Exercício 06:
Recuperando e removendo elementos condicionalmente
Considere as funções:
takeWhile :: (a -> Bool) -> [a] -> [a]
takeWhile _ [] = []
takeWhile p (x:xs)
| p x = x : takeWhile p xs
| otherwise = []
dropWhile :: (a -> Bool) -> [a] -> [a]
dropWhile _ [] = []
dropWhile p xs@(x:xs')
| p x = dropWhile p xs'
| otherwise = xs
Ambas recebem uma função que recebe um tipo qualquer e retorna um booleano, uma lista, e retornam uma lista. A leitura dessas funções é pegue/remova os elementos da lista enquanto a condição imposta pela função seja verdadeira. Para exemplificar, vamos criar uma função que retorna se um número é menor do que 0 ou não:
menor0 :: Num a => a -> Bool
menor0 x = x < 0
Ao fazer takeWhile menor0 [-10,-9..10] obteremos como resposta a lista [-10,-9,-8,-7,-6,-5,-4,-3,-2,-1], por outro lado, se fizermos dropWhile menor0 [-10,-9..10] obteremos a lista [0,1,2,3,4,5,6,7,8,9,10].
Para facilitar a utilização de tais funções, quando a função de condição for pequena, podemos utilizar as funções anônimas. Uma função anônima é definida por:
\par1 par2 .. parn -> expr
Em que par são os parâmetros de entrada e expr a expressão de retorno, dessa forma não precisamos dar um nome para a função ou formalizá-la e o exemplo anterior ficaria:
takeWhile (\x -> x < 0) [-10,-9..10]
dropWhile (\x -> x < 0) [-10,-9..10]
As funções anônimas mais simples podem ser expressas através do estilo Pointfree, em que a variável está implícita dentro da definição:
takeWhile (< 0) [-10,-9..10]
dropWhile (< 0) [-10,-9..10]
Exemplos de Pointfree:
(+) 2 3 -- 5
(+1) 2 -- 3
(1+) 2 -- 3
(*3) 2 -- 6
Exercício 07:
Aplicando uma função em elementos da lista
Digamos que temos uma lista v representando um vetor numérico e queremos aplicar uma função de transformação nesse vetor, a função sin por exemplo. Uma alternativa seria fazer:
u = [sin vi | vi <- v]
Alternativamente podemos utilizar a função map:
u = map sin v
A função map f l aplica a função f em cada elemento da lista l.
Exercício 08:
Filtrando os elementos da lista
Uma outra tarefa comum é eliminar elementos de uma lista que não atendam a um critério definido por uma função pred:
filter :: (a -> Bool) -> [a] -> [a]
filter _pred [] = []
filter pred (x:xs)
| pred x = x : filter pred xs
| otherwise = filter pred xs
A função filter constrói uma lista com os elementos da lista passada como parâmetro que retornem verdadeiro para pred. Digamos que queremos extrair uma lista de elementos pares de uma lista qualquer:
lista = [1..100]
even x = (x `rem` 2) == 0
listaPar = filter even lista
Exercício 09:
Reduzindo uma lista
Em muitas ocasiões precisamos aplicar uma função nos elementos de uma lista, dois a dois, de tal forma a retornar apenas um elemento. Por exemplo, considere a somatória dos valores de uma lista:
somatoria :: Num a => [a] -> a
somatoria [] = 0
somatoria (x:xs) = x + (somatoria xs)
A somatória nada mais é do que uma aplicação da função soma cumulativamente nos elementos da lista. Se considerarmos a função produtoria teríamos:
produtoria :: Num a => [a] -> a
produtoria [] = 1
produtoria (x:xs) = x * (produtoria xs)
As únicas diferenças para as duas funções são: o valor utilizado para a lista vazia e a operação realizada (*). Podemos generalizar esse tipo de função como:
foldr :: (a -> b -> a) -> a -> [b] -> a
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
A função foldr recebe uma função a ser aplicada a dois elementos, um valor do tipo a, uma lista do tipo b e retorna um valor do tipo a. O uso de dois tipos genéricos é para generalizar o uso dessa função. Repare que a função foldr é muito similar as funções somatoria e produtoria descritas acimas. Essas funções poderiam ser definidas como:
somatoria lista = foldr (+) 0 lista
produtoria lista = foldr (*) 1 lista
Note que foldr não apresenta recursão caudal, isso pode ser facilmente resolvido com a introdução da função foldl:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
Com isso podemos implementar uma função reverse (já existente no Haskell) que inverte a ordem dos elementos da lista:
reverse :: [a] -> [a]
reverse = foldl (flip (:)) []
A função flip (:) recebe uma lista e um valor e coloca o valor na frente da lista:
flip (:) [2,3,4] 1 -- [1,2,3,4]
Exercício 10:
Combinando duas listas
Existem diversas situações em que duas listas devem ser combinadas. O exemplo mais trivial é a concatenação de duas listas, digamos que temos lista1 = [1,2,3] e lista2 = [4,5,6], podemos concatená-las com:
lista = lista1 ++ lista2
E teremos que lista = [1,2,3,4,5,6].
Em outra situação podemos ter uma lista representando as coordenadas x de diversos pontos e outra representando as coordenadas y correspondentes, e precisamos combinar as informações em uma lista de tuplas representando a coordenada completa de cada ponto.
Ou seja, queremos que as listas x = [1.0, 0.5, 0.7] e y = [0.3, -1.2, 0.7] se torne pontos = [(1.0,0.3), (0.5, -1.2), (0.7, 0.7)]. Para isso temos a função zip implementada como:
zip :: [a] -> [b] -> [(a,b)]
zip (a:as) (b:bs) = (a,b) : zip as bs
zip _ _ = []
E com isso basta chamar pontos = zip x y para obter o resultado desejado.
Finalmente, se duas listas representam dois vetores diferentes e queremos realizar a operação de soma de vetores, implementaríamos como:
somaVetores :: [a] -> [a] -> [a]
somaVetores (v:vs) (u:us) = v+u : somaVetores vs us
somaVetores _ _ = []
Da mesma forma podemos querer realizar operações diferentes da soma entre os elementos de dois vetores, podemos então generalizar a função com o zipWith:
zipWith :: (a->b->c) -> [a]->[b]->[c]
zipWith f (a:as) (b:bs) = f a b : zipWith f as bs
zipWith _ _ _ = []
E poderíamos fazer:
somaVetores v u = zipWith (+) v u
Repetições, replicações e ciclos
A função repeat x fornece uma lista infinita contendo apenas o valor x:
repeat :: a -> [a]
repeat x = xs where xs = x : xs
take 5 (repeat 2) -- [2,2,2,2,2]
A função replicate n x gera uma lista de tamanho n com o valor x, e pode ser implementada como:
replicate :: Int -> a -> [a]
replicate n x = take n (repeat x)
Já a função cycle lista gera uma lista infinita de repetições da lista fornecida:
cycle :: [a] -> [a]
cycle [] = error "Prelude.cycle: empty list"
cycle xs = xs' where xs' = xs ++ xs'
take 10 (cycle [0,1]) -- [0,1,0,1,0,1,0,1,0,1]
Exercício 11:
O método de Newton é utilizado para encontrar aproximações das raízes de uma função f qualquer. Dada a função f e sua derivada f' e um chute inicial x0 para uma das raízes da função, obtemos uma melhor aproximação com:
x1 = x0 - (f x0)/(f' x0)
Dado x1, podemos repetir o processo para achar uma aproximação ainda melhor:
x2 = x1 - (f x1)/(f' x1)
E repetimos o processo até que algum critério de convergência seja atingido. Vamos implementar em Haskell esse método para achar uma das raízes de \(x^2 - 4x + 10\). Primeiro definimos f e f' e uma função delta:
f x = x^2 - 4*x + 2
f' x = 2*x - 4
delta x = (f x) / (f' x)
Agora criamos a função naoConvergiu que retorna verdadeiro se o valor absoluto de delta for maior que 1e-10, indicando que a redução de x ainda é significativa. Também criamos uma função para atualizar o valor de x:
naoConvergiu x = abs (delta x) > 1e-10
atualiza x = x - (delta x)
Para repetir a aplicação da função atualiza temos a função iterate definida como:
iterate :: (a -> a) -> a -> [a]
iterate f x = x : iterate f (f x)
Essa função gera uma lista infinita de aplicações sucessivas de uma função f. Ou seja, a chamada da função iterate (\x -> 2*x) 1 irá gerar a lista [1, 2*1, 2*2*1, 2*2*2*1...]. Se fizermos:
print (take 100 $ iterate atualiza 1)
Obteremos uma lista com 100 elementos com diversas aproximações da raíz. Percebemos que a raíz convergiu para aproximadamente 0.5858, ou \(2 - \sqrt{2}\), que é a solução analítica. Finalmente podemos criar uma função raiz que aplica o método de Newton até que obtenha uma aproximação boa. Para isso podemos remover todos os elementos da lista que retornem True ao aplicar a função naoConvergiu e, então, pegar o primeiro elemento da lista restante:
raiz = head . (dropWhile naoConvergiu)
Finalmente, temos que o método de Newton é definido por:
newton x0 = raiz $ iterate atualiza x0
Operações lógicas em listas
Digamos que queremos criar uma lista de números primos:
primos = [x | x <- [1..1000], primo x]
A função primo deve verificar se existe um número de 2 até x-1 que divida x, se o conjunto de números que dividem x for vazio, então ele é primo:
primo x = null [x' | x' <- [2..x-1], x `rem` x' == 0]
Uma vez que temos a lista de primos, podemos verificar se um número y é primo caso ele pertença a essa lista. Para isso precisamos verificar se um dos elementos da lista é igual a y, o primeiro passo é comparar y com todos os valores da lista:
ehPrimo y = map (==y) primos
Em seguida, temos que verificar se algum deles é verdadeiro, podemos aplicar o operador lógico ou (||) em todos os elementos da lista utilizando as funções foldl ou foldr:
ehPrimo y = foldr (||) False (map (==y) primos
A aplicação de foldr retorna True se pelo menos um elemento da lista for verdadeiro e False caso contrário. A aplicação de foldr é generalizada como a função or em uma lista (e a contrapartida a função and):
and :: [Bool] -> Bool
and = foldr (&&) True
or :: [Bool] -> Bool
or = foldr (||) False
Exercício 12: Reparem que o uso de foldr nos permite aplicar as funções and e or em listas infinitas, dado que exista um elemento False para o caso de and e um elemento True para o caso de or.
E da mesma forma podemos definir as funções any (qualquer verdadeiro) e all (todos verdadeiros) que recebem um predicado como parâmetro:
any :: (a -> Bool) -> [a] -> Bool
any p = or . map p
all :: (a -> Bool) -> [a] -> Bool
all p = and . map p
Finalmente, podemos definir as funções elem e notElem que determina se x é um elemento da lista ou não:
elem :: (Eq a) => a -> [a] -> Bool
elem x = any (== x)
notElem :: (Eq a) => a -> [a] -> Bool
notElem x = all (/= x)
Nossa função ehPrimo se torna:
ehPrimo y = elem y primos