[Haskell Aula 01] Listas

Aula 01 -> LISTAS

Bom, ja sabemos declarar uma lista em Haskell.

Sabemos inicializar ela do jeito "fácil" trivial...

Ok...

Então pra que servirá essa aula?

Listas em Haskell são mais complexas (e úteis) do que parecem.

Como aprendemos no primário ensino médio, conjuntos matemáticos podem ser defindos por extensão e por compreensão.

Com as listas em Haskell acontece exatamente a mesma coisa.

Extensão:

Matemática:

Sejam A e B conjuntos.
A = {1,2,3,4,5,6}
B = {}
Haskell:

A :: [Int]
A = [1,2,3,4,5,6]

B :: [a]
B = []

Parecido, não?

E quando a lista é uma progressão aritmética é fácil defini-la em Haskell.

Olhem:

[1..10] == [1,2,3,4,5,6,7,8,9,10]
[1,3..10] == [1,3,5,7,9]
[1..] == [1,2,3,4,5,6, ... ,44523455, 44523456, 44523457, ...... ] //Em haskell podemos definir listas infinitas!

Compreensão:

Muitas vezes não é possível definir conjuntos por extensão, muitos conjuntos são infinitos.

Por exemplo, dado um número x, vamos definir o conjunto de todos os números naturais maiores do que x.

Matemática:

Seja A um conjunto e x um natural.
A = {a E N : a > x }
(nota: Entendam o 'E' como 'pertence a' e 'N' é o conjunto dos números naturais)

Vamos então definir essa lista em Haskell.

Imaginem que n seja uma outra lista.

A :: [Int]
A = [ a | a <- n, a > x]
Vamos fazer uma comparação da sintaxe utilizada nos dois casos:

Matemática: {elemento E conjunto gerador : condição }

Haskell: [ elemento | elemento <- conjunto gerador , condição ]

O operador '<-' pode ser lido como: "Vem de".

Então, no exemplo "a <- n" podemos ler como "a vem de n"

Ta certo, ja sabemos definir listas, mas mal sabemos como utilizá-las...

Quando comecei a aprender Haskell, a minha maior dificuldade foi entender como eu iria percorrer uma lista sem utilizar loops.

A resposta é recursão!

Por uma definição informal podemos dizer que recursão é algo que utiliza a si próprio para ser definido.

Um exemplo é a sequencia de fibonacci.

fib 1 = 1
fib 2 = 1
fib n = (fib (n-1)) + (fib (n-2))

E notem que recursão só faz sentido em matemática e deve seguir algumas regras que veremos em mais detalhes mais à frente.

Mas imaginem uma recursão fora do contexto matemático, por exemplo:

vocês pegam numa receita de bolo e la está escrito:

>
Ingredientes:

bolo de chocolate

ovos

farinha

...

Bom, vamos voltar às listas.

Existem alguns operadores para listas que tornam a nossa vida muito mais fácil, como, por exemplo o ':'.

Que insere um elemento no início de uma lista.

Por exemplo:

4:[1,2,3] == [4,1,2,3]
Podemos definir uma lista utilizando apenas o operador ':'

1:2:3:4:5:6:[] == [1,2,3,4,5,6]
A assinatura do operador ':' é

(:) :: a -> [a] -> [a]
Onde a é um tipo arbitrário, isto é, pode ser qualquer tipo.

Outro operador que é vastamente utilizado é o '++', que concatena duas listas.

[1,2] ++ [3,4] == [1,2,3,4]ATENÇÃO:

[1,2] ++ 3ERRADO!!!O operador '++' recebe duas listas, o correto seria:

[1,2] ++ [3]
EXERCÍCIOS:

(1)

Defina as seguintes listas por compreensão:

a)

[0,2,4,6,8,10]b ) Os múltiplos de 2 e 3 entre 0 e 20.c)

[[1], [1,1], [1,1,1], [1,1,1,1], [1,1,1,1,1]]
NOTA:

Na aula 0 e nessa aula eu apresentei algumas assinaturas de funções, essas assinaturas estão ERRADAS!

Servem apenas para exemplificar e muitas delas nem compilarão.

Mais pra frente vamos descobrir o porquê estão erradas e como deixá-las da forma correta.

Bom, por enquanto é tudo o que precisamos saber sobre listas para a aula da semana seguinte.

Abraços!

http://forum.imasters.com.br/public/style_emoticons/default/thumbsup.gif