Programação Programação FuncionalFuncional
8a. Seção de Slides
Generalização em HaskellGeneralização em Haskell(2a. Parte)(2a. Parte)
2
Polimorfismo e Ordem Mais Alta• Importantes funções que são polimórficas e de
ordem mais alta, simultaneamente:– map (mapear: aplicar sobre) : uma lista L2 é criada a
partir de uma lista L1, aplicando uma operação sobre cada elemento de L1;
– fold (redução) : um valor é calculado, resultado da aplicação de uma operação binária ao longo de toda uma lista de elementos;
– filter (filtrar): uma lista L2 é criada a partir de uma lista L1, selecionando alguns elementos de L1 que satisfazem a uma determinada propriedade.
• As funções map , fold e filter não impõem qualquer restrição sobre os tipos envolvidos.
3
Map (aplicar sobre: mapear)
• Uma lista L2 é criada a partir de uma lista L1, aplicando uma operação sobre cada elemento de L1.
• Não há restrição sobre o tipo dos elementos de L1, que ainda pode ser diferente do tipo dos elementos de L2.
L1 = [ e1 , e2 , ... , ek ]
L2 = [ f(e1) , f(e2) , ... , f(ek) ]
f f f
4
Map (aplicar sobre: mapear)
Main> map times2 [2,3,4][4,6,8]Main> map times3 [2,3,4][6,9,12]
Main> map times2 [2,3,4][4,6,8]Main> map times3 [2,3,4][6,9,12]
1 .2 .3 .
1 .2 .3 .
times2, times3 :: Int -> Inttimes2 n = 2*ntimes3 n = 3*n
5
Map (aplicar sobre: mapear)1 .2 .3 .4 .
1 .2 .3 .4 .
isEven :: Int -> BoolisEven n | n `mod` 2 == 0 = True | otherwise = False
6
Map (aplicar sobre: mapear)
Main> map isEven [2,3,4][True,False,True]
Main> map isEven [2,3,4][True,False,True]
1 .2 .
1 .2 .
isEven :: Int -> BoolisEven n = (n `mod` 2 == 0)
7
Map (aplicar sobre: mapear)
Main> map small "ABC Esporte Clube""abc esporte clube"
Main> map small "ABC Esporte Clube""abc esporte clube"
1 .2 .3 .4 .5 .6 .
1 .2 .3 .4 .5 .6 .
offset = ord 'a' - ord 'A'isCapital ch = (ch >= 'A') && (ch <= 'Z')small :: Char -> Charsmall ch | isCapital ch = chr (ord ch + offset) | otherwise = ch
8
Map (aplicar sobre: mapear)
Main> map length ["ABC","Esporte","Clube"][3,7,5]Main> map length [2,3,4]ERRO DE TIPO!!!
Main> map length ["ABC","Esporte","Clube"][3,7,5]Main> map length [2,3,4]ERRO DE TIPO!!!
1 .2 .
1 .2 .
length [] = 0length (a:x) = 1 + length x
9
Map (aplicar sobre: mapear)
1 .2 .3 .
1 .2 .3 .
map :: (t -> u) -> [t] -> [u]map f [] = []map f (a:x) = f a : map f x
1 .2 .
1 .2 .
map :: (t -> u) -> [t] -> [u]map f l = [ f a | a <- l ]
• Definição:
• Alternativa:
10
Fold (“dobrar”, redução, resumir)
• Um valor é calculado, resultado da aplicação de uma operação binária ao longo de toda uma lista de elementos.
• Não há restrição sobre o tipo dos elementos da lista.
fold f [ e1 ] = e1
fold f [ e1 , e2 , ... , ek ]= e1 `f` (e2 `f` (... `f` ek) ...)= f e1 (fold f [ e2 , ... , ek ])
11
Fold (“dobrar”, redução, resumir)
Main> fold (+) [1..3]6Main> fold (||) [False,True,False]TrueMain> fold (++) ["ABC"," Esporte", " ", "Clube"]"ABC Esporte Clube"Main> fold (-) [1..3]2
Main> fold (+) [1..3]6Main> fold (||) [False,True,False]TrueMain> fold (++) ["ABC"," Esporte", " ", "Clube"]"ABC Esporte Clube"Main> fold (-) [1..3]2
12
Main> fold maxi [2,4,3]4Main> fold maxi [2]2Main> fold maxi []ERRO!!!
Main> fold maxi [2,4,3]4Main> fold maxi [2]2Main> fold maxi []ERRO!!!
1 .2 .3 .4 .
1 .2 .3 .4 .
maxi :: Int -> Int -> Intmaxi a b | a > b = a | otherwise = b
Fold (“dobrar”, redução, resumir)
13
1 .2 .3 .
1 .2 .3 .
fold :: (t -> t -> t) -> [t] -> tfold f [a] = afold f (a:b:x) = f a (fold f (b:x))
• Definição:
• Mas os tipos da definição podem ser mais gerais...• Qual a restrição sobre o tipo da operação f que será executada ao longo da lista?
Fold (“dobrar”, redução, resumir)
14
Fold (“dobrar”, redução, resumir)
fold f [ e1 , e2 , ... , ek ]= e1 `f` (e2 `f` (... `f` ek) ...)= f e1 (fold f [ e2 , ... , ek ])
tipo do primeiro argumento de f tem que ser t
tipo do segundo argumento de f tem que ser o mesmo do valor de
retorno de fold
• Supondo uma lista [e1,...,ek] de tipo [t] :
15
Fold (“dobrar”, redução, resumir)
fold f [ e1 , e2, e3 ]= f e1 (fold f [ e2 , e3 ])= f e1 (f e2 (fold f [ e3 ]))= f e1 (f e2 e3)
tipo do valor de retorno de f deve ser o mesmo tipo do segundo argumento de f
• Supondo uma lista [e1,...,ek] de tipo [t] :
16
Fold (“dobrar”, redução, resumir)
• Restrições:– tipo do primeiro argumento de f tem que ser t, o tipo dos elementos da lista.– tipo do segundo argumento de f tem que ser o mesmo tipo do valor de retorno de fold.
– tipo do valor de retorno de f deve ser o mesmo tipo do segundo argumento de f.
1 .2 .3 .
1 .2 .3 .
fold :: (t -> u -> u) -> [t] -> ufold f [a] = afold f (a:b:x) = f a (fold f (b:x))
17
Fold (“dobrar”, redução, resumir)
1 .2 .3 .4 .5 .
1 .2 .3 .4 .5 .
fold1 :: (t -> u -> u) -> u -> [t] -> ufold1 f s [] = sfold1 f s (a:x) = f a (fold1 f s x)
sumListInt l = fold1 (+) 0 l
• Acrescentando um argumento a fold:
Main> sumListInt [1..3]6Main> sumListInt [3]3Main> sumListInt []0
Main> sumListInt [1..3]6Main> sumListInt [3]3Main> sumListInt []0
18
Filter (Filtrar)
• Uma lista L2 é criada a partir de uma lista L1, selecionando alguns elementos de L1 que satisfazem a uma determinada propriedade.
• Não há restrição sobre o tipo dos elementos de L1, mas é o mesmo tipo dos elementos de L2.
L1 = [ e1 , e2 , ... , ek ]
L2 = [ e1 , e2 , ... , ek ]
p? ok p? não p? ok
19
Filter (Filtrar)
• Supondo uma lista [e1,...,ek] de tipo [t] , a propriedade p que é aplicada aos elementos da lista é do tipo:
t -> Bool
L1 = [ e1 , e2 , ... , ek ]
L2 = [ e1 , e2 , ... , ek ]
p? ok p? não p? ok
20
Filter (Filtrar)
Main> filter isEven [1..6][2,4,6]
Main> filter isEven [1..6][2,4,6]
1 .2 .
1 .2 .
isEven :: Int -> BoolisEven n = (n `mod` 2 == 0)
21
Filter (Filtrar)
Main> filter nonEmpty ["ABC","","Esporte Clube"]["ABC","Esporte Clube"]
Main> filter nonEmpty ["ABC","","Esporte Clube"]["ABC","Esporte Clube"]
1 .2 .
1 .2 .
nonEmpty :: String -> BoolnonEmpty st = (st /= "")
22
Filter (Filtrar)
1 .2 .3 .4 .5 .
1 .2 .3 .4 .5 .
filter :: (t -> Bool) -> [t] -> [t]filter p [] = []filter p (a:x) | p a = a : filter p x | otherwise = filter p x
• Definição:
1 .2 .
1 .2 .
filter :: (t -> Bool) -> [t] -> [t]filter p l = [ a | a <- l, p a ]
• Alternativa:
Recommended
