Haskell/Listas e n-uplas

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

Em Haskell, temos duas estruturas de dados fundamentais: listas e n-uplas. Elas agrupam vários valores num único dado, como veremos.

Listas

Abra uma sessão do GHCi para criarmos algumas listas:

Prelude> let numeros = [1,2,3,4]
Prelude> let vOUf  = [True, False, False]
Prelude> let strings = ["uma", "lista", "de", "strings"]

Colchetes são usados para delimitar listas, sendo que cada elemento deve ser separado por uma vírgula. A única restrição para a criação de uma lista é que todos os elementos devem ter o mesmo tipo. Tentar criar uma lista com elementos de tipos diferentes resulta em erro:

Prelude> let mix = [True, "bonjour"]

<interactive>:1:20: error:
    * Couldn't match expected type `Bool' with actual type `[Char]'
    * In the expression: "bonjour"
      In the expression: [True, "bonjour"]
      In an equation for `mix': mix = [True, "bonjour"]

Criando listas

Além de especificar a lista completa num único comando, de uma vez só, podemos criá-la dado por dado usando (:), chamado de cons. Este termo vem da linguagem de programação LISP, que cunharam o termo em inglês "to cons", uma abreviação de "to construct", e que se refere especificamente ao processo de adicionar um elemento ao início de uma lista.

Prelude> let numeros = [1,2,3,4]
Prelude> numeros
[1,2,3,4]
Prelude> 0:numeros
[0,1,2,3,4]

Quando se usa adicionar um elemento a uma lista usando (:), temos uma nova lista como resultado. Esse operador avalia o primeiro elemento a sua esquerda, e toda a expressão a sua direita. Por isso, é possível usá-lo indefinidamente.

Prelude> 1:0:numeros
[1,0,1,2,3,4]
Prelude> 2:1:0:numeros
[2,1,0,1,2,3,4]
Prelude> 5:4:3:2:1:0:numeros
[5,4,3,2,1,0,1,2,3,4]

Na verdade, todas as listas em Haskell são construída desta forma, sendo que o último elemento adicionado é uma lista vazia, representada por []. A notação de usar colchete trata-se de um açúcar sintático. Isso quer dizer que [1,2,3,4] é exatamente a mesma coisa que 1:2:3:4:[]. Entretanto, visualizar a ordem reversa da avaliação desse açúcar sintático ajuda a entender o que acontece:

1 : 2 : 3 : 4 : []
1 : (2 : (3 : (4 : [])))
1 : (2 : (3 : [4]))
1 : (2 : [3,4])
1 : [2,3,4]
[1,2,3,4]

Aqui podemos ver que cons é um operador com associatividade-à-direita.

Observe que True:False:[] é uma expressão válida, enquanto que True:False não é.

Prelude> True:False

<interactive>:1:6: error:
    * Couldn't match expected type `[Bool]' with actual type `Bool'
    * In the second argument of `(:)', namely `False'
      In the expression: True : False
      In an equation for `it': it = True : False

Novamente, temos um erro de incompatibilidade de tipos. Ele nos diz que (:) (que é uma função, como quase tudo em Haskell), esperava que seu segundo argumento, o do lado direito, fosse uma lista (exptected type [Bool]), quando na verdade False não o é (actual type `Bool').

Lembre-se:

• Todos os elementos de uma lista deve ser do mesmo tipo.
• Só de pode usar cons para adicionar um elemento a uma lista. Para formar uma lista, deve-se adicionar um elemento a uma lista vazia. Isso quer dizer que os argumentos à esquerda devem sempre ser elementos, e à direita, listas.

Exercício

1. 3:[True,False] é um código válido em Haskell? Por quê?
2. Escreva uma função chamada cons8 que recebe uma lista como argumento e adicionar 8 ao seu início. Teste os seguintes exemplos:
   1. cons8 []
   2. cons8 [1,2,3]
   3. cons8 [True,False]
   4. let foo = cons8 [1,2,3]
cons8 foo
3. Adapte cons8 para que ela adicione 8 ao fim da lista. (Dica: lembre-se que usamos (++) para concatenar duas listas de caracteres anteriormente.)
4. Escreva uma função de dois argumentos, uma lista e um elemento, e que adicionar o elemento à lista. Comece com:

let meuCons lista elemento =

Strings são listas

Como mencionamos em Tipos básicos, em Haskell, strings são listas de caracteres. Isso significa que o tipo String pode ser manipulado como qualquer outra lista de outros tipos. Por exemplo, em vez de definir uma lista com uma sequência de caracteres usando aspas duplas, podemos usar a notação de lista, ou (:):

Prelude>"ola" == ['o','l','a']
True
Prelude>"ola" == 'o':'l':'a':[]
True

Novamente, aspas duplas trata-se de outro açúcar sintático.

Lista de listas

Listas podem ser criadas a partir de qualquer tipo de dado, desde que todos os elementos sejam do mesmo tipo. Isso quer dizer que podemos criar uma lista cujos elementos são outras listas. Tente o seguinte no GHCi:

Prelude> let listaDeListas = [[1,2],[3,4],[5,6]]
Prelude> listaDeListas
[[1,2],[3,4],[5,6]]

Como uma lista é um valor por si só, é importante lembrar que este valor não é do mesmo tipo que os elementos que formam a lista: o tipo [Int] não é o mesmo que Int. Os próximos exercícios podem te ajudar a entender melhor esta observação.

Exercícios

Quais das seguintes linhas são códigos válidos e quais não são? Reescreva-as usando a notação de cons. [1,2,3,[]] [1,[2,3],4] [[1,2,3],[]] Quais das seguintes linhas são códigos válidos e quais não são? Reescreva-as usando a notação de colchetes. []:[[1,2,3],[4,5,6]] []:[] []:[]:[] [1]:[]:[] ["hi"]:[1]:[] Em Haskell, é possível termos uma lista de listas de listas? Por quê? Diga por que este código é inválido: [[1,2],3,[4,5]]

Listas de elementos de diferentes tipos não podem ser criadas, mas uma lista vazia pode ser adicionada a uma lista de qualquer tipo. Por exemplo, []:[[1, 2], [1, 2, 3]] é válido e retorna [[], [1, 2], [1, 2, 3]], e [1]:[[1, 2], [1, 2, 3]] é valido e produz [[1], [1, 2], [1, 2, 3]]. Entretanto, ['a']:[[1, 2], [1, 2, 3]] retorna um erro.

Listas nos permitem expressar vários tipos de dados mais complexos (matrizes bidimensionais, por exemplo). Elas também se favorecem bastante do sistema de tipos de Haskell. É bastante comum que um programador de Haskell se confunda trabalhando com listas de listas, mesmo os mais experientes. Portanto, a checagem de tipos sempre ajuda durante o desenvolvimento de uma aplicação.

N-uplas

Uma n-upla, assim como uma lista, é uma outra solução para armazenar vários dados num único dado. Entretanto, elas diferem entre si em dois pontos importantes:

• N-uplas tem tamanho fixo. Não se pode adicionar ou eliminar nada de uma n-upla. Portanto, só faz sentido usá-las quando se sabe a quantidade de valores que será armazenada. Por exemplo, se quisermos armazenar uma coordenada 2D, já sabemos que sempre teremos dois valores (x e y) e, por isso, podemos usar uma dupla.

• Os elementos de uma n-upla não precisam ser do mesmo tipo. Por exemplo, numa agenda de telefone, poderíamos armazenar três dados num único valor: nome, número de telefone e quantidade de ligações recebidas daquele contato. Neste caso, os três dados não são do mesmo tipo (dois strings e um número, ou um string e dois números, por exemplo), e por isso podemos usar uma tripla.

N-uplas são delimitadas por parênteses, e cada elemento é separado por uma vírgula. Veja:

(True, 1)
("Ola, mundo", False)
(4, 5, "Seis", True, 'b')

Tente execudar cada linha no GHCi. Perceba que nenhum erro é retornado. Se trocarmos os parênteses por colchetes, isto é, tentarmos criar listas, em vez de n-uplas, teremos erros de tipo.

O primeiro exemplo é uma dupla: True e 1. O segundo, outra dupla: "Ola, mundo" e False. O último é uma quíntupla contendo dois números, um string e um caractere: 4, 5, "Seis", True e 'b', respectivamente.

Com o tempo você verá que n-uplas maiores que 3, ou até 4, são bastante incomuns, mas, por hora, nos basta saber que podemos criar uma n-upla do tamanho que quisermos e precisarmos.

Exercícios

Escreva uma tripla cujo primeiro valor seja 4, o segundo seja "ola", e o terceiro seja True. Quais dos seguntes são n-uplas válidas? (4, 4) (4, "ola") (True, "bla", "foo") () Listas podem ser criadas ao se adicionar um novo elemento a uma outra lista. Entretanto, não existe uma operação similar para manipular n-uplas. Qual o motivo disto? Suponha que haja, sim, uma operação semelhante. O que você teria ao "adicionar" um elemento a uma n-upla?

N-uplas são úteis quando queremos queremos ter mais de um valor como saída de uma função. Em muitas outras linguagens, quando precisamos fazer isso, geralmente é preciso embrulhar os valores num novo tipo de dado, e que geralmente só será usado por aquela determinada função. Em Haskell, as n-uplas são uma generalização bastante simples deste procedimento.

N-uplas dentro de n-uplas e outras combinações

Podemos usar a mesma lógica de "lista de listas" com as n-uplas. Elas também são valores por si só, o que torna possível colocá-las dentro de outras n-uplas, em quantos níveis quisermos. Também podemos ter listad de n-uplas, n-uplas de listas, ou qualquer outra combinação.

((2,3), True)
((2,3), [2,3])
[(1,2), (3,4), (5,6)]

O tipo de uma n-uplas é definido pelo seu tamanho e pelos tipos de cada elemento nela contido. Por exemplo, ("Ola",32) e (47,"mundo") são diferentes. Uma é do tipo (String,Int), e a outra é do tipo (Int,String). Isso implica em restrições para criamos uma lista de n-uplas: [("a",1),("b",9),("c",9)] é uma lista válida, mas [("a",1),(2,"b"),(9,"c")] não é.

Exercícios
Quais das seguintes linhas de código são válidas em Haskell? Por quê? 1:(2,3) (2,4):(2,3) (2,4):[] [(2,4),(5,5),('a','b')] ([2,4],[2,2])

Recuperando valores

Estas estruturas só são úteis, obviamente, se pudermos acessar algum valor específico nelas contido. É isso que veremos agora.

Começando por duplas, ou pares ordenados (x,y). Imagine que você quer se referir a uma casa específica num tabuleiro de xadrez. Podemos enumerar as linhas e colunas com números de 1 a 8. Assim, o par (2,5) representa a casa na coluna 2, e na linha 5. Agora, queremos uma função para encontrar todas as peças posicionadas em certa coluna. Podemos começar olhando para as coordenadas de todas as peças, e depois examinamos a parte da coluna para saber se é igual ou não a que estamos procurando. Dado um par de coordenadas (x,y) de uma certa peça, nossa função deve extrair o x (a coordenada da coluna). Para isso, temos duas funções nativas: fst e snd Elas retornam o primeiro e segundo dado do par, respectivamente. Vejamos:

Prelude> fst (2, 5)
2
Prelude> fst (True, "boo")
True
Prelude> snd (5, "ola")
"ola"

Perceba que, por definição, ambas funções funcionam apenas com duplas.

No caso de uma lista, as funções head e tail quase equivalentes a fst e snd. Elas "desmontam" uma lista em duas partes: o primeiro e o segundo argumento de (:). Enquanto head retorna o primeiro elemento de uma lista, tail retorna o restante da lista.

Prelude> 2:[7,5,0]
[2,7,5,0]
Prelude> head [2,7,5,0]
2
Prelude> tail [2,7,5,0]
[7,5,0]

Nota: head e tail são potencialmente perigosas. Não podemos aplicá-la a listas vazias, isto é, []. Faça o teste no GHCi: aplique ambas sucessivamente a uma lista até chegar perto ao final dela. Você receberá uma mensagem de erro. Se fosse uma aplicação real, ela teria sido interrompida. Entretanto, temos vários jeitos de lidar com o problema da lista vazia em Haskell. Chegaremos lá, mas, por hora, vamos nos ater ao básico.

Outros problemas

As quatro funções que apresentamos até agora, não resolvem completamente todos nossos problemas. Como lidamos com n-uplas que não sejam de dois elementos? E para listas, existe um jeito mais fácil acessar valores do ir separando o primeiro elemento? Por hora, deixaremos assim. Depois que tivermos o embasamento necessário, voltaremos a estes tópicos no capítulo sobre manipulação de listas. Apenas saiba que separar entre cabeça e cauda nos permitirá fazer o que quisermos.

Exercícios

Crie uma combinação de fst e snd para extrair o valor 4 da segunte n-upla: (("Ola", 4), True) A notação geralmente usada para representar um tabuleiro de xadrez é diferente da que usamos aqui: a linhas são enumeradas de 1 a 8, e as colunas são nomeadas de A a H, sendo que o nome das colunas vem primeiro. Mesmo assim, ainda seria possível criar uma dupla para representar uma casa específica, como ('A', 4), por exemplo? Qual importante diferença entre listas e n-uplas este caso ilustra? Escreva uma função que retorne a cabeça e a cauda de uma lista como sendo o primeiro e segundo elemento de uma dupla. Use head e tail para escrever uma função que retorne o quinto elemento de uma lista. A seguir, comente sobre ela, apontando incômodos e problemas que você tenha percebido.

Tipos polimórficos

O tipo de uma dista depende do tipo de seus elementos, e é representado por colchetes:

Prelude>:t [True, False]
[True, False] :: [Bool]
Prelude>:t ["ola", "oi"]
["ola", "oi"] :: [[Char]]

Uma lista de Bool é diferente de uma lista [Char] (que é o sinônimo de String), e como sabemos, pelos tipos das funções, cada um de seus argumentos já tem um tipo pré-determinado. Mas então, como é que a função head, por exemplo, pode funcionar tanto com [Bool], quanto com [Int], ou quanto com [String]? Se pensarmos nesta restrição dos argumentos, deveríamos ter uma headBool :: [Bool] -> Bool, outra headInt :: [Int] -> Int, e assim por diante. Só que isto seria um grande problema, e não faria nenhum sentido. Afinal de contas, listas são montadas da mesma maneira, independente do tipo de seus valores. Portanto, faz bem mais sentido que elas sejam desmontadas de forma semelhante, sem depender do tipo.

Vejamaos no GHCi:

Prelude> head [True, False]
True
Prelude> head ["ola", "oi"]
"ola"

Agora procure ver a assinatura de tipo de head usando o comando :t:

Prelude>:t head
head :: [a] -> a

O a que aparece na assinatura, não é um tipo. Lembre-se que o nome dos tipos sempre começam com letra maiúscula em Haskell. Neste caso, a é uma variável de tipo. Quando uma função possui uma assinatura contendo variáveis, isso quer dizer que ela permite que qualquer tipo seja usado. É o que chamamos de polimorfismo: funções ou valores que são definidos com tendo um único tipo, são chamados de monomórficos, enquanto que ao usarmos uma variável de tipo, criamos funções ou valores polimórficos. A assinatura de head, por exemplo, nos diz que ela aceita uma lista ([a]) cujos valores podem ser de qualquer tipo a, e retorna um valor do mesmo tipo a.

Perceba que dentro de uma mesma anotação de tipo, todas as ocorrências de uma mesma variável de tipo devem ter o mesmo nome. Por exemplo:

f :: a -> a

significa que f recebe um argumento de qualquer tipo a, retorna um resultado do mesmo tipo a, enquanto que

f :: a -> b

significa que f recebe um argumento de qualquer tipo a, e retorna um argumento de qualquer tipo b, que pode ou não ser o mesmo que a. Usar variáveis diferentes não quer dizer que os tipos devem ser diferentes, mas sim que eles podem ou não ser diferentes.

Exemplo: fst e snd

Como vimos, fst e snd são funções para extrair valores de duplas. A esta altura, é desejável que você já tenha o hábito de se perguntar qual o tipo das funções que aparecem por aqui. Vamos analisar estas funções funções. Assim como as listas, o tipo de uma n-upla depende do tipo de seus elementos. Portanto, fst e snd devem ser polimórficas para funcionar com qualquer dupla. Também temos que lembrar que o tipo da própria n-upla não precisa ser homogênea, isto é, todos os elementos não necessariamente precisam ser do mesmo tipo. Se fosse este o caso, então

fst :: (a, a) -> a

só funcionaria com duplas (x,y) em que x e y tivessem o mesmo tipo. O mesmo para snd. Entretanto, ambas as funções são definidas como sendo:

fst :: (a,b) -> a
snd :: (a,b) -> b

Mesmo sem saber o funcionamento de fst e snd, só de ver seus tipos você já poderia suspeitar que fst realiza alguma operação em relação ao primeiro elemento de uma dupla, enquanto que snd opera sobre o segundo elemento.

Exercícios

Sugira uma assinatura de tipo para as seguintes funções: A solução do terceiro exercício da seção anterior: "uma função que retorne a cabeça e a cauda de uma lista como sendo o primeiro e segundo elemento de uma dupla". A solução do quarto exercício da seção anterior: "uma função que retorne o quinto elemento de uma lista". h x y z = chr (x - 2) (lembre-se que discutimos sobre chr no capítulo anteior).

Resumo

Este capítulo discutiu sobre listas e n-uplas. As principais semelhanças e diferenças entre elas são:

1. Listas são definidas usando-se colchetes e vírgulas: [1,2,3].
   • Listas podem conter qualquer coisa, desde que todas essas coisas sejam do mesmo tipo.
   • Listas também podem ser criadas usando o operador cons, (:), que adiciona um elemento a uma lista.
2. N-uplas são definidas usando-se parênteses e vírgulas: ("Joao",32).
   • N-uplas podem contar qualquer coisa, sendo que elas não precisam ser do mesmo tipo.
   • O tamanho de uma n-upla já está definido em seu tipo; n-uplas de diferentes tamanho terão tipos diferentes.
3. Listas e n-uplas podem ser combinadas de várias maneiras (listas dentro de n-uplas, n-uplas de listas etc.), mas a restrições de tipos de cada uma destas estruturas ainda devem ser atendidas.