Aula 6 Listas - DECOM-UFOP | Início3/104 Layout 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

1/104

Programação Funcional

Aula 6

Listas

José Romildo Malaquias

Departamento de ComputaçãoUniversidade Federal de Ouro Preto

2011.2

2/104

1 Listas

2 Strings

3 Seqüências aritméticas

4 Casamento de padrão com listas

5 Operações com listasnullhead e tail, init e lastelemlength e (!!)take, drop e splitAt(++) e concatreversezip e zipWithmap e filterfoldl e foldr, foldl1 e foldr1

6 List comprehension

3/104

Layout

1 Listas

2 Strings





4/104

Listas

I Lista é uma seqüência de elementos de um mesmo tipo.

I [a] é o tipo das listas cujos elementos são do tipo aI Estruturalmente a forma de uma lista pode ser:

lista vazianenhum elemento na seqüênciaconstrutor de dado: (constante)

[] :: [a]

lista não vaziaformada por dois componentes:cabeça: o primeiro elemento da listacauda: lista de todos os demais elementos, a partir do segundoconstrutor 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/104

Exemplos de listas

[]

I seqüência vazia (nenhum elemento)

I não tem cabeça e nem cauda

I tipo: [a]

I é um valor polimórfico, pois pertence a todos os tipos lista

6/104

Exemplos de listas (cont.)

False : []

I seqüência: False

I cabeça: False

I cauda: []

I tipo: [Bool]

7/104


’a’ : (’b’ : [])

I seqüência: ’a’, ’b’

I cabeça: ’a’

I cauda: ’b’ : []

I tipo: [Char]

8/104


15 : (9 : (42 : []))

I seqüência: 15, 9, 42

I cabeça: 15

I cauda: 9 : (42 : [])

I tipo: Num a => [a]

9/104


15 : (9.45 : (15 : (0 : [])))

I seqüência: 15, 9.45, 15, 0

I cabeça: 15

I cauda: 9.45 : (15 : (0 : []))

I tipo: Fractional a => [a]

10/104


15 : (’H’ : (False : []))não é uma expressão válida, uma vez que todos os elementos de umalista devem ser de um mesmo tipo.

11/104

Notações de listas

I O construtor constante [] denota a lista vazia.

I O construtor : constrói uma lista não vazia a partir da cabeça eda cauda.

I : é um operador binário infixo com precedência 5 eassociatividade à direita.

I Isto significa que os parênteses no segundo argumentogeralmente são desnecessários.

I Exemplo: o valor100 : 200 : 300 : 400 : []

é idêntido a100 : (200 : (300 : (400 : [])))

12/104

Notações de listas (cont.)

I Uma lista finita pode ser denotada escrevendo os seuselementos entre colchetes e separados por vírgula:[ exp1, ..., expn ]

I Esta é uma notação simplificada para listas finitas, sendoequivalente aexp1 : ... : expn : []

13/104


I Exemplo:A lista de 6 números[10, 20, 30, 40, 50, 60]

é apenas uma abreviação sintática para10 : 20 : 30 : 40 : 50 : 60 : []

14/104


I Exemplo:A lista[[]]

que é uma abreviação para[] : []

é a lista unitária cujo único elemento é a lista vazia. O seu tipo é[[a]].

15/104

Exercícios

Exercício 1

Dê um exemplo de uma expressão que contenha duas ocorrências dalista vazia, sendo a primeira ocorrência do tipo [Bool] e a segundado tipo [Char].

16/104

Layout

1 Listas

2 Strings





17/104

Strings

I Em Haskell strings (cadeias de caracteres) são simplesmentelistas de caracteres.

I O tipo String é um sinônimo para [Char] .

I Existe uma notação especial para constantes strings: aseqüência de caracteres é escrita entre aspas " .

I Exemplos:

A string "UFOP" é apenas uma sintaxe conveniente para a lista decaracteres [’U’,’F’,’O’,’P’]A string vazia "" é o mesmo que [], a lista vazia, do tipo [Char].

18/104

Strings (cont.)

I Códigos de escape podem ser usados em constantes caractere constantes strings para representar alguns caracteres.

I Exemplos:’\n’’\\’"bom\ndia\nbrasil""abcd\tEFG""\"aspas\" dentro da string""tabulador:\tou\Îou\9."

19/104

Strings (cont.)

I 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/104

Strings (cont.)

I Códigos de controle:

Escape Escape Unicode Meaning\NUL \^@ U+0000 null character\SOH \Â 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 \Ê U+0005 enquiry\ACK \^F U+0006 acknowledge\BEL \^G U+0007 bell\BS \^H U+0008 backspace\HT \Î 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

21/104

Strings (cont.)

\SO \^N U+000E shift out\SI \Ô U+000F shift in\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+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

22/104

Strings (cont.)

\US \^_ U+001F unit separator\SP U+0020 space\DEL U+007F delete

23/104

Strings (cont.)

I Códigos de escape numéricos:

\decimal código decimal\o octal código octal\x hexa código hexadecimal

Exemplos:\1234\xbeef\o1234O valor numérico máximo é \1114111, que também pode serescrito \x10ffff ou \o4177777.

24/104

Strings (cont.)

I Seqüência de escape vazia:\&

Literais string podem conter a seqüência de esccape vazia,escrita \&.Ela não é um caracter real, mas serve para separar umaseqüência de escape numérica de um dígito decimal que vemlogo em seguida.Exemplo:A string "\130\&12" é formada pelos caracteres ’\130’, ’1’ e’2’.Já a string "\13012" é formada apenas pelo caracter ’\13012’.

25/104

Strings (cont.)

I 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"

26/104

Instância de classes

I 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]

I Duas listas são iguais se e somente se os seus elementoscorrespondentes são iguais.

I A comparação de listas é lexicográfica (da mesma maneira quepalavras são organizadas em um dicionário).

27/104

Instância de classes (cont.)

I 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] Truecompare "Abracadabra" "Zebra" LTshow [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"

28/104

Layout

1 Listas

2 Strings





29/104

Seqüências aritméticas

Haskell tem uma sintaxe especial para seqüências aritméticas.

30/104

Seqüências aritméticas (cont.)

[ exp1, exp2 .. exp3 ]

I É a seqüência aritmética que começa com exp1, continua comexp2 e cujos elementos não ultrapassam exp3.

I Para tipos numéricos, a razão da progressão é exp2− exp1.I 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’] ""

31/104


[ exp1 .. exp2 ]

I É a seqüência aritmética que começa com exp1 e cujoselementos não ultrapassam exp2.

I Para tipos numéricos, a razão da progressão é 1.I 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]

32/104


[ exp1, exp2 .. ]

I É a seqüência aritmética que começa com exp1 e cujo segundoelemento é exp2.

I Para tipos numéricos, a razão da progressão é exp2− exp1.

I Pode ser infinita.I 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)

33/104


[ exp1 .. ]

I É a seqüência aritmética que começa com exp1.

I Para tipos numéricos, a razão da progressão é 1.

I Pode ser infinita.I 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]

34/104


I A notação de lista para seqüências aritméticas é simplesmenteuma abreviação sintática para aplicações de métodos da classeEnum:[ a, b .. c ] ≡ enumFromThenTo a b c[ a .. b ] ≡ enumFromTo a b[ a, b .. ] ≡ enumFromThen a b[ a .. ] ≡ enumFrom a

I Exemplo:[10,15..44] [10,15,20,25,30,35,40]enumFromThenTo 10 15 44 [10,15,20,25,30,35,40]

I Portanto seqüências aritméticas só podem ser usadas para listasde elementos de um tipo que seja instância da classe Enum.

35/104


I A classe Enum:class Enum a where

succ :: a -> apred :: a -> atoEnum :: Int -> afromEnum :: a -> IntenumFrom :: 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 ()

36/104

Layout

1 Listas

2 Strings





37/104

Casamento de padrão com listas

I Casamento de padrão é a operação básica de Haskell paradecompor valores estruturados.

I Para cada construtor de dados existe uma forma de padrãocorrespondente.

38/104

Casamento de padrão com listas (cont.)

I Estruturalmente uma lista pode ser vazia ou não vazia:padrão lista vazia[]

é um padrão constanteo casamento sucede se e somente se o valor for a lista vazia

padrão lista não vazia

pad1 : pad2

é formado por dois padrões pad1 e pad2o casamento sucede se e somente se o valor for uma lista nãovazia cuja cabeça casa com pad1 e cuja cauda casa com pad2

39/104


I Exemplo:O padrão [] casa somente com a lista vazia.

padrão valor casamento variáveis[] [] sucede[] [1,2,3] falha

40/104


I Exemplo:O padrão x:xs casa com qualquer lista não vazia, associandoas variáveis x e xs com a cabeça e a cauda da lista,respectivamente.

padrão valor casamento variáveisx:xs [] falhax:xs [1,2,3] sucede x 7→ 1, xs 7→ [2,3]x:xs [’A’] sucede x 7→ ’A’, xs 7→ []

41/104


I Exemplo:O padrão x:y:_ casa com qualquer lista que tenha pelo menosdois elementos, associando as variáveis x e y ao primeiro esegundo elementos da lista, respectivamente.

padrão valor casamento variáveisx:y:_ [] falhax:y:_ ["ana"] falhax:y:_ [1,2] sucede x 7→ 1, y 7→ 2x:y:_ [1,2,3] sucede x 7→ 1, y 7→ 2

42/104


I Exemplo:O padrão x:_:z:[] casa com qualquer lista que tenhaexatamente três elementos, associando as variáveis x e z aoprimeiro e terceiro elementos da lista, respectivamente.

padrão valor casamento variáveisx:_:z:[] [] falhax:_:z:[] ["ana"] falhax:_:z:[] [1,2,3] sucede x 7→ 1, z 7→ 3x:_:z:[] [1,2,3,4,5] falha

43/104


I Exemplo:O padrão 0:a:_ casa com qualquer lista de números que tenhapelo menos dois elementos, sendo o primeiro igual a zero,associando a variável a ao segundo elemento da lista.

padrão valor casamento variáveis0:a:_ [] falha0:a:_ [0] falha0:a:_ [0,2,3] sucede a 7→ 20:a:_ [0,10,6,3] sucede a 7→ 100:a:_ [7,0,8] falha

44/104


I Exemplo:O padrão (m,_):_ casa com qualquer lista de pares não vazia,associando a variável m ao primeiro componente do par que é oprimeiro 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

45/104


I A forma[ padrao1, . . ., padraon ]

é uma abreviação sintática parapadrao1 : . . . : padraon : []

cujo casamento sucede somente se a lista tiver exatamente nelementos.

46/104


I Exemplo:O padrão [1,alfa] casa com qualquer lista de dois númerosque começa com 1, associando a variável alfa ao segundoelemento 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

47/104


I Exemplo:A expressãocase tail [10] of

[] -> "vazia"_ -> "nao vazia"

resulta em "vazia", pois o valor da expressão tail [10] casacom o padrão para lista vazia [].

48/104


I Exemplo:A expressãocase [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].

49/104


I Exemplo:A expressãocase [10..20] of

x:y:z:_ -> x + y + z_ -> 0

resulta em 33, pois a lista [10..20] casa com o padrãox:y:z:_, associando x com 10, y com 11 e z com 12.

50/104


I Exemplo:A expressãocase [10,20] of

x:y:z:_ -> x + y + z_ -> 0

resulta em 0, pois a lista [10,20] não casa com o primeiropadrão x:y:z:_, mas casa com o segundo _.Observe que o primeiro padrão casa somente com listas quetenham pelo menos três elementos.

51/104


I Exemplo:A expressãocase [10,20,30] of

[x1,_,x3] -> x1 + x3_ -> 0

resulta em 40, pois a lista [10,20,30] casa com o primeiropadrão [x1,_,x3].Observe que este padrão casa somente com listas que tenhamexatamente três elementos.

52/104


I Exemplo:A expressãocase [100,20,3] of

a:b:xs | a > b -> b:a:xs| a = b -> a:xs

xs -> xsresulta em [20,100,3], pois a lista [100,20,3] casa com oprimeiro padrão a:b:xs e o primeiro elemento é maior do que osegundo.

53/104

Exercícios

Exercício 2

Defina uma função usando casamento de padrão que retorna osucessor do primeiro elemento de uma lista, se houver, e zero casocontrário.

Exercício 3

Usando casamento de padrão, defina uma função que retorna a somados dois primeiros elementos de uma lista se a lista tiver pelo menosdois elementos, a cabeça da lista se ela contiver apenas umelemento, e zero caso contrário.

Exercício 4

Resolva os exercícios 2 e 3 usando funções da biblioteca ao invés decasamento de padrão.

54/104

Layout

1 Listas

2 Strings





55/104

Operações com listas

I As listas são muito importantes na programação funcional.

I Serão apresentadas as operações principais com listas.

56/104

Layout

1 Listas

2 Strings





57/104

Operações com listas: null

I null retorna True se o seu argumento é a lista vazia ([]) e Falsecaso contrário.

I Exemplos:null [] Truenull [1,2,3,4,5] Falsenull "" Truenull "FIM" False

null :: [a] -> Boolnull [] = Truenull _ = False

58/104

Layout

1 Listas

2 Strings





59/104

Operações com listas: head

I head seleciona o primeiro elemento de uma lista não vazia.

I Exemplos:head [10,20,30,40,50] 10head "FIM" ’F’head [] errohead "" erro

head :: [a] -> ahead (x:_) = x

60/104

Operações com listas: tail

I tail seleciona a cauda de uma lista não vazia, isto é, todos oselementos exceto o primeiro.

I Exemplos:tail [10,20,30,40,50] [20,30,40,50]tail "Aroma" "roma"tail [] errotail "" erro

tail :: [a] -> atail (_:xs) = xs

61/104

Operações com listas: init

I init seleciona todos os elementos de uma lista não vazia,exceto o último elemento.

I Exemplos:init [15] []init [True,False] [True]init [1,2,3,4,5] [1,2,3,4]init "Brasil" "Brasi"init [] erro

init :: [a] -> [a]init [_] = []init (x:xs) = x : init xs

62/104

Operações com listas: last

I last seleciona o último elemento de uma lista não vazia.

I Exemplos:last [15] 15last [True,False] Falselast [1,2,3,4,5] 5last "Brasil" ’l’last [] erro

last :: [a] -> alast [x] = xlast (_:xs) = last xs

63/104

Layout

1 Listas

2 Strings





64/104

Operações com listas: elem

I elem recebe um valor e uma lista e retorna True se e somentese o valor é um elemento da lista.

I Exemplos:elem 5 [] Falseelem 5 [5] Trueelem 5 [4,5] Trueelem ’d’ "Pedro" True8 ‘elem‘ [2,4,6,8,10] True’#’ ‘elem‘ "Pedro" False

infixl 4 ‘elem‘elem :: Eq a => a -> [a] -> Boolelem _ [] = Falseelem x (y:ys) = x == y || elem x ys

65/104

Layout

1 Listas

2 Strings





66/104

Operações com listas: length

I length retorna o número de elementos de uma lista finita.

I Exemplos:length [] 0length [15] 1length [div 2 0, mod 3 0] 2length [1,2,3,4,5] 5length "Brasil" 6

length :: [a] -> Intlength [] = 0length (_:xs) = 1 + length xs

67/104

Operações com listas: (!!)

I (!!) recebe uma lista e um número inteiro e retorna o elementoda lista cuja posição é dada pelo número.

I A posição do primeiro elemento é zero.

I A posição do último elemento é o tamanho da lista menos um.

I Se a posição for inválida ocorre um erro.

I 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

infixl 9 !!(!!) :: [a] -> Int -> a(x:_) !! 0 = x(_:xs) !! n = xs !! (n-1)

68/104

Layout

1 Listas

2 Strings





69/104

Operações com listas: take

I take recebe um número inteiro n e uma lista xs e retorna oprefixo de tamanho n da lista xs.

I 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] []

take :: Int -> [a] -> [a]take n _ | n <= 0 = []take _ [] = []take n (x:xs) = x : take (n-1) xs

70/104

Operações com listas: drop

I drop recebe um número inteiro n e uma lista xs e retorna o sufixoda lista xs após os n primeiros elementos.

I 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]

drop :: Int -> [a] -> [a]drop n xs | n <= 0 = xsdrop _ [] = []drop n (_:xs) = drop (n-1) xs

71/104

Operações com listas: splitAt

I splitAt recebe um número inteiro n e uma lista xs e retorna umpar onde o primeiro elemento é um prefixo de tamanho n de xs eo segundo elemento é o resto da lista.

I 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])

72/104

Operações com listas: splitAt (cont.)

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

73/104

Layout

1 Listas

2 Strings





74/104

Operações com listas: (++)

I (++) concatena duas listas.

I 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]

infixr 5 ++(++) :: [a] -> [a] -> [a][] ++ ys = ys(x:xs) ++ ys = x : (xs ++ ys)

75/104

Operações com listas: concat

I concat aplicada a uma lista de listas, concatena as listas emuma única lista

I 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"

concat :: [[a]] -> [a]concat [] = []concat (xs:xss) = xs ++ concat xss

76/104

Layout

1 Listas

2 Strings





77/104

Operações com listas: reverse

I reverse recebe uma lista finita e retorna uma lista com osmesmos elementos, porém em ordem reversa.

I 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"

reverse :: [a] -> [a]reverse [] = []reverse (x:xs) = reverse xs ++ [x]

78/104

Layout

1 Listas

2 Strings





79/104

Operações com listas: zip

I zip recebe duas listas e retorna a lista dos pares formados peloselementos correspondentes da primeira e da segunda lista.

I Se as listas forem de tamanhos diferentes, o tamanho doresultado é o menor tamanho.

I 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’)]

zip :: [a] -> [b] -> [(a, b)]zip (x:xs) (y:ys) = (x,y) : zip xs yszip _ _ = []

80/104

Operações com listas: zipWith

I zipWith recebe uma função binária e duas listas e retorna a listaformada pelos resultados da aplicação da função aos elementoscorrespondentes da listas dadas.

I Se as listas forem de tamanhos diferentes, o tamanho doresultado é o menor tamanho.

I 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]

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]zipWith f (x:xs) (y:ys) = f x y : zipWith f xs yszipWith _ _ _ = []

81/104

Layout

1 Listas

2 Strings





82/104

Operações com listas: map

I map recebe uma função e uma lista e retorna a lista formada pelaaplicação da função em cada elemento da lista dada.

I 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]

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

83/104

Operações com listas: filter

I filter recebe uma função f e uma lista xs e retorna a listaformada pelos elementos de xs para os quais a função f retornaTrue.

I 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"]

filter :: (a -> Bool) -> [a] -> [a]filter _ [] = []filter f (x:xs)

| f x = x : filter f xs| otherwise = filter f xs

84/104

Layout

1 Listas

2 Strings





85/104

Operações com listas: foldl

I foldl reduz uma lista, usando uma função binária e um valorinicial, de forma associativa à esquerda.

I foldl (⊕) e [x0,x1,...,xn−1]≡(...((e ⊕ x0) ⊕ x1) ...) ⊕ xn−1

I Exemplos:foldl (+) 0 [] 0foldl (+) 0 [1] 1foldl (+) 0 [1,2] 3foldl (+) 0 [1,2,4] 7foldl (*) 1 [5,2,4,10] 400foldl (&&) True [2>0,even 6,odd 5,null []] Truefoldl (||) False [2>3,even 6,odd 5,null []] Truefoldl (\a x -> 2*a+x) 0 [1,2,3,4,5] 57

86/104

Operações com listas: foldl (cont.)

foldl :: (a -> b -> a) -> a -> [b] -> afoldl f z [] = zfoldl f z (x:xs) = foldl f (f z x) xs

87/104

Operações com listas: foldr

I foldr reduz uma lista, usando uma função binária e um valorinicial, de forma associativa à direita.

I foldr (⊕) e [x0,...,xn−2,xn−1]≡x0 ⊕ (... (xn−2 ⊕ (xn−1 ⊕ e)) ...)

I Exemplos:foldr (+) 0 [] 0foldr (+) 0 [1] 1foldr (+) 0 [1,2] 3foldr (+) 0 [1,2,4] 7foldr (*) 1 [5,2,4,10] 400foldr (&&) True [2>0,even 6,odd 5,null []] Truefoldr (||) False [2>3,even 6,odd 5,null []] Truefoldr (\x a -> 2*a+x) 0 [1,2,3,4,5] 129

88/104

Operações com listas: foldr (cont.)

foldr :: (a -> b -> b) -> b -> [a] -> bfoldr f z [] = zfoldr f z (x:xs) = f x (foldr f z xs)

89/104

Operações com listas: foldl1

I foldl1 reduz uma lista não vazia usando uma função binária, deforma associativa à esquerda.

I foldl1 é uma variante de foldl que não tem valor inicial, eportanto deve ser aplicada a listas não-vazias.

I Exemplos:foldl1 (+) [] errofoldl1 (+) [1] 1foldl1 (+) [1,2,4] 7foldl1 (*) [5,2,4,10] 400foldl1 (&&) [2>0,even 6,odd 5,null []] Truefoldl1 max [1,8,6,10,-48,5] 10

foldl1 :: (a -> a -> a) -> [a] -> afoldl1 f (x:xs) = foldl f x xs

90/104

Operações com listas: foldr1

I foldr1 reduz uma lista não vazia usando uma função binária, deforma associativa à esquerda.

I foldr1 é uma variante de foldr que não tem valor inicial, eportanto deve ser aplicada a listas não-vazias.

I Exemplos:foldr1 (+) [] errofoldr1 (+) [1] 1foldr1 (+) [1,2,4] 7foldr1 (*) [5,2,4,10] 400foldr1 (&&) [2>0,even 6,odd 5,null []] Truefoldr1 max [1,8,6,10,-48,5] 10

foldr1 :: (a -> a -> a) -> [a] -> afoldr1 _ [x] = xfoldr1 f (x:xs) = f x (foldr1 f xs)

91/104

Exercícios

Exercício 5

Defina a função recursivaproduct :: Num a => [a] -> a

que retorna o produto de uma lista de números.

Exercício 6

Defina as funções recursivasand :: [Bool] -> Boolor :: [Bool] -> Bool

que retornam respectivamente a conjunção e a disjunção de uma listade valoresl lógicos.

92/104

Layout

1 Listas

2 Strings





93/104

List comprehension

I Em Matemática, a notação de compreensão pode ser usada paraconstruir novos conjuntos a partir de conjuntos já conhecidos.

I 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}.

94/104

List comprehension (cont.)

I Em Haskell também há uma notação de compreensão similarque pode ser usada para construir novas listas a partir de listasconhecidas.

I Exemplo:[ x^2 | x <- [1..5] ]

é a lista [1,4,9,16,25] de tdos os números x^2 tal que x é umelmento da lista [1,2,3,4,5].

95/104


I A expressão x <- [1..5] é chamada gerador, já que elainforma como gerar valores para a variável x.

I Compreensões podem ter múltiplos geradores, separados porvírgula.

I Exemplo:[(x,y) | x <- [1,2,3], y <- [4,5]] [(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

96/104


I Se a ordem dos geradores for trocada, a ordem dos elementosna lista resultante também é trocada.

I Exemplo:[(x,y) | y <- [4,5], x <- [1,2,3]] [(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

97/104


I Geradores múltiplos são semelhantes a loops aninhados: osúltimos geradores são como loops mais profundamenteaninhados cujas variáveis mudam mais freqüentemente.

I 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 componentex de cada par muda mais frequentemente.

98/104


I Geradores posteriores podem depender de variáveisintroduzidas em geradores anteriores.

I 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 ospares de números (x,y) tal que x e y são elementos da lista[1..3] e y >= x.

99/104


I Exemplo:Usando geradores dependentes pode-se definir a função queconcatena 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]

100/104


I List comprehensions podem usar guardas para restringir osvalores produzidos por geradores anteriores.

I 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.

101/104


I Exemplo:Usando uma guarda podemos definir uma função que mapeiaum 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]

102/104


I Exemplo:Um número inteiro positivo é primo se seus únicos fatores são 1e ele próprio. Assim, usando fatores que podemos definir umafunção que decide se um número é primo:prime :: Int -> Boolprime n = factors n == [1,n]

Exemplos de aplicação da função:prime 15 Falseprime 7 True

103/104


I Exemplo:Usando um guarda agora podemos definir uma função queretorna a lista de todos os números primos até um determinadolimite: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]

104/104

Fim

Documents

Aula 6 Listas - DECOM-UFOP | Início3/104 Layout 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