View
215
Download
0
Category
Preview:
Citation preview
Generalizações:Map, Fold, Filter, e Composição
©André Santos e Marcelo d’Amorim 2010
Padrão Recursivo Map
©André Santos e Marcelo d’Amorim 2010
O que há de diferente entre doubleL e sqrL?
doubleL :: [Int] -> [Int]doubleL [] = []doubleL (a:x) = (2*a) : doubleL x
Padrão Recursivo Map
©André Santos e Marcelo d’Amorim 2010
doubleL :: [Int] -> [Int]doubleL [] = []doubleL (a:x) = (2*a) : doubleL x
Padrão Recursivo Map
©André Santos e Marcelo d’Amorim 2010
doubleL :: [Int] -> [Int]doubleL [] = []doubleL (a:x) = (2*a) : doubleL x
doubleL = map doublesqrL = map sqr
A função de mapeamento
• Recebe como argumentos:– Uma função de transformação a ser
aplicada a cada elemento da lista– a lista de entrada
©André Santos e Marcelo d’Amorim 2010
mapmap :: (t -> u) -> [t] -> [u]map f [] = []map f (a:as) = f a : map f as
snds :: [(t,u)] -> [u]snds xs = map snd xs
map length [“abc“, “defg“] = ?
©André Santos e Marcelo d’Amorim 2010
Outra definição para map
map f l = [f a | a <- l]
©André Santos e Marcelo d’Amorim 2010
Padrão Recursivo Fold
©André Santos e Marcelo d’Amorim 2010
sum:: [Int] -> Intsum [] = 0sum (a:x) = a + sum x
O que há de diferente entre sum e mult?
sum:: [Int] -> Intsum [] = 0sum (a:x) = a + sum x
Padrão Recursivo Fold
©André Santos e Marcelo d’Amorim 2010
sum:: [Int] -> Intsum [] = 0sum (a:x) = a + sum x
Padrão Recursivo Fold
©André Santos e Marcelo d’Amorim 2010
sum = fold (+) 0mult = fold (*) 1
Exemplo: folding
and :: [Bool] -> Booland = fold (&&) True
concat :: [[t]] -> [t]concat = fold (++) []
maximum :: [Int] -> Intmaximum = fold maxi 0
©André Santos e Marcelo d’Amorim 2010
Exemplo: folding
fold (||) [False, True, True]
fold (++) [“Bom“, “ “, “Dia“]
fold min [6]
fold (*) [1..6]
©André Santos e Marcelo d’Amorim 2010
A função de folding
• Recebe como argumentos:– uma função de acumulação aplicada de
forma incremental aos elementos da lista– um elemento neutro– a lista de entrada
©André Santos e Marcelo d’Amorim 2010
foldr::(t -> u -> u) -> u -> [t] -> u
foldr
foldr f s [] = sfoldr f s (a:as) = f a (foldr f s as)
concat :: [[t]] -> [t]concat xs = foldr (++) [] xs
and :: [Bool] -> Booland bs = foldr (&&) True bs
©André Santos e Marcelo d’Amorim 2010
Padrão Recursivo Filter
©André Santos e Marcelo d’Amorim 2010
evenL :: [Int]-> [Int]evenL [] = []evenL (a:x) | isEven a = a::evenL x | otherwise = evenL x
O que há de diferente entre evenL e gt10L ?
Padrão Recursivo Filter
©André Santos e Marcelo d’Amorim 2010
evenL :: [Int]-> [Int]evenL [] = []evenL (a:x) | isEven a = a::evenL x | otherwise = evenL x
Padrão Recursivo Filter
©André Santos e Marcelo d’Amorim 2010
evenL :: [Int]-> [Int]evenL [] = []evenL (a:x) | isEven a = a::evenL x | otherwise = evenL x
evenL = filter isEven greater10L = filter gt10
Exemplo: filtrando
filter :: (t -> Bool) -> [t] -> [t]filter p [] = []filter p (a:as) | p a = a : filter p as | otherwise = filter p as
digits, letters :: String -> Stringdigits st = filter isDigit stletters st = filter isLetter stevens xs = filter isEven xs where isEven n = (n ‘mod‘ 2 == 0)
©André Santos e Marcelo d’Amorim 2010
Outra definição para filter
filter p l = [a | a <- l, p a]
©André Santos e Marcelo d’Amorim 2010
Exemplo: Biliotecabooks :: Database -> Person -> [Book]books db per = map snd (filter isPer db)where isPer (p,b) = (p == per)
returnLoan :: Database -> Person -> Book -> Database
returnLoan db p b = filter notPB dbwhere notPB pr = (pr /= (p,b))
©André Santos e Marcelo d’Amorim 2010
Exercícios
• Defina as seguintes funções sobre listas– Retornar a soma dos quadrados dos itens (fold)– Maior raiz quadrada de uma lista (map e fold)– Manter na lista todos os itens maiores que
zero (filter)
©André Santos e Marcelo d’Amorim 2010
COMPOSIÇÃO
©André Santos e Marcelo d’Amorim
Composição de funções
• Similar ao comando pipe do Unix (mas ordem diferente)
• Semântica do operador .
©André Santos e Marcelo d’Amorim
(f . g) x = f (g x)
• (f . g) x = f (g x)
Ilustração
u vg f
g >.> f
t
f . g
Exemplo 1
©André Santos e Marcelo d’Amorim
splitWords :: String -> [Word]splitLines :: [Word] -> [Line]fill = splitLines . splitWords
Exemplo 2
• Dado
• Avaliação da expressão(twice succ) 12:= (succ . succ) 12= succ (succ 12)= 14
twice :: (t -> t) -> (t -> t)twice f = f . f
Composição de funções
• Qual o tipo do operador . ?
©André Santos e Marcelo d’Amorim
Composição de funções
• Qual o tipo do operador . ?
©André Santos e Marcelo d’Amorim
(.) :: (b -> c) -> (a -> b) -> (a -> c)
Alta ordem e polimórfica!
Nota
• Aplicação tem bind mais forte que composição
©André Santos e Marcelo d’Amorim
f . g x
(f . g) x
Não é o mesmo que
©André Santos, 1998-2002
Exemplo de Definições
dropSpace = dropWhile (member whitespace)
dropWord = dropWhile (not . member whitespace)
getWord = takeWhile (not . member whitespace)
member st x = elem x st
Pre-definidas...
(+2)(2+)(>2)(3:)(==0)
Exercício
• Escreva a função getEvens usando apenas filter, ==0, mod, e composição.
©André Santos e Marcelo d’Amorim
Exercício
• Escreva a função getEvens usando apenas filter, ==0, mod, e composição.
©André Santos e Marcelo d’Amorim
getEvens = filter ((==0).(‘mod‘ 2))
Explique comportamento...
(++ “\n“)map (+1) >.> filter (>0)double = map (*2)books db per = map snd (filter ((==per).fst db)
Recommended