Haskell/Listas III
|
Este módulo encontra-se em processo de tradução. A sua ajuda é bem vinda. |
Folds
editarAssim como map, folds são funções de alta ordem que recebem uma função e uma lista. Entretanto, em vez de aplicar a função elemento por elemento, um fold opera sobre a lista como um todo. A palavra fold significa "dobrar", em inglês, e veremos como o funcionamento destas funções tem a ver com este verbo. Primeiro, começando com um exemplo simples.
Veja as seguintes funções:
soma [] = 0 soma (x:xs) = x + soma xs
produto [] = 1 produto (x:xs) = x * produto xs
concatenar [] = [] concatenar (x:xs) = x ++ concatenar xs
As funções soma, produto e concatenar apresentam um padrão recursivo conhecido como fold. É como se a função "dobrasse" a lista de certa maneira para rotornar um único valor final, em vez de uma lista, como acontece com map.
No Prelude, temos quatro funções desse tipo: foldr, foldl, foldr1 e foldl1.
Fold right: foldr
editar
Esta função é a versão associativa-à-direita. Ela dobra a lista da esquerda para a direita. Quando ela é aplicada, foldr usa a função de entrada para combinar cada elemento da lista ao valor acumulado, cujo valor inicial é outro argumento.
foldr pode ser escrita como:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f acum [] = acum
foldr f acum (x:xs) = f x (foldr f acum xs)
O primeiro argumento é uma função de dois argumentos. O segundo argumento é o valor inicial do acumulador, que geralmente começa com um valor "neutro" que depende de cada caso.
Comparando com as funções que vimos no começo da seção:
soma: a função é(+)e o acumulador neutro é0.produto: a função é(*)e o acumulador neutro é1.concatenar: a função é(++)e o acumulador neutro é[].
Nestes três exemplos, os argumentos de f tem ambos o mesmo tipo (a -> a -> a), mas como vimos pela definição de foldr, isso não é uma exigência (a -> b -> b), apenas uma coincidência.
Uma boa maneida de visualizar a aplicação de foldr é usando a representação de uma "árvore". A aplicação
foldr f acum (a:b:c:[])
pode ser expandida para
f a (f b (f c acum))
a qual pode ser facilmente vista e entendida asssim:
: f
/ \ / \
a : foldr f acum a f
/ \ -------------> / \
b : b f
/ \ / \
c [] c acum
Veja o último nível: cada ramo (c e acum) são argumentos para f, cujo resultado se torna o segundo argumento para mais uma aplicação de f no nível superior, sendo que o primeiro argumento vem da lista (b). Perceba também que a aplicação começa do fim da lista e segue em direção ao começo.
Fold left: foldl
editar
A versão associativa-à-esquerda se chama foldl. Ela processa a lista na direção oposta, ou seja, da esquerda para direita. Ela poderia ser definida como
foldl :: (b -> a -> b) -> b -> [a] -> b
foldl f acum [] = acum
foldl f acum (x:xs) = foldl f (f acum x) xs
Se expandirmos foldl f acum (a:b:c:[]) teremos
f (f (f acum a) b ) c
que podemos visualizar em forma de árvore assim:
: f
/ \ / \
a : foldl f acum f c
/ \ -------------> / \
b : f b
/ \ / \
c [] acum a
Podemos ver que a lista é processada a partir do começo, seguindo até o fim.
foldl e foldr são opostos?
editar
Talvez você tenha percebido que em alguns casos foldl e foldr não são opostas entre si. Vejamos um caso envolvendo subtração:
foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
Estes casos vão retornar True ou Flase? Pensar que foldr vai da direita para a esquerda, pode nos levar à conclusão de que a segunda igualdade é verdadeira, mas não é bem isso que acontece:
Prelude> foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1 True Prelude> False
Isso acontece porque a diferença entre foldr e foldl está na forma da expressão resultante, e não na ordem dos elementos da lista. Vejamos a expansão destas expressões:
foldl (-) 6 [3, 2, 1] == 6 - 3 - 2 - 1
foldl (-) (6 - 3) [2, 1] == 6 - 3 - 2 - 1
foldl (-) ((6 - 3) - 2) [1] == 6 - 3 - 2 - 1
foldl (-) (((6 - 3) - 2) - 1) [] == 6 - 3 - 2 - 1
(((6 - 3) - 2) - 1) == 6 - 3 - 2 - 1
6 - 3 - 2 - 1 == 6 - 3 - 2 - 1
True
foldr (-) 6 [1, 2, 3] == 6 - 3 - 2 - 1
1 - (foldr (-) 6 [2, 3]) == 6 - 3 - 2 - 1
1 - (2 - (foldr (-) 6 [3])) == 6 - 3 - 2 - 1
1 - (2 - (3 - (foldr (-) 6 []))) == 6 - 3 - 2 - 1
1 - (2 - (3 - (6))) == 6 - 3 - 2 - 1
1 - 2 + 3 - 6 == 6 - 3 - 2 - 1
False
Perceba também que o argumento acumulador (6) encontra-se sempre dentro do maior número de parêntenses.
foldr1 e foldl1
editar
A anotação de tipo de foldr exige que seja fornecido um valor inicial para o argumento acumulador, e assim o fizemos nos exemplos anteriores. No caso de foldr1, não há necessidade de definí-lo, sendo que o último elemento da lista será o valor inicial:
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 f [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
foldr1 _ [] = error "Prelude.foldr1: empty list"
O mesmo vale para foldl1:
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
foldl1 _ [] = error "Prelude.foldl1: empty list"
Nestas duas funções, todos os argumentos da função devem ser do mesmo tipo, bem como os elementos da lista. O resultado também será deste mesmo tipo.
Folds e avaliação preguiçosa
editarVocê verá que as versões associativas-à-direita das funções de fold são mais comuns que as associativas-à-esquerda, em Haskell. O motivo disso é a possibilidade de operarmos em listas infinitas. Uma vez que a chamada recursiva em foldl não é feita dentro de um argumento de f, a expressão só pode ser avaliada quando toda a lista for processada, o que é impossível de acontecer se ela for infinita. Já com foldr, a avaliação da lista pode ser interrompida a qualquer momento pelo compilador, seguindo algum critério do programa.
Como exemplo, considere a função eco que repete um número n por n vezes numa lista:
eco :: [Int] -> [Int]
eco ls = foldr faux [] ls
where faux x xs = (replicate x x) ++ xs
Testando no GHCi:
Prelude> take 11 (eco [1..]) [1,2,2,3,3,3,4,4,4,4,5]
Poderíamos ter usado foldl:
eco :: Int -> Int
eco ls = foldl faux [] ls
where faux xs x = xs ++ (replicate x x)
Entretanto, usar take 11 (eco [1..]) neste caso, faria o programa entrar num processo recursivo infinito, possivelmente travando a máquina. Se você quiser tentar, use Ctrl-c para interromper o processamento quando quiser.
Como exemplo final, a função map que vimos no capítulo passado pode ser definida em termos de alguma função fold. Novamente, prefere-se foldr para podermos operar em listas infinitas:
map :: (a -> b) -> [a] -> [b]
map f ls = foldr faux [] ls where faux x xs = f x : xs
Funções fold exigem certo tempo para nos acostumarmos com elas. Entretanto, elas são bastante recorrentes em programação funcional e, eventualmente, seu uso se torna bastante natural para o programador. Toda vez que alguém quiser atravesar uma lista e realizar alguma operação com todos os seus elementos, muito provavelmente uma fold será usada.
| Exercícios |
|---|
and, or, maximum e minimum correspondem a estas funções destes exercícios, respectivamente. |
Scans
editarUm função scan ("varredura", em inglês) é como se fosse uma mistura de map e uma função fold. Operar um fold numa lista resulta num valor acumulado final, enquanto que usar map opera uma função elemento a elemento numa lista. Uma scan realiza ambos: acumula um valor final, como uma fold, mas retorna os valores parciais para cada elemento da lista, como map.
Assim, como as funções fold, o Prelude contém quatro funções scan:
scanl :: (b -> a -> b) -> b -> [a] -> [b]
scanl1 :: (a -> a -> a) -> [a] -> [a]
scanl é a versão associativa-à-esquerda, sendo que o segundo arugmento (o parâmetro acumulador) se torna o primeiro elemento da lista resultante: scanl (+) 0 [1..3] = [0,1,3,6]. Já scanl1 é versão que não exige valor inicial, sendo que o primeiro elemento da lista se torna o parâmetro acumulador: scanl1 (+) [1..3] = [1,3,6].
scanr :: (a -> b -> b) -> b -> [a] -> [b]
scanr1 :: (a -> a -> a) -> [a] -> [a]
Estas são as versões associativas-à-direita. Em scanr, o parâmetro acumulador se torna o último elemento da lista: scanr (+) 0 [1..3] = [6,3,1,0]. Na versão scanr1, o primeiro elemento da lista se torna o valor inicial do parâmetro acumulador, e o último elemento da lista de saída: scanr1 (+) [1..3] = [6,3,1].
| Exercícios |
|---|
|
Filtros
editarUma operação bastante comum em listas é a filtragem: gerar uma nova lista selecionando elementos de outra lista de entrada que atenderem a uma certa condição. Vejamos um exemplo simples de uma função que seleciona apenas os números pares de uma lista de inteiros. Usaremos a função mod que computa o resto da divisão entre dois números:
manterPares :: [Int] -> [Int]
manterPares [] = []
manterPares (n:ns) =
if (mod n 2) == 0
then n : (manterPares ns)
else manterPares ns
Esta definição é bastante específica. Porém, podemos escrevê-la usando uma função mais geral fornecida no Prelude chamada filter cuja assinatura é:
filter :: (a -> Bool) -> [a] -> [a]
Portanto, precisamos de uma função cuja assinatura seja a -> Bool para testar todos os elementos de uma lista. Se ela retorna True, o elemento é mantido na saída de filter. Se for Flase, o elemento é eliminado.
Para reescrevermos manterPares usando filter, precisamos definir uma função auxilar para testar a paridade dos números:
ePar :: Int -> Bool
ePar n = (mod n 2) == 0
Agora, basta usá-la em filter:
manterPares ns = filter ePar ns
Compreensão de listas
editarCompreensão de listas é um açúcar sintático que nos permite criar listas a partir de algumas operações bastante comuns, tais como filter. Por exemplo, poderíamos escrever manterPares da seguinte forma:
manterPares es = [n | n <- es, ePar n]
É uma forma sintática bastante compacta, mas bem simples de entender o que está acontecendo:
- Tome a lista
es, e seja cada um de seus elementos chamado den. - Para cada
n, testar seePar né verdadeiro. - Se, e somente se a condição de
eParfor verdadeira, acrescentarnà nova lista sendo criada.
A semelhança desta sintaxe com a notação matemática para representar conjuntos é proposital. A compreensão pode, portanto, ser lida de forma semelhante também: uma lista de elementos tais que pertença a e que seja par.
Assim, se es for [1,2,3,4], o resultado da compreensão seria [2,4]. Como 1 e 3 não passam no teste ePar, eles são excluídos.
Uma das vantagens dessa sintaxe é que ela pode ser facilmente estendida. Podemos usar quantos testes quisermos, ou nenhum. Todas as condições devem ser separadas por virgulas, e devem resultar em um Bool. Suponha que queiramos filtrar os números pares maiores que 100:
manterParesGrandes :: [Int] -> [Int]
manterParesGrandes es = [n | n <- es, ePar n, n > 100]
Além disso, podemos usar uma expressão no lugar de apenas n do lado direito da barra vertial. Para subtrair uma unidade de cada elemento antes de adicioná-lo à lista:
paresMenosUm es = [n - 1 | n <- es, ePar n]
Isso quer dizer que compreensão de lista envolve as funcionalidades de filter e map.
Além disso, podemos também usar casamento de padrões. Suponha que a lista de entrada seja uma dupla (Int, Int) e queremos uma lista com o primeiro elemento dela, sendo que a condição deve ser ePar deve ser avaliada usando o segundo elemento. Podemos usar as funções fst e snd para escrever
fstComSndPar :: [(Int, Int)] -> [Int]
fstComSndPar ps = [fst p | p <- ps, ePar (snd p)]
Porém, podemos usar casamento de padrões da seguinte forma:
fstComSndPar ps = [x | (x, y) <- ps, ePar y]
Casamento de padrões pode ser usado na expressão à esquerda da barra vertical, e também podemos usar mais de uma lista para obter elementos, as quais não precisam ser argumentos:
todasDuplas :: [(Int, Int)]
todasDuplas = [(x, y) | x <- [1..4], y <- [5..8]]
Acabamos de criar uma lista de duplas contendo todas as combinações possíveis entre x e y:
Prelude> let todasDuplas = [(x, y) | x <- [1..4], y <- [5..8]] Prelude> todasDuplas [(1,5),(1,6),(1,7),(1,8) ,(2,5),(2,6),(2,7),(2,8) ,(3,5),(3,6),(3,7),(3,8) ,(4,5),(4,6),(4,7),(4,8)]
E ainda poderíamos acrescentar alguma condição. Por exemplo, a soma dos elementos das duplas devem ser maior que 8:
Prelude> [(x, y) | x <- [1..4], y <- [5..8], x + y > 8] [(1,8),(2,7),(2,8),(3,6),(3,7),(3,8),(4,5),(4,6),(4,7),(4,8)]
| Exercícios |
|---|
|