# Haskell/Listas III

* Listas III
* Básico
* Recursividade
* Listas II (listas infinitas, map)
* Listas III (folds, compreensão)
* Declaração de tipos
* Lambdas e operadores
* Casamento de padrões
* Estruturas de controle: case
* Funções de alta ordem
* Usando o GHCi

## Folds

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

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:
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
pode ser expandida para
a qual pode ser facilmente vista e entendida asssim:
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

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
Se expandirmos foldl f acum (a:b:c:) teremos
que podemos visualizar em forma de árvore assim:
Podemos ver que a lista é processada a partir do começo, seguindo até o fim.

### foldl e foldr são opostos?

Talvez você tenha percebido que em alguns casos foldl e foldr não são opostas entre si. Vejamos um caso envolvendo subtração:
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:
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:
Perceba também que o argumento acumulador (6) encontra-se sempre dentro do maior número de parêntenses.

### foldr1 e foldl1

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:
O mesmo vale para foldl1:
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

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:
Testando no GHCi:
Poderíamos ter usado foldl:
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:
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
* 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.
* 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.
* 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

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 é 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].
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
* Escreva sua própria definição de scanr: primeiro, use recusrividade, e depois use foldr. Faça o mesmo para scanl.
* 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

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:
Esta definição é bastante específica. Porém, podemos escrevê-la usando uma função mais geral fornecida no Prelude chamada filter cuja assinatura é:
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:
Agora, basta usá-la em filter:

## Compreensão de listas

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:
É 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 $n$ tais que $n$ pertença a $es$ 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:
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:
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
Porém, podemos usar casamento de padrões da seguinte forma:
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:
Acabamos de criar uma lista de duplas contendo todas as combinações possíveis entre x e y:
E ainda poderíamos acrescentar alguma condição. Por exemplo, a soma dos elementos das duplas devem ser maior que 8:
* Exercícios
* 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.
* 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]]
* A ordem das condições altera o resultado da função? Descubra usando as funções que você acabou de escrever.
* 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.
* Reescreva fstComSndPar usando filter e map em vez de compreensão de listas.