Haskell/Listas III

Origem: Wikilivros, livros abertos por um mundo aberto.



Este módulo encontra-se em processo de tradução. A sua ajuda é bem vinda.

Folds[editar | editar código-fonte]

Assim 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:

  1. soma []     = 0
    soma (x:xs) = x + soma xs
    
  2. produto []     = 1
    produto (x:xs) = x * produto xs
    
  3. 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 | editar código-fonte]

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:

  1. soma: a função é (+) e o acumulador neutro é 0.
  2. produto: a função é (*) e o acumulador neutro é 1.
  3. 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 | editar código-fonte]

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 | editar código-fonte]

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 | editar código-fonte]

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[editar | editar código-fonte]

Você 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
  1. Defina as seguintes funções recursivas, e depois escreva uma definição usando foldr ou foldl:
    • eListas :: [Bool] -> Bool, que retorna True se uma lista de Bools contiver apenas True, ou False, caso contrário.
    • ouListas :: [Bool] -> Bool, que retorna True se pelo menos um elemento de uma lista de Bools for verdadeiro, ou False, caso contrário.
  2. Defina as seguintes funções usando foldl1 ou foldr1:
    • maximo :: Ord a => [a] -> a, que retorna o elemento de maior valor de uma lista. Use a função max :: Ord a => a -> a -> a, que retorna seu argumento de maior valor.
    • minimo :: Ord a => [a] -> a, que retorna o elemento de menor valor de uma lista. Use a função min :: Ord a => a -> a -> a, que retorna seu argumento de menor valor.
  3. Use uma função fold (qual?) para definir inverter :: [a] -> [a], a qual inverte a ordem dos elementos de uma lista.
As funções do Prelude and, or, maximum e minimum correspondem a estas funções destes exercícios, respectivamente.

Scans[editar | editar código-fonte]

Um 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
  1. Escreva sua própria definição de scanr: primeiro, use recusrividade, e depois use foldr. Faça o mesmo para scanl.
  2. Defina as seguintes funções:
    • fatLista :: Integer -> [Integer], que retorna uma lista dos fatoriais de 1 até o valor de seu argumento. Por exemplo: fatLista 4 = [1,2,6,24].

Filtros[editar | editar código-fonte]

Uma 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[editar | editar código-fonte]

Compreensã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 de n.
  • Para cada n, testar se ePar n é verdadeiro.
  • Se, e somente se a condição de ePar for verdadeira, acrescentar n à 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
  1. Escreva a função retornaDivisiveis :: Int -> [Int] -> [Int] que filtra uma lista de inteiros e retorna apenas os elementos que são divisíveis pelo seu primeiro argumento. Dica: x é divisível por n se mod x n == 0.
  2. Escreva a função selecionaCaudas :: [[Int]] -> [[Int]] usando compreensão de listas. Ela deve retornar a cauda das listas cujas cabeças são maiores que 5, e deve eliminar listas vazias:
    selecionaCaudas [[7,6,3],[],[6,4,2],[9,4,3],[5,5,5]] = [[6,3],[4,2],[4,3]]
  3. A ordem das condições altera o resultado da função? Descubra usando as funções que você acabou de escrever.
  4. Vimos que compreensão de listas são combinações de filter e map, mas agora você deve fazer o caminho inverso: defina mapear e filtrar usando compreensão de listas.
  5. Reescreva fstComSndPar usando filter e map em vez de compreensão de listas.