05 funcoes alta ordem

Prévia do material em texto

Uma função de alta ordem (boba)
applyBinOper::(t -> t -> t) -> t -> t -> t
applyBinOper f x y = f x y
Uma função de alta ordem (boba)
applyBinOper::(t -> t -> t) -> t -> t -> t
applyBinOper f x y = f x y
Exemplos:
applyBinOper (+) 10 20 – 30
applyBinOper (*) 10 20 -- 200
applyBinOper (||) True False –- True
applyBinOper (++) “abc” “def” -- “abcdef”
Exemplos
double :: [Int] -> [Int]
double [] = []
double (a:x) = (2*a) : double x
sqrList :: [Int] -> [Int]
sqrList [] = []
sqrList (a:x)= (a*a) : sqrList x
Funções de mapeamento (mapping)
Exemplos
times2 :: Int -> Int
times2 n = 2 * n
sqr :: Int -> Int
sqr n = n * n
Funções de transformação dos elementos
Mapeamento (map)
map :: (t -> u) -> [t] -> [u]
map f [] = []
map f (a:as) = f a : map f as
Mapeamento (map)
map :: (t -> u) -> [t] -> [u]
map f [] = []
map f (a:as) = f a : map f as
doubleList xs = map times2 xs
sqrList xs = map sqr xs
seconds :: [(t,u)] -> [u]
seconds xs = map snd xs
map length [“abc“, “defg“] = ?
Exercícios
• Defina, usando map, uma função que calcula a raiz
quadrada de todos os elementos de uma lista de
números
• Defina uma função posicaoAlfabeto que, dado
um String, devolve uma lista contendo as posições de
cada caractere dessa String no alfabeto ('a' == 1, 'b'
== 2, etc.). Use a função map para resolver essa
questão. Pode ser útil também empregar a função
ord do pacote Data.Char.
• Defina map usando compreensões de listas (sem
recursão)
Mais exemplos
maximum' :: [Int] -> Int
maximum' [a] = a
maximum' (a:as) = max a (maximum' as) 
zeroInRange ::[Int] -> Bool
zeroInRange [] = False
zeroInRange (a:as) = 
 (||) (a==0) (zeroInRange as)
Mais exemplos2
product :: [Int] -> Int
product [] = 1
product (a:as) = (*) a (product as) 
createTree ::[Int] -> Tree Int
createTree [] = NiT
createTree (a:as) = 
 insert a (createTree as)
 -- suponha que insert já foi definida
folding
sumList :: [Int] -> Int 
sumList [] = 0
sumList (a:as) = a + sumList as
e1 + e2 + ... + em
fold :: (t -> t -> t) -> [t] -> t
fold f [a] = a
fold f (a:as) = f a (fold f as)
sumList l = fold (+) l
folding
and :: [Bool] -> Bool
and xs = fold (&&) xs
concat :: [[t]] -> [t]
concat xs = fold (++) xs
maximum :: [Int] -> Int
maximum xs = fold max xs
Mais folding
fold (||) [False, True, True]
fold (++) [“Bom“, “ “, “Dia“]
fold min [6]
fat n = fold (*) [1..n]
foldr::(t -> u -> u) -> u -> [t] -> u 
foldr
foldr f s [] = s
foldr f s (a:as) 
 = f a (foldr f s as)
concat :: [[t]] -> [t]
concat xs = foldr (++) [] xs
and :: [Bool] -> Bool
and bs = foldr (&&) True bs
fold = foldr1 no GHC
Exercícios
• Defina uma função que, dada uma lista de
Strings, devolve o comprimento da maior delas.
 
Use tanto map quanto foldr para resolver a questão.
Exercícios
• Defina uma função que, dada uma lista de
Strings, a transforma em uma lista de números
onde cada número dessa lista corresponde à soma
dos “valores” dos caracteres do String que
aparece na mesma posição da lista de entrada. Os
valores correspondem à posição da letra no alfabeto
('a' = 1, 'b' = 2, 'c' = 3, etc.). A função ord (do
pacote Data.Char) pode ser útil para resolver essa
questão.
 
Use tanto map quanto foldr para resolver a questão.
Exercícios
Defina em Haskell uma função para inserir um
elemento em uma árvore de busca (não precisa ser
balanceada). 
Em seguida, usando foldr, defina uma função que
cria uma árvore a partir de uma lista de números
inteiros e de uma função que insere elementos em uma
árvore:
criarArvore :: 
 Ord t => [t]->(Tree t->t->Tree t)->Tree t
Exemplo: filtrando
digits, letters :: String -> String
filter :: (t -> Bool) -> [t] -> [t]
filter p [] = []
filter p (a:as) 
 | p a = a : filter p as
 | otherwise = filter p as
digits st = filter isDigit st
letters st = filter isLetter st
evens xs = filter isEven xs
 where isEven n = (n ‘mod‘ 2 == 0)
Outra definição para filter
filter p l = [a | a <- l, p a]
Exercícios
• Defina uma função para, dada uma lista
de inteiros, remove da lista todos os
elementos que não sejam primos. Sua
solução deve empregar filter.
Exercícios
• Defina uma função para, dada uma lista
de listas de inteiros, remover da lista
todas as listas cujas somas dos elementos
são menores que um certo valor, também
fornecido como argumento. Use filter 
e foldr para resolver esta questão.
• (f . g) x = f (g x)
A função de composição
u vg f
t
f . g
A função de composição
(.) :: (u -> v) -> (t -> u) -> 
 (t -> v)
(.) f g x = f (g x)
==
(.) f g = \x -> f (g x)
:type (.)
(.)::(b->c)->(a->b)->a->c 
Composição de funções
• Estruturar programas compondo funções
fill :: String -> [Lines]
fill s = splitLines (splitWords s)
splitWords :: String -> [Word]
splitLines :: [Word] -> [Line]
fill = splitLines . splitWords
Funções como valores e
resultados
• twice :: (t -> t) -> (t -> t)
twice f = f . f
• (twice succ) 12
= (succ . succ) 12
= succ (succ 12)
= 14
Funções como valores e
resultados
iter :: Int -> (t -> t) -> (t -> t)
iter 0 f = id
iter n f = (iter (n-1) f).f
(iter 10 double) 3
Exercícios
• Implemente uma função mapfilter que, sem usar
map nem filter, comporte-se como a função
map.filter
Expressões que definem funções
• addNum :: Int -> (Int -> Int)
addNum n = h
 where 
 h m = n + m
• Notação Lambda
\m -> 3+m
addNum n = (\m -> n+m)
 comp2
\x y -> g (f x) (f y)
y
 f 
 f g 
g (f x) (f y)
x
-- qual o tipo da função abaixo?
comp2 f g = (\x y -> g (f x) (f y))
comp2 :: (t -> u) -> (u -> u -> v) -> 
 (t -> t -> v)
Exercício
• Dada uma função f do tipo t -> u ->
v, defina uma expressão da forma 
(\... -> ...) 
 para uma função do tipo u -> t -> v 
que se comporta como f mas recebe seus
argumentos na ordem inversa
Exercício
Defina, usando lambdas, funções para
• Dada uma lista de pares, devolver uma lista contendo apenas
os primeiros elementos de cada par
• Dados uma lista de listas de números e um número n, devolver
uma lista contendo todas cujo comprimento seja maior que n
• Dada uma lista de listas, criar uma lista que contém todos os
elementos das sub-listas da lista de entrada, mas removendo
duplicação:
Prelude> f [[1..10], [5..20], [6, 8.. 15]]
[1,2,3,4,5,7,9,11,13,15,16,17,18,19,20,6,8,10,12,14]
Exercícios
• Implemente uma função mapfold que, sem usar map 
nem foldr, comporte-se como a função
map.foldr
Em seguida, implemente uma função que pega a lista l 
produzida como resultado de uma aplicação de
mapfold e, dada uma lista m de elementos de um tipo
tão genérico quando possível, aplica os elementos de l a
m. 
f i = foldr (\x y -> ([a | a <- x, (length [b | b <-y, a == b] == 0)]) ++ y) [] i
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34