Haskell/Listas II

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

Até agora já vimos como construir listas usando (:) e [], e vimos também como criar funções recursivas que operam em listas. Neste capítulo teremos nosso primeiro contato com listas infinitas, compreensão de listas e funções de alta ordem.

Nota: Muitos dos exemplos a seguir são operações matemáticas. Por simplicidade, usaremos sempre o tipo Integer quando trabalharmos com números. Se você quiser convertê-las para outros tipos de números, basta escrever funções polimórficas para a classe Num, como vimos no capítulo Tipos básicos II.

Mais notações para listas

Definindo séries

Haskell possui um notação muito conveniente para definirmos listas contendo uma série sequencial de valores. Por exemplo, tente no GHCi:

Prelude> [1..10]
[1,2,3,4,5,6,7,8,9,10]

A notação .. nos permite criar uma lista de valores igualmente espaçados entre si.

Código          Resultado
-------         ---------
[1..10]         [1,2,3,4,5,6,7,8,9,10]
[2,4..10]       [2,4,6,8,10]
[5,4..1]        [5,4,3,2,1]
[1,3..10]       [1,3,5,7,9]

Em termos matemáticos, esta notação nos permite criar apenas progressões aritméticas. Isso quer dizer que não podemos digitar [2,4,8,16..1024] esperar que o resultado seja [2,4,8,16,32,64,128,256,512,124].

Na verdade, esta notação também pode ser usada com outros tipos não-númericos, desde que seus valores possam ser enumerados para podermos criar uma sequência:

Prelude> ['a'..'z']
"abcdefghijklmnopqrstuvwxyz"

Parênteses devem ser usados quando os valores forem não-numéricos:

Prelude> [(False)..(True)]
[False,True]

Listas infinitas

Nota: Caso você execute algum comando que faça o compilador avaliar uma lista infinita, o processo só será interrompido em dois casos: 1) você usou uma função que possui alguma condição de parada; 2) interrupção manual usando Ctrl-C.

Graças à avaliação preguiçosa de Haskell, podemos definir listas infinitas. A expressão

y = [1..]

cria uma lista infinita números sucessivos a partir de 1. Se fosse

y = [10,20..]

teríamos uma lista infinita com todos os múltiplos de 10.

Tais listas são úteis na prática porque, na prática, elas nunca são avaliadas além do necessário. Aplicações em que estas listas são usadas sem critério de parada, apesar de existirem, são minoria. Isso porque o desejável é que os programas encerrem seu processamento em algum momento. Entretanto, avaliar uma lista infinita é uma das alternativas para que um programa entre num loop infinito, o que é necessário em certo jogos, por exemplo.

Suponha que você precise trabalhar apenas com os cinco primeiros múltiplos de 27. Em vez de escrevê-los literalmentel, basta fazer:

cinco27 = take 5 [27,(2*27)..]

Listas vazias

Mesmo tendo a opção de usar head e tail para repartir listas, usar casamento de padrões é, quase sempre, a melhor escolha. O ponto é que é facil nos esquecermos que head e tail causam erro se a lista for vazia. Por isso temos a função null :: [a] -> Bool que retorna True se a lista for vazia, e False se não for. Uma função para dobrar os elementos de uma lista poderia ser escrita assim:

dobrarLista :: [Integer] -> [Integer]
dobrarLista xs
    | null xs   = []
    | otherwise = 2 * (head xs) : dobrarLista (tail xs)

Exercício

Defina a função recursiva repetir :: a -> [a] que cria listas infinitas. O Prelude possui a repeat que realiza a mesma tarefa.

Recriando listas

Seguindo a recomendação da seção anterior, vamos reescrever dobrarLista usando casamento de padrões:

dobrarLista :: [Integer] -> [Integer]
dobrarLista [] = []
dobrarLista (n:ns) = (2 * n) : dobrarLista ns

O caso base é a lista vazia, que retorna uma lista vazia. No caso recursivo, dobrarLista cria uma nova lista usando (:). O primeiro elemento da lista resultante é o dobro da cabeça da lista de entrada, sendo que o restante do resultado é obtido de forma recursiva, usando a cauda da entrada como argumento.

Vejamos como acontece a avaliação de dobrarLista [1,2,3,4]:

dobrarLista 1:[2,3,4] = (1*2) : dobrarLista (2 : [3,4])
                      = (1*2) : (2*2) : dobrarLista (3 : [4])
                      = (1*2) : (2*2) : (3*2) : dobrarLista (4 : [])
                      = (1*2) : (2*2) : (3*2) : (4*2) : dobrarLista []
                      = (1*2) : (2*2) : (3*2) : (4*2) : []
                      = 2 : 4 : 6 : 8 : []
                      = [2, 4, 6, 8]

O momento em que as expressões de multiplicação são avaliadas não afetam o resultado final da função, desde que elas não resultem em algum tipo de erro.

Essa flexibilidade na ordem de avaliação é uma propriedade importante de Haskell. Sendo uma linguagem de programção funcional pura, é o compilador que decide quando as expressões são avalidas. Sendo uma linguagem preguiçosa, a avaliação geralmente só é feita quando um resultado final é exigido, o que podem nem acontecer.

Generalizando a operação

Para calcular o triplo dos elementos de uma lista, poderíamos fazer o mesmo que fizemos em dobrarLista:

triplicarLista :: [Integer] -> [Integer]
triplicarLista [] = []
triplicarLista (n:ns) = (3 * n) : triplicarLista ns

Entretanto, não queremos escrever diferentes funções de multiplicação de listas para cada fator escolhido, seja para duplicar, triplicar, quadruplicar, ou qualquer outro. Por isso, vamos criar uma função generalizada que permita multiplicar os elementos de uma lista por qualquer número. Ela terá dois argumentos: o fator de multiplicação e a lista de Integer:

multiplicarLista _ [] = []
multiplicarLista m (n:ns) = (m * n) : multiplicarLista m ns

Neste exemplo usamos _ para ignorar o valor do fator no caso base: independente do valor do primeiro argumento, se o segundo for uma lista vazia, multiplicarLista retorna uma lista vazia.

Um teste no GHCi mostra que mutiplicarLista funciona:

Prelude> multiplicarLista 17 [1,2,3,4]
[17,34,51,68]

Exercício

Escreva as seguintes funções e teste-as no GHCi. Não se esqueça das assinaturas de tipo.

1. tomarInt retorna os primeiro n elementos de uma lista. Exemplo: tomarInt 4 [11,21,31,41,51,61] = [11,21,31,41].
2. eliminarInt elemina os n primeiros elementos de uma lista e retorna o restante. Exemplo: eliminaInt 3 [11,21,31,41,51] = [41,51].
3. somaInt retorna a soma dos elementos de uma lista.
4. scanSoma soma os elementos de uma lista e retorna uma lista com valores acumulados. Exemplo: scanSoma [2,3,4,5] = [2,5,9,14].
5. difs retorna a diferença entre elementos adjacentes de uma lista. Exemplo: difs [3,5,6,8] = [2,1,2]. (Dica: uma possível solução é escrever uma função auxiliarm que toma duas listas e calcula a diferença entre seus elementos correspondentes. Outra solução é tentar usar casamento de padrões com lista de pelo menos dois elementos: (x:y:ys).)

As três primeiras lista estão no Prelude e se chamam take, drop e sum.

Caso geral

Começamos este capítulo com uma função especializada em multiplicar os elementos de uma lista por 2. Depois, percebemos que é possível criar uma função mais geral que multiplique uma lista por qualquer valor desejado. Mas e se quiséssemos fazer qualquer outra operação, como a adição, por exemplo?

Podemos criar uma função ainda mais geral que multiplicarLista usando outra propriedade bastante importante de Haskell. Vejamos a anotação de tipo:

multiplicarLista :: Integer -> [Integer] -> [Integer]

A primeira coisa a saber é que podemos considerar -> como sendo um operador com associatividade-à-direita, bem como cons. Isso quer dizer que a anotação de tipo poderia ser escrita como

multiplicarLista :: Integer -> ([Integer] -> [Integer])

Podemos interpretar isso como se multiplicarLista recebesse apenas um argumento do Integer, e retornasse uma outra função cujo argumento é uma lista de Integer.

Poderíamos escrever dobrarLista em termos de multiplicarLista:

dobrarLista :: [Integer] -> [Integer]
dobrarLista xs = multiplicarLista 2 xs

Ou, eliminando xs:

dobrarLista = multiplicarLista 2

Este tipo de escrita, em que não deixamos explícitos os argumentos é chamada de ponto livre (point-free, em inglês) ou sem ponto (pointless, em inglês).

Nossa nova definição nos diz que aplicar apenas um argumento a multiplicarLista nos retorna uma versão mais específica da função geral. Perceba que começamos com Integer -> [Integer] -> [Integer], e agora temos [Integer] -> [Integer]. Se aplicarmos mais um argumento, teremos um resultado final [Integer].

Agora podemos ver que funções em Haskell se comportam como quaisquer outros valores. Funções podem retornar outras funções, e função podem ser tratadas como objetos independentes sem mencionarmos seus argumentos. Elas se parecem com constantes. E poderíamos ter funções como argumentos de outras funções? Sim, e é justamente isso que nos permite generalizar ainda mais a função multiplicarLista. Queremos criar uma função que recebe uma outra função e que aplique-a aos elementos de uma determinada lista:

aplicarAosInteger :: (Integer -> Integer) -> [Integer] -> [Integer]
aplicarAosInteger _ [] = []
aplicarAosInteger f (n:ns) = (f n) : aplicarAosInteger f ns

Com aplicarAosInteger podemos aplicar qualquer função do tipo Integer -> Integer a uma lista de Integer. Podemos, então, reescrever multiplicarLista:

multiplicarLista :: Integer -> [Integer] -> [Integer]
multiplicarLista m = aplicarAosInteger ((*) m)

Usamos (*) com um único argumento para criarmos outra função pronta para receber mais um argumento, os quais viram da lista que seria o segundo argumento.

Currying

Se toda essa abstração acabou por confundí-lo, talvez uma explicação concreta ajude. Quando escrevemos 5 * 7 em Haskell, a função (*) não recebe dois argumento de uma só vez. Na verdade, ela primeiro recebe o 5 e retorna uma nova função, que vamos chamar de 5*. Depois, 5* recebe o seu próprio argumento, o 7, que foi o segundo de (*). A função 5* é avaliada com o argumento 7 e um resultado é produzido: 35.

Podemos dizer, então, que todas as funções em Haskell recebem apenas um argumento. Entretanto, se soubermos quantas funções intermediárias precisam ser criadas para chegarmos a um resultado final, a função original pode ser tratada como se tivesse mais de um argumento. O número de argumentos a que geralmente nos referimos é, na verdade, a quantidade de funções intermediárias de um argumento, mais o resultado final.

O processo de criar funções intermediárias por meio da aplicação de argumentos a funções complexas é chamado de currying, um termo cunhado em homenagem ao matemático Haskell Curry. O próprio nome "Haskell" é uma homenagem a mesma pessoa.

A função map

Enquanto aplicarAosInteger tem tipo (Integer -> Integer) -> [Integer] -> [Integer], sua definição não tem nada que a limite a ser aplicada a Integer. Usando a mesma lógica, poderíamos criar funções como aplicarAosChar, aplicarAosBool ou aplicarAosString. Todas elas teriam a mesma definição, exceto pela assinatura de tipo. Podemos, então, evitar toda essa redundância com um passo final: generalizar também a assinatura de tipo usando tipos polimórficos. O Prelude possui uma função que faz exatamente isso, chamada map:

map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = (f x) : map f xs

Usando map podemos definir muitas outras funções de forma bastante simples, pois ela é a solução geral para aplicar uma função a cada elemento de uma lista. Funções como map, as quais recebem outras funções como argumento, são chamadas de funções de alta ordem. Veremos mais sobre funções de alta ordem para processamento de listas no próximo capítulo.

Exercícios

Use map para criar uma função que recebe uma lista de Int e retorna outra lista cujos elementos sejam o oposto (sinal invertido) dos elementos do argumento de entrada. Implemente as três funções seguintes para codificação run-length usando duplas: rleCodifica "aaaabbaaa" = [(4,'a'),(2,'b'),(3,'a')]. rleDecodifica [(3,'d'),(2,'a'),(1,'b'),(1,'a')] = "bbbaaca" rleString "bbbaaca" = "3b2aca" As função concat e group podem ser úteis. Para usá-las você deve usar o pacote Data.List.