09-listas

Prévia do material em texto

1/100
Programação Funcional
Capítulo 9
Listas
José Romildo Malaquias
Departamento de Computação
Universidade Federal de Ouro Preto
2013.1
2/100
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
3/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
4/100
Listas
Lista é uma seqüência de elementos de um mesmo tipo.
[a] é o tipo das listas cujos elementos são do tipo a
Estruturalmente a forma de uma lista pode ser:
lista vazia
I nenhum elemento na seqüência
I construtor de dado: (constante)
[] :: [a]
lista não vazia
I formada por dois componentes:
cabeça: o primeiro elemento da lista
cauda: lista de todos os demais elementos, a partir do segundo
I construtor de dado: (dois argumentos)
infixr 5 :(:) :: a -> [a] -> [a]
O primeiro argumento é a cabeça da lista.
O segundo argumento é a cauda da lista.
5/100
Exemplos de listas
[]
seqüência vazia (nenhum elemento)
não tem cabeça e nem cauda
tipo: [a]
é um valor polimórfico, pois pertence a todos os tipos lista
6/100
Exemplos de listas (cont.)
False : []
seqüência: False
cabeça: False
cauda: []
tipo: [Bool]
7/100
Exemplos de listas (cont.)
’a’ : (’b’ : [])
seqüência: ’a’, ’b’
cabeça: ’a’
cauda: ’b’ : []
tipo: [Char]
8/100
Exemplos de listas (cont.)
15 : (9 : (42 : []))
seqüência: 15, 9, 42
cabeça: 15
cauda: 9 : (42 : [])
tipo: Num a => [a]
9/100
Exemplos de listas (cont.)
15 : (9.45 : (15 : (0 : [])))
seqüência: 15, 9.45, 15, 0
cabeça: 15
cauda: 9.45 : (15 : (0 : []))
tipo: Fractional a => [a]
10/100
Exemplos de listas (cont.)
15 : (’H’ : (False : []))
não é uma expressão válida, uma vez que todos os elementos de uma lista devem ser
de um mesmo tipo.
11/100
Notações de listas
O construtor constante [] denota a lista vazia.
O construtor : constrói uma lista não vazia a partir da cabeça e da cauda.
: é um operador binário infixo com precedência 5 e associatividade à direita.
Isto significa que os parênteses no segundo argumento geralmente são
desnecessários.
Exemplo: o valor
100 : 200 : 300 : 400 : []
é idêntido a
100 : (200 : (300 : (400 : [])))
12/100
Notações de listas (cont.)
Uma lista finita pode ser denotada escrevendo os seus elementos entre colchetes
e separados por vírgula:
[ exp1, ..., expn ]
Esta é uma notação simplificada para listas finitas, sendo equivalente a
exp1 : ... : expn : []
13/100
Notações de listas (cont.)
Exemplo:
A lista de 6 números
[10, 20, 30, 40, 50, 60]
é apenas uma abreviação sintática para
10 : 20 : 30 : 40 : 50 : 60 : []
14/100
Notações de listas (cont.)
Exemplo:
A lista
[[]]
que é uma abreviação para
[] : []
é a lista unitária cujo único elemento é a lista vazia. O seu tipo é [[a]].
15/100
Exercícios
Exercício 1
Dê um exemplo de uma expressão que contenha duas ocorrências da lista vazia,
sendo a primeira ocorrência do tipo [Bool] e a segunda do tipo [Char].
16/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
17/100
Strings
Em Haskell strings (cadeias de caracteres) são simplesmente listas de
caracteres.
O tipo String é um sinônimo para [Char] .
Existe uma notação especial para constantes strings: a seqüência de caracteres
é escrita entre aspas " .
Exemplos:
A string "UFOP" é apenas uma sintaxe conveniente para a lista de caracteres
[’U’,’F’,’O’,’P’]
A string vazia "" é o mesmo que [], a lista vazia, do tipo [Char].
18/100
Strings (cont.)
Códigos de escape podem ser usados em constantes caracter e constantes
strings para representar alguns caracteres.
Exemplos:
’\n’
’\\’
"bom\ndia\nbrasil"
"abcd\tEFG"
"\"aspas\" dentro da string"
"tabulador:\tou\^Iou\9."
19/100
Strings (cont.)
Códigos de escape de 1 caracter:
Escape Unicode Character
\0 U+0000 null character
\a U+0007 alert
\b U+0008 backspace
\f U+000C form feed
\n U+000A newline (line feed)
\r U+000D carriage return
\t U+0009 horizontal tab
\v U+000B vertical tab
\" U+0022 double quote
\& n/a no character
\’ U+0027 single quote
\\ U+005C backslash
20/100
Strings (cont.)
Códigos de controle:
Escape Escape Unicode Meaning
\NUL \^@ U+0000 null character
\SOH \^A U+0001 start of heading
\STX \^B U+0002 start of text
\ETX \^C U+0003 end of text
\EOT \^D U+0004 end of transmission
\ENQ \^E U+0005 enquiry
\ACK \^F U+0006 acknowledge
\BEL \^G U+0007 bell
\BS \^H U+0008 backspace
\HT \^I U+0009 horizontal tab
\LF \^J U+000A line feed (newline)
\VT \^K U+000B vertical tab
\FF \^L U+000C form feed
\CR \^M U+000D carriage return
\SO \^N U+000E shift out
\SI \^O U+000F shift in
21/100
Strings (cont.)
\DLE \^P U+0010 data link escape
\DC1 \^Q U+0011 device control 1
\DC2 \^R U+0012 device control 2
\DC3 \^S U+0013 device control 3
\DC4 \^T U+0014 device control 4
\NAK \^U U+0015 negative acknowledge
\SYN \^V U+0016 synchronous idle
\ETB \^W U+0017 end of transmission block
\CAN \^X U+0018 cancel
\EM \^Y U+0019 end of medium
\SUB \^Z U+001A substitute
\ESC \^[ U+001B escape
\FS \^\ U+001C file separator
\GS \^] U+001D group separator
\RS \^^ U+001E record separator
\US \^_ U+001F unit separator
\SP U+0020 space
\DEL U+007F delete
22/100
Strings (cont.)
Códigos de escape numéricos:
\decimal código decimal
\o octal código octal
\x hexa código hexadecimal
Exemplos:
\1234
\xbeef
\o1234
O valor numérico máximo é \1114111, que também pode ser escrito \x10ffff ou
\o4177777.
23/100
Strings (cont.)
Seqüência de escape vazia:
\&
Literais string podem conter a seqüência de escape vazia, escrita \&.
Ela não é um caracter real, mas serve para separar uma seqüência de escape
numérica de um dígito decimal que vem logo em seguida.
Exemplo:
A string "\130\&12" é formada pelos caracteres ’\130’, ’1’ e ’2’.
Já a string "\13012" é formada apenas pelo caracter ’\13012’.
24/100
Strings (cont.)
Seqüência de escape gap:
\brancos\
Esta seqüência pode aparecer em literais strings.
É formada por uma seqüência de caracteres brancos (espaços, mudanças de linha,
tabulações, ...) delimitada pelo caracter \.
Ela não reprsenta nenhum caracter e é ignorada.
É útil para escrever um literal string em várias linhas.
Exemplo: A string
"uma longa \
\string, escrita\
\ em muitas linhas"
é a idêntica a
"uma longa string, escrita em muitas linhas"
25/100
Instância de classes
Tipos listas são instâncias de várias classes:
instance Eq a => Eq [a]instance Ord a => Ord [a]instance Read a => Read [a]instance Show a => Show [a]
Duas listas são iguais se e somente se os seus elementos correspondentes são
iguais.
A comparação de listas é lexicográfica (da mesma maneira que palavras são
organizadas em um dicionário).
26/100
Instância de classes (cont.)
Exemplos:
[1,2,3,4,5] == [1,2,3,4,5] True
[1,2] == [1,2,3] False
"Maria" /= "maria" True
"elegante" <= "elefante" False
[1,2,3] > [1,2] True
compare "Abracadabra" "Zebra" LT
show [1,2,3,4] "[1,2,3,4]"
show "Bom dia!" "\"Bom dia!\""
read "[6,0,32]" :: [Int] [6,0,32]
read "[’f’,’i’,’m’]" :: String "fim"
read "\"fim\"" :: String "fim"
27/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
28/100
Seqüências aritméticas
Haskell tem uma sintaxe especial para seqüências aritméticas.
29/100
Seqüênciasaritméticas (cont.)
[ exp1, exp2 .. exp3 ]
É a seqüência aritmética que começa com exp1, continua com exp2 e cujos
elementos não ultrapassam exp3.
Para tipos numéricos, a razão da progressão é exp2−exp1.
Exemplos:
[4,6..14] [4,6,8,10,12,14]
[5,10..44] [5,10,15,20,25,30,35,40]
[18,15..0] [18,15,12,9,6,3,0]
[4.0,4.4..5.2] [4.0,4.4,4.800000000000001,5.200000000000001]
[’m’,’o’..’x’] "moqsuw"
[’0’,’2’..’9’] "02468"
[’m’,’o’..’a’] ""
30/100
Seqüências aritméticas (cont.)
[ exp1 .. exp2 ]
É a seqüência aritmética que começa com exp1 e cujos elementos não
ultrapassam exp2.
Para tipos numéricos, a razão da progressão é 1.
Exemplos:
[5..10] [5,6,7,8,9,10]
[7..19] [7,8,9,10,11,12,13,14,15,16,17,18,19]
[7..5] []
[’M’..’P’] "MNOP"
[False .. True] [False,True]
31/100
Seqüências aritméticas (cont.)
[ exp1, exp2 .. ]
É a seqüência aritmética que começa com exp1 e cujo segundo elemento é exp2.
Para tipos numéricos, a razão da progressão é exp2−exp1.
Pode ser infinita.
Exemplos:
[5,7..] [5,7,9,11,13,15,17,... -- (seqüência infinita)
[0,6..] [0,6,12,18,24,30,36,... -- (seqüência infinita)
[7,2..] [7,2,-3,-8,-13,-18,... -- (seqüência infinita)
[9,9..] [9,9,9,9,9,9,9,9,9,... -- (seqüência infinita)
32/100
Seqüências aritméticas (cont.)
[ exp1 .. ]
É a seqüência aritmética que começa com exp1.
Para tipos numéricos, a razão da progressão é 1.
Pode ser infinita.
Exemplos:
[5 ..] [5,6,7,8,9,10,11,12,13,... -- (seqüência infinita)
[3 ..] [3,4,5,6,7,8,9,10,11,12,... -- (seqüência infinita)
[1.1 ..] [1.1,2.1,3.1,4.1,5.1,6.1,... -- (seqüência infinita)
[LT ..] [LT,EQ,GT]
[5..] :: (Enum a, Num a) => [a]
[’B’..] :: [Char]
33/100
Seqüências aritméticas (cont.)
A notação de lista para seqüências aritméticas é simplesmente uma abreviação
sintática para aplicações de métodos da classe Enum:
[ a, b .. c ] ≡ enumFromThenTo a b c
[ a .. b ] ≡ enumFromTo a b
[ a, b .. ] ≡ enumFromThen a b
[ a .. ] ≡ enumFrom a
Exemplo:
[10,15..44] [10,15,20,25,30,35,40]
enumFromThenTo 10 15 44 [10,15,20,25,30,35,40]
Portanto seqüências aritméticas só podem ser usadas para listas de elementos
de um tipo que seja instância da classe Enum.
34/100
Seqüências aritméticas (cont.)
A classe Enum:
class Enum a where
succ :: a -> a
pred :: a -> a
toEnum :: Int -> a
fromEnum :: a -> Int
enumFrom :: a -> [a]
enumFromThen :: a -> a -> [a]
enumFromTo :: a -> a -> [a]
enumFromThenTo :: a -> a -> a -> [a]
instance Enum Intinstance Enum Integerinstance Enum Floatinstance Enum Doubleinstance Enum Charinstance Enum Boolinstance Enum Orderinginstance Enum ()
35/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
36/100
Casamento de padrão com listas
Casamento de padrão é a operação básica de Haskell para decompor valores
estruturados.
Para cada construtor de dados existe uma forma de padrão correspondente.
37/100
Casamento de padrão com listas (cont.)
Estruturalmente uma lista pode ser vazia ou não vazia:
padrão lista vazia
[]
I é um padrão constante
I o casamento sucede se e somente se o valor for a lista vazia
padrão lista não vazia
pad1 : pad2
I é formado por dois padrões pad1 e pad2
I o casamento sucede se e somente se o valor for uma lista não vazia cuja cabeça casa
com pad1 e cuja cauda casa com pad2
38/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão [] casa somente com a lista vazia.
padrão valor casamento variáveis
[] [] sucede[] [1,2,3] falha
39/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão x:xs casa com qualquer lista não vazia, associando as variáveis x exs com a cabeça e a cauda da lista, respectivamente.
padrão valor casamento variáveis
x:xs [] falha
x:xs [1,2,3] sucede x 7→ 1, xs 7→ [2,3]
x:xs [’A’] sucede x 7→ ’A’, xs 7→ []
40/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão x:y:_ casa com qualquer lista que tenha pelo menos dois elementos,
associando as variáveis x e y ao primeiro e segundo elementos da lista,
respectivamente.
padrão valor casamento variáveis
x:y:_ [] falha
x:y:_ ["ana"] falha
x:y:_ [1,2] sucede x 7→ 1, y 7→ 2
x:y:_ [1,2,3] sucede x 7→ 1, y 7→ 2
41/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão x:_:z:[] casa com qualquer lista que tenha exatamente três
elementos, associando as variáveis x e z ao primeiro e terceiro elementos da
lista, respectivamente.
padrão valor casamento variáveis
x:_:z:[] [] falha
x:_:z:[] ["ana"] falha
x:_:z:[] [1,2,3] sucede x 7→ 1, z 7→ 3
x:_:z:[] [1,2,3,4,5] falha
42/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão 0:a:_ casa com qualquer lista de números que tenha pelo menos
dois elementos, sendo o primeiro igual a zero, associando a variável a ao
segundo elemento da lista.
padrão valor casamento variáveis
0:a:_ [] falha
0:a:_ [0] falha
0:a:_ [0,2,3] sucede a 7→ 2
0:a:_ [0,10,6,3] sucede a 7→ 10
0:a:_ [7,0,8] falha
43/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão (m,_):_ casa com qualquer lista não vazia de pares, associando a
variável m ao primeiro componente do par que é o primeiro elemento da lista.
padrão valor casamento variáveis
(m,_):_ [] falha
(m,_):_ [("fim",True)] sucede m 7→ "fim"
(m,_):_ [(10,’M’),(20,’F’)] sucede m 7→ 10
44/100
Casamento de padrão com listas (cont.)
A forma
[ padrao1, . . ., padraon ]
é uma abreviação sintática para
padrao1 : . . . : padraon : []
cujo casamento sucede somente se a lista tiver exatamente n elementos.
45/100
Casamento de padrão com listas (cont.)
Exemplo:
O padrão [1,alfa] casa com qualquer lista de dois números que começa com1, associando a variável alfa ao segundo elemento da lista.
padrão valor casamento variáveis
[1,alfa] [] falha
[1,alfa] [1] falha
[1,alfa] [1,5] sucede alfa 7→ 5
[1,alfa] [9,5] falha
[1,alfa] [1,2,3] falha
46/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case tail [10] of[] -> "vazia"_ -> "nao vazia"
resulta em "vazia", pois o valor da expressão tail [10] casa com o padrão
para lista vazia [].
47/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case [10,20,30,40] of[] -> "lista vazia"
x:xs -> "cabeca: " ++ show x ++ " cauda: " ++ show xs
resulta em "cabeca: 10 cauda: [20,30,40]", pois a lista [10,20,30,40]
casa com o padrão para lista não vazia x:xs, associando x com 10 e xs com
[20,30,40].
48/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case [10..20] of
x:y:z:_ -> x + y + z_ -> 0
resulta em 33, pois a lista [10..20] casa com o padrão x:y:z:_, associando x
com 10, y com 11 e z com 12.
49/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case [10,20] of
x:y:z:_ -> x + y + z_ -> 0
resulta em 0, pois a lista [10,20] não casa com o primeiro padrão x:y:z:_, mas
casa com o segundo _.
Observe que o primeiro padrão casa somente com listas que tenham pelo menos
três elementos.
50/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case [10,20,30] of
[x1,_,x3] -> x1 + x3_ -> 0
resulta em 40, pois a lista [10,20,30] casa com o primeiro padrão [x1,_,x3].
Observe que este padrão casa somente com listas que tenham exatamente três
elementos.
51/100
Casamento de padrão com listas (cont.)
Exemplo:
A expressão
case [100,20,3] of
a:b:xs | a > b -> b:a:xs
| a = b -> a:xs
xs -> xs
resulta em [20,100,3], pois a lista [100,20,3] casa com o primeiro padrão
a:b:xs e o primeiro elemento é maior do que o segundo.
52/100
Exercícios
Exercício 2
Defina uma função usando casamento de padrão que retorna o sucessor do primeiro
elemento de uma lista, se houver, e zero caso contrário.
Exercício 3
Usando casamento de padrão, defina uma função que retorna a soma dos dois
primeiros elementos de uma lista se a lista tiver pelo menos dois elementos, a cabeça
da lista se ela contiver apenas um elemento, e zero caso contrário.Exercício 4
Resolva os exercícios 2 e 3 usando funções da biblioteca ao invés de casamento de
padrão.
53/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
54/100
Operações com listas
As listas são muito importantes na programação funcional.
Serão apresentadas as operações principais com listas.
55/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
56/100
Operações com listas: null
null retorna True se o seu argumento é a lista vazia ([]) e False caso contrário.
Exemplos:
null [] True
null [1,2,3,4,5] False
null "" True
null "FIM" False
Definição:
null :: [a] -> Bool
null [] = True
null _ = False
56/100
Operações com listas: null
null retorna True se o seu argumento é a lista vazia ([]) e False caso contrário.
Exemplos:
null [] True
null [1,2,3,4,5] False
null "" True
null "FIM" False
Definição:
null :: [a] -> Bool
null [] = True
null _ = False
57/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
58/100
Operações com listas: head
head seleciona o primeiro elemento de uma lista não vazia.
Exemplos:
head [10,20,30,40,50] 10
head "FIM" ’F’
head [] erro
head "" erro
Definição
head :: [a] -> a
head (x:_) = x
58/100
Operações com listas: head
head seleciona o primeiro elemento de uma lista não vazia.
Exemplos:
head [10,20,30,40,50] 10
head "FIM" ’F’
head [] erro
head "" erro
Definição
head :: [a] -> a
head (x:_) = x
59/100
Operações com listas: tail
tail seleciona a cauda de uma lista não vazia, isto é, todos os elementos exceto
o primeiro.
Exemplos:
tail [10,20,30,40,50] [20,30,40,50]
tail "Aroma" "roma"
tail [] erro
tail "" erro
Definição:
tail :: [a] -> a
tail (_:xs) = xs
59/100
Operações com listas: tail
tail seleciona a cauda de uma lista não vazia, isto é, todos os elementos exceto
o primeiro.
Exemplos:
tail [10,20,30,40,50] [20,30,40,50]
tail "Aroma" "roma"
tail [] erro
tail "" erro
Definição:
tail :: [a] -> a
tail (_:xs) = xs
60/100
Operações com listas: init
init seleciona todos os elementos de uma lista não vazia, exceto o último
elemento.
Exemplos:
init [15] []
init [True,False] [True]
init [1,2,3,4,5] [1,2,3,4]
init "Brasil" "Brasi"
init [] erro
Definição:
init :: [a] -> [a]
init [_] = []
init (x:xs) = x : init xs
60/100
Operações com listas: init
init seleciona todos os elementos de uma lista não vazia, exceto o último
elemento.
Exemplos:
init [15] []
init [True,False] [True]
init [1,2,3,4,5] [1,2,3,4]
init "Brasil" "Brasi"
init [] erro
Definição:
init :: [a] -> [a]
init [_] = []
init (x:xs) = x : init xs
61/100
Operações com listas: last
last seleciona o último elemento de uma lista não vazia.
Exemplos:
last [15] 15
last [True,False] False
last [1,2,3,4,5] 5
last "Brasil" ’l’
last [] erro
Definição:
last :: [a] -> a
last [x] = x
last (_:xs) = last xs
61/100
Operações com listas: last
last seleciona o último elemento de uma lista não vazia.
Exemplos:
last [15] 15
last [True,False] False
last [1,2,3,4,5] 5
last "Brasil" ’l’
last [] erro
Definição:
last :: [a] -> a
last [x] = x
last (_:xs) = last xs
62/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
63/100
Operações com listas: elem
elem recebe um valor e uma lista e retorna True se e somente se o valor é um
elemento da lista.
Exemplos:
elem 5 [] False
elem 5 [5] True
elem 5 [4,5] True
elem ’d’ "Pedro" True
8 ‘elem‘ [2,4,6,8,10] True
’#’ ‘elem‘ "Pedro" False
Definição:
infixl 4 ‘elem‘
elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
63/100
Operações com listas: elem
elem recebe um valor e uma lista e retorna True se e somente se o valor é um
elemento da lista.
Exemplos:
elem 5 [] False
elem 5 [5] True
elem 5 [4,5] True
elem ’d’ "Pedro" True
8 ‘elem‘ [2,4,6,8,10] True
’#’ ‘elem‘ "Pedro" False
Definição:
infixl 4 ‘elem‘
elem :: Eq a => a -> [a] -> Bool
elem _ [] = False
elem x (y:ys) = x == y || elem x ys
64/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
65/100
Operações com listas: length
length retorna o número de elementos de uma lista finita.
Exemplos:
length [] 0
length [15] 1
length [div 2 0, mod 3 0] 2
length [1,2,3,4,5] 5
length "Brasil" 6
Definição:
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
65/100
Operações com listas: length
length retorna o número de elementos de uma lista finita.
Exemplos:
length [] 0
length [15] 1
length [div 2 0, mod 3 0] 2
length [1,2,3,4,5] 5
length "Brasil" 6
Definição:
length :: [a] -> Int
length [] = 0
length (_:xs) = 1 + length xs
66/100
Operações com listas: (!!)
(!!) recebe uma lista e um número inteiro e retorna o elemento da lista cuja
posição é dada pelo número.
A posição do primeiro elemento é zero.
A posição do último elemento é o tamanho da lista menos um.
Se a posição for inválida ocorre um erro.
Exemplos:
[1,2,3,4,5] !! 0 1
[1,2,3,4,5] !! 1 2
"Brasil" !! 3 ’s’
[35,46] !! 8 erro
[35,46] !! (-2) erro
Definição
infixl 9 !!
(!!) :: [a] -> Int -> a
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
66/100
Operações com listas: (!!)
(!!) recebe uma lista e um número inteiro e retorna o elemento da lista cuja
posição é dada pelo número.
A posição do primeiro elemento é zero.
A posição do último elemento é o tamanho da lista menos um.
Se a posição for inválida ocorre um erro.
Exemplos:
[1,2,3,4,5] !! 0 1
[1,2,3,4,5] !! 1 2
"Brasil" !! 3 ’s’
[35,46] !! 8 erro
[35,46] !! (-2) erro
Definição
infixl 9 !!
(!!) :: [a] -> Int -> a
(x:_) !! 0 = x
(_:xs) !! n = xs !! (n-1)
67/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
68/100
Operações com listas: take
take recebe um número inteiro n e uma lista xs e retorna o prefixo de tamanho n
da lista xs.
Exemplos:
take 5 "Hello World!" "Hello"
take 3 [1,2,3,4,5] [1,2,3]
take 3 [1,2] [1,2]
take 3 [] []
take (-9) [1,2] []
take 0 [1,2] []
Definição
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
68/100
Operações com listas: take
take recebe um número inteiro n e uma lista xs e retorna o prefixo de tamanho n
da lista xs.
Exemplos:
take 5 "Hello World!" "Hello"
take 3 [1,2,3,4,5] [1,2,3]
take 3 [1,2] [1,2]
take 3 [] []
take (-9) [1,2] []
take 0 [1,2] []
Definição
take :: Int -> [a] -> [a]
take n _ | n <= 0 = []
take _ [] = []
take n (x:xs) = x : take (n-1) xs
69/100
Operações com listas: drop
drop recebe um número inteiro n e uma lista xs e retorna o sufixo da lista xs após
os n primeiros elementos.
Exemplos:
drop 6 "Hello World!" "World!"
drop 3 [1,2,3,4,5] [4,5]
drop 3 [1,2] []
drop 3 [][]
drop (-9) [1,2] [1,2]
drop 0 [1,2] [1,2]
Definição
drop :: Int -> [a] -> [a]
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
69/100
Operações com listas: drop
drop recebe um número inteiro n e uma lista xs e retorna o sufixo da lista xs após
os n primeiros elementos.
Exemplos:
drop 6 "Hello World!" "World!"
drop 3 [1,2,3,4,5] [4,5]
drop 3 [1,2] []
drop 3 [] []
drop (-9) [1,2] [1,2]
drop 0 [1,2] [1,2]
Definição
drop :: Int -> [a] -> [a]
drop n xs | n <= 0 = xs
drop _ [] = []
drop n (_:xs) = drop (n-1) xs
70/100
Operações com listas: splitAt
splitAt recebe um número inteiro n e uma lista xs e retorna um par onde o
primeiro elemento é um prefixo de tamanho n de xs e o segundo elemento é o
resto da lista.
Exemplos:
splitAt 6 "Hello World!" ("Hello ","World!")
splitAt 3 [1,2,3,4,5] ([1,2,3],[4,5])
splitAt 1 [1,2,3] ([1],[2,3])
splitAt 3 [1,2,3] ([1,2,3],[])
splitAt 4 [1,2,3] ([1,2,3],[])
splitAt 0 [1,2,3] ([],[1,2,3])
splitAt (-9) [1,2,3] ([],[1,2,3])
Definição
splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs | n <= 0 = ([],xs)
splitAt _ [] = ([],[])
splitAt n (x:xs) = (x:xs’,xs’’)where
(xs’,xs’’) = splitAt (n-1) xs
70/100
Operações com listas: splitAt
splitAt recebe um número inteiro n e uma lista xs e retorna um par onde o
primeiro elemento é um prefixo de tamanho n de xs e o segundo elemento é o
resto da lista.
Exemplos:
splitAt 6 "Hello World!" ("Hello ","World!")
splitAt 3 [1,2,3,4,5] ([1,2,3],[4,5])
splitAt 1 [1,2,3] ([1],[2,3])
splitAt 3 [1,2,3] ([1,2,3],[])
splitAt 4 [1,2,3] ([1,2,3],[])
splitAt 0 [1,2,3] ([],[1,2,3])
splitAt (-9) [1,2,3] ([],[1,2,3])
Definição
splitAt :: Int -> [a] -> ([a],[a])
splitAt n xs | n <= 0 = ([],xs)
splitAt _ [] = ([],[])
splitAt n (x:xs) = (x:xs’,xs’’)where
(xs’,xs’’) = splitAt (n-1) xs
71/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
72/100
Operações com listas: (++)
(++) concatena duas listas.
Exemplos:
[] ++ [20,10] [20,10]
[4] ++ [20,10] [4,20,10]
[1,2,3,4,5] ++ [20,10] [1,2,3,4,5,20,10]
"ana" ++ " carolina" "ana carolina"
[(10,True),(5,False)] ++ [] [(10,True),(5,False)]
[1,2] ++ [] ++ [1] ++ [0,3] [1,2,1,0,3]
Definição
infixr 5 ++
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
72/100
Operações com listas: (++)
(++) concatena duas listas.
Exemplos:
[] ++ [20,10] [20,10]
[4] ++ [20,10] [4,20,10]
[1,2,3,4,5] ++ [20,10] [1,2,3,4,5,20,10]
"ana" ++ " carolina" "ana carolina"
[(10,True),(5,False)] ++ [] [(10,True),(5,False)]
[1,2] ++ [] ++ [1] ++ [0,3] [1,2,1,0,3]
Definição
infixr 5 ++
(++) :: [a] -> [a] -> [a]
[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)
73/100
Operações com listas: concat
concat aplicada a uma lista de listas, concatena as listas em uma única lista
Exemplos:
concat [] []
concat [[1,2,3]] [1,2,3]
concat [[1,2,3], [4]] [1,2,3,4]
concat [[1,2,3], [4], [], [5,6,7,8]] [1,2,3,4,5,6,7,8]
concat ["we"," ","like"," ","lists"] "we like lists"
Definição
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
73/100
Operações com listas: concat
concat aplicada a uma lista de listas, concatena as listas em uma única lista
Exemplos:
concat [] []
concat [[1,2,3]] [1,2,3]
concat [[1,2,3], [4]] [1,2,3,4]
concat [[1,2,3], [4], [], [5,6,7,8]] [1,2,3,4,5,6,7,8]
concat ["we"," ","like"," ","lists"] "we like lists"
Definição
concat :: [[a]] -> [a]
concat [] = []
concat (xs:xss) = xs ++ concat xss
74/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
75/100
Operações com listas: reverse
reverse recebe uma lista finita e retorna uma lista com os mesmos elementos,
porém em ordem reversa.
Exemplos:
reverse [] []
reverse [1] [1]
reverse [1,2] [2,1]
reverse [1,2,3] [3,2,1]
reverse [1,2,3,4,5] [5,4,3,2,1]
reverse "ROMA" "AMOR"
Definição
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
75/100
Operações com listas: reverse
reverse recebe uma lista finita e retorna uma lista com os mesmos elementos,
porém em ordem reversa.
Exemplos:
reverse [] []
reverse [1] [1]
reverse [1,2] [2,1]
reverse [1,2,3] [3,2,1]
reverse [1,2,3,4,5] [5,4,3,2,1]
reverse "ROMA" "AMOR"
Definição
reverse :: [a] -> [a]
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
76/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
77/100
Operações com listas: zip
zip recebe duas listas e retorna a lista dos pares formados pelos elementos
correspondentes da primeira e da segunda lista.
Se as listas forem de tamanhos diferentes, o tamanho do resultado é o menor
tamanho.
Exemplos:
zip [] [] []
zip [1,2,3] [] []
zip [] [1,2,3] []
zip [True] [1] [(True,1)]
zip [1,2] ["ana","pedro"] [(1,"ana"),(2,"pedro")]
zip [1,2,3] "ABC" [(1,’A’),(2,’B’),(3,’C’)]
zip [1,2,3,4,5] [0.5,0.6] [(1,0.5),(2,0.6)]
zip [1,2,3] "BRASIL" [(1,’B’),(2,’R’),(3,’A’)]
Definição
zip :: [a] -> [b] -> [(a, b)]
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []
77/100
Operações com listas: zip
zip recebe duas listas e retorna a lista dos pares formados pelos elementos
correspondentes da primeira e da segunda lista.
Se as listas forem de tamanhos diferentes, o tamanho do resultado é o menor
tamanho.
Exemplos:
zip [] [] []
zip [1,2,3] [] []
zip [] [1,2,3] []
zip [True] [1] [(True,1)]
zip [1,2] ["ana","pedro"] [(1,"ana"),(2,"pedro")]
zip [1,2,3] "ABC" [(1,’A’),(2,’B’),(3,’C’)]
zip [1,2,3,4,5] [0.5,0.6] [(1,0.5),(2,0.6)]
zip [1,2,3] "BRASIL" [(1,’B’),(2,’R’),(3,’A’)]
Definição
zip :: [a] -> [b] -> [(a, b)]
zip (x:xs) (y:ys) = (x,y) : zip xs ys
zip _ _ = []
78/100
Operações com listas: zipWith
zipWith recebe uma função binária e duas listas e retorna a lista formada pelos
resultados da aplicação da função aos elementos correspondentes da listas
dadas.
Se as listas forem de tamanhos diferentes, o tamanho do resultado é o menor
tamanho.
Exemplos:
zipWith (+) [] [] []
zipWith (+) [1,2,3,4,5] [3,3,4,1,5] [4,5,7,5,10]
zipWith (++) ["AB","cde"] ["?","123"] ["AB?","cd123"]
zipWith (^) [5,6,7,8] [2,3,4,5] [25,216,2401,32768]
zipWith (*) [5,6,7,8] [2,3] [10,18]
Definição
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []
78/100
Operações com listas: zipWith
zipWith recebe uma função binária e duas listas e retorna a lista formada pelos
resultados da aplicação da função aos elementos correspondentes da listas
dadas.
Se as listas forem de tamanhos diferentes, o tamanho do resultado é o menor
tamanho.
Exemplos:
zipWith (+) [] [] []
zipWith (+) [1,2,3,4,5] [3,3,4,1,5] [4,5,7,5,10]
zipWith (++) ["AB","cde"] ["?","123"] ["AB?","cd123"]
zipWith (^) [5,6,7,8] [2,3,4,5] [25,216,2401,32768]
zipWith (*) [5,6,7,8] [2,3] [10,18]
Definição
zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys
zipWith _ _ _ = []
79/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
80/100
Operações com listas: map
map recebe uma função e uma lista e retorna a lista formada pela aplicação da
função em cada elemento da lista dada.
Exemplos:
map sqrt [0,1,4,9] [0.0,1.0,2.0,3.0]map succ "HAL" "IBM"
map head ["bom","dia","turma"] "bdt"
map (<3) [1,2,3] [True,True,False]
map (+2) [2,5,6,0] [4,7,8,2]
map (\x -> 2*x+1) [2,5,6,0] [5,11,13,1]
Definição
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
80/100
Operações com listas: map
map recebe uma função e uma lista e retorna a lista formada pela aplicação da
função em cada elemento da lista dada.
Exemplos:
map sqrt [0,1,4,9] [0.0,1.0,2.0,3.0]
map succ "HAL" "IBM"
map head ["bom","dia","turma"] "bdt"
map (<3) [1,2,3] [True,True,False]
map (+2) [2,5,6,0] [4,7,8,2]
map (\x -> 2*x+1) [2,5,6,0] [5,11,13,1]
Definição
map :: (a -> b) -> [a] -> [b]
map _ [] = []
map f (x:xs) = f x : map f xs
81/100
Operações com listas: filter
filter recebe uma função f e uma lista xs e retorna a lista formada pelos
elementos de xs para os quais a função f retorna True.
Exemplos:
filter even [0,1,4,9,10,11,15] [0,4,10]
filter (<10) [0,1,4,9,10,11,15] [0,1,4,9]
filter (not . null) ["abc","","d"] ["abc","d"]
Definição
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x:xs) | f x = x : filter f xs
| otherwise = filter f xs
81/100
Operações com listas: filter
filter recebe uma função f e uma lista xs e retorna a lista formada pelos
elementos de xs para os quais a função f retorna True.
Exemplos:
filter even [0,1,4,9,10,11,15] [0,4,10]
filter (<10) [0,1,4,9,10,11,15] [0,1,4,9]
filter (not . null) ["abc","","d"] ["abc","d"]
Definição
filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x:xs) | f x = x : filter f xs
| otherwise = filter f xs
82/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
83/100
Operações com listas: foldl
foldl reduz uma lista, usando uma função binária e um valor inicial, de forma
associativa à esquerda.
foldl (⊕) e [x0,x1,...,xn−1]
≡
(...((e ⊕ x0) ⊕ x1) ...) ⊕ xn−1
Exemplos:
foldl (+) 0 [] 0
foldl (+) 0 [1] 1
foldl (+) 0 [1,2] 3
foldl (+) 0 [1,2,4] 7
foldl (*) 1 [5,2,4,10] 400
foldl (&&) True [2>0,even 6,odd 5,null []] True
foldl (||) False [2>3,even 6,odd 5,null []] True
foldl (\a x -> 2*a+x) 0 [1,2,3,4,5] 57
Definição
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
83/100
Operações com listas: foldl
foldl reduz uma lista, usando uma função binária e um valor inicial, de forma
associativa à esquerda.
foldl (⊕) e [x0,x1,...,xn−1]
≡
(...((e ⊕ x0) ⊕ x1) ...) ⊕ xn−1
Exemplos:
foldl (+) 0 [] 0
foldl (+) 0 [1] 1
foldl (+) 0 [1,2] 3
foldl (+) 0 [1,2,4] 7
foldl (*) 1 [5,2,4,10] 400
foldl (&&) True [2>0,even 6,odd 5,null []] True
foldl (||) False [2>3,even 6,odd 5,null []] True
foldl (\a x -> 2*a+x) 0 [1,2,3,4,5] 57
Definição
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
84/100
Operações com listas: foldr
foldr reduz uma lista, usando uma função binária e um valor inicial, de forma
associativa à direita.foldr (⊕) e [x0,...,xn−2,xn−1]
≡
x0 ⊕ (... (xn−2 ⊕ (xn−1 ⊕ e)) ...)
Exemplos:
foldr (+) 0 [] 0
foldr (+) 0 [1] 1
foldr (+) 0 [1,2] 3
foldr (+) 0 [1,2,4] 7
foldr (*) 1 [5,2,4,10] 400
foldr (&&) True [2>0,even 6,odd 5,null []] True
foldr (||) False [2>3,even 6,odd 5,null []] True
foldr (\x a -> 2*a+x) 0 [1,2,3,4,5] 129
Definição
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
84/100
Operações com listas: foldr
foldr reduz uma lista, usando uma função binária e um valor inicial, de forma
associativa à direita.foldr (⊕) e [x0,...,xn−2,xn−1]
≡
x0 ⊕ (... (xn−2 ⊕ (xn−1 ⊕ e)) ...)
Exemplos:
foldr (+) 0 [] 0
foldr (+) 0 [1] 1
foldr (+) 0 [1,2] 3
foldr (+) 0 [1,2,4] 7
foldr (*) 1 [5,2,4,10] 400
foldr (&&) True [2>0,even 6,odd 5,null []] True
foldr (||) False [2>3,even 6,odd 5,null []] True
foldr (\x a -> 2*a+x) 0 [1,2,3,4,5] 129
Definição
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
85/100
Operações com listas: foldl1
foldl1 reduz uma lista não vazia usando uma função binária, de forma
associativa à esquerda.
foldl1 é uma variante de foldl que não tem valor inicial, e portanto deve ser
aplicada a listas não-vazias.
Exemplos:
foldl1 (+) [] erro
foldl1 (+) [1] 1
foldl1 (+) [1,2,4] 7
foldl1 (*) [5,2,4,10] 400
foldl1 (&&) [2>0,even 6,odd 5,null []] True
foldl1 max [1,8,6,10,-48,5] 10
Definição
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
85/100
Operações com listas: foldl1
foldl1 reduz uma lista não vazia usando uma função binária, de forma
associativa à esquerda.
foldl1 é uma variante de foldl que não tem valor inicial, e portanto deve ser
aplicada a listas não-vazias.
Exemplos:
foldl1 (+) [] erro
foldl1 (+) [1] 1
foldl1 (+) [1,2,4] 7
foldl1 (*) [5,2,4,10] 400
foldl1 (&&) [2>0,even 6,odd 5,null []] True
foldl1 max [1,8,6,10,-48,5] 10
Definição
foldl1 :: (a -> a -> a) -> [a] -> a
foldl1 f (x:xs) = foldl f x xs
86/100
Operações com listas: foldr1
foldr1 reduz uma lista não vazia usando uma função binária, de forma
associativa à esquerda.
foldr1 é uma variante de foldr que não tem valor inicial, e portanto deve ser
aplicada a listas não-vazias.
Exemplos:
foldr1 (+) [] erro
foldr1 (+) [1] 1
foldr1 (+) [1,2,4] 7
foldr1 (*) [5,2,4,10] 400
foldr1 (&&) [2>0,even 6,odd 5,null []] True
foldr1 max [1,8,6,10,-48,5] 10
Definição
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
86/100
Operações com listas: foldr1
foldr1 reduz uma lista não vazia usando uma função binária, de forma
associativa à esquerda.
foldr1 é uma variante de foldr que não tem valor inicial, e portanto deve ser
aplicada a listas não-vazias.
Exemplos:
foldr1 (+) [] erro
foldr1 (+) [1] 1
foldr1 (+) [1,2,4] 7
foldr1 (*) [5,2,4,10] 400
foldr1 (&&) [2>0,even 6,odd 5,null []] True
foldr1 max [1,8,6,10,-48,5] 10
Definição
foldr1 :: (a -> a -> a) -> [a] -> a
foldr1 _ [x] = x
foldr1 f (x:xs) = f x (foldr1 f xs)
87/100
Exercícios
Exercício 5
Defina a função recursiva
product :: Num a => [a] -> a
que retorna o produto de uma lista de números.
Exercício 6
Defina as funções recursivas
and :: [Bool] -> Bool
or :: [Bool] -> Bool
que retornam respectivamente a conjunção e a disjunção de uma lista de valoresl
lógicos.
88/100
Tópicos
1 Listas
2 Strings
3 Seqüências aritméticas
4 Casamento de padrão com listas
5 Operações com listas
null
head e tail, init e last
elem
length e (!!)
take, drop e splitAt
(++) e concat
reverse
zip e zipWith
map e filter
foldl e foldr, foldl1 e foldr1
6 List comprehension
89/100
List comprehension
Em Matemática, a notação de compreensão pode ser usada para construir novos
conjuntos a partir de conjuntos já conhecidos.
Exemplo:
{x2|x ∈ [1...5]}
é o conjunto {1,4,9,16,25} de todos os números x2 tal que x é um elemento do
conjunto {1,2,3,4,5}.
90/100
List comprehension (cont.)
Em Haskell também há uma notação de compreensão similar que pode ser
usada para construir novas listas a partir de listas conhecidas.
Exemplo:
[ x^2 | x <- [1..5] ]
é a lista [1,4,9,16,25] de tdos os números x^2 tal que x é um elmento da lista
[1,2,3,4,5].
91/100
List comprehension (cont.)
A expressão x <- [1..5] é chamada gerador, já que ela informa como gerar
valores para a variável x.
Compreensões podem ter múltiplos geradores, separados por vírgula.
Exemplo:
[(x,y) | x <- [1,2,3], y <- [4,5]]
 [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]
92/100
List comprehension (cont.)
Se a ordem dos geradores for trocada, a ordem dos elementos na lista resultante
também é trocada.
Exemplo:
[(x,y) | y <- [4,5], x <- [1,2,3]]
 [(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]
93/100
List comprehension (cont.)
Geradores múltiplos são semelhantes a loops aninhados: os últimos geradores
são como loopsmais profundamente aninhados cujas variáveis mudam mais
freqüentemente.
Exemplo:
[(x,y) | y <- [4,5], x <- [1,2,3]]
 [(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]
Como x <- [1,2,3] é o último gerador, o valor do componente x de cada par
muda mais frequentemente.
94/100
List comprehension (cont.)
Geradores posteriores podem depender de variáveis introduzidas em geradores
anteriores.
Exemplo:
[(x,y) | x <- [1..3], y <- [x..3]]
 [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]
a lista [(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)] de todos os pares de
números (x,y) tal que x e y são elementos da lista [1..3] e y >= x.
95/100
List comprehension (cont.)
Exemplo:
Usando geradores dependentes pode-se definir a função que concatena uma
lista de listas:
concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]
concat [[1,2,3],[4,5],[6]] [1,2,3,4,5,6]
96/100
List comprehension (cont.)
List comprehensions podem usar guardas para restringir os valores produzidos
por geradores anteriores.
Exemplo:
[x | x <- [1..10], even x]
 [2,4,6,8,10]
a lista de todos os números x tal que x é um elemento da lista [1..10] e x é par.
97/100
List comprehension (cont.)
Exemplo:
Usando uma guarda podemos definir uma função que mapeia um número inteiro
positivo à sua lista de fatores:
factors :: Int -> [Int]
factors n = [x | x <- [1..n], n ‘mod‘ x == 0]
Exemplos de aplicação da função:
factors 15 [1,3,5,15]
factors 120 [1,2,3,4,5,6,8,10,12,15,20,24,30,40,60,120]
98/100
List comprehension (cont.)
Exemplo:
Um número inteiro positivo é primo se seus únicos fatores são 1 e ele próprio.
Assim, usando fatores que podemos definir uma função que decide se um
número é primo:
prime :: Int -> Bool
prime n = factors n == [1,n]
Exemplos de aplicação da função:
prime 15 False
prime 7 True
99/100
List comprehension (cont.)
Exemplo:
Usando um guarda agora podemos definir uma função que retorna a lista de
todos os números primos até um determinado limite:
primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]
Exemplos de aplicação da função:
primes 40 [2,3,5,7,11,13,17,19,23,29,31,37]
primes 12 [2,3,5,7,11]
100/100
Fim
	Listas
	Strings
	Seqüências aritméticas
	Casamento de padrão com listas
	Operações com listas
	null
	head e tail, init e last
	elem
	length e (!!)
	take, drop e splitAt
	(++) e concat
	reverse
	zip e zipWith
	map e filter
	foldl e foldr, foldl1 e foldr1
	List comprehension