funcoes_ordem_superior

Prévia do material em texto

Programação Funcional
Aula 6 - Funções de Ordem Superior
Wladimir Araújo Tavares 1
1Universidade Federal do Ceará - Campus de Quixadá
24 de março de 2020
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 1 / 9
Funções de ordem superior
Uma função é de ordem superior se ela tem um argumento que é uma
função ou seu resultado é uma função.
1 twice :: (a -> a) -> a -> a
2 twice f x = f (f x)
3
4 curry :: ((a, b) -> c) -> a -> b -> c
5 curry f = \x y -> f (x, y)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 2 / 9
Função map
A função map aplica uma função a cada elemento duma lista.
1 map :: (a -> b) -> [a] -> [b]
Exemplos:
1 > map (+1) [1,3,5,7]
2 [2,4,6,8]
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 3 / 9
Função map
Podemos definir map usando a definição de lista por compreensão:
1 map f xs = [f x | x<-xs]
Também podemos definir map usando recursão:
1 map f [] = []
2 map f (x:xs) = f x : map f xs
Esta última forma será útil para provar propriedades usando indução.
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 4 / 9
Função map
Podemos definir map usando a definição de lista por compreensão:
1 map f xs = [f x | x<-xs]
Também podemos definir map usando recursão:
1 map f [] = []
2 map f (x:xs) = f x : map f xs
Esta última forma será útil para provar propriedades usando indução.
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 4 / 9
Função map
Podemos definir map usando a definição de lista por compreensão:
1 map f xs = [f x | x<-xs]
Também podemos definir map usando recursão:
1 map f [] = []
2 map f (x:xs) = f x : map f xs
Esta última forma será útil para provar propriedades usando indução.
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 4 / 9
Função foldr
Muitas funções sobre listas seguem o seguinte padrão de definição
recursiva:
f [] = v
f (x:xs) = x ⊕ f xs
Ou seja, f transforma:
a lista vazia em v;
a lista não-vazia x : xs usando uma operação ⊕ para combinar x
com f xs.
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 5 / 9
Função foldr
A função foldr transforma uma lista usando uma operação associada à
direita (“fold right”):
foldr (⊕) v [x1, x2, . . . , xn] = x1 ⊕ (x2 ⊕ (. . . (xn ⊕ v) . . .))
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 6 / 9
Definição recursiva da função foldr
Definição recursiva do foldr
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 7 / 9
Exemplo sum
Defina uma função sum :: [Int] - > Int tal que (sum xs) devolve a
soma dos elementos da lista xs. Por Exemplo,
> sum [1,2,3]
6
Definição recursiva:
sum [] = 0 v = 0
sum (x:xs) = x + sum xs ⊕ = +
Definição usando foldr:
sum xs = foldr (\x z-> x + z) 0 xs
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 8 / 9
Exerćıcio
Defina uma função inserir :: Ord a => a -> [a] -> [a] tal que
(inserir x xs) recebe um elemento x e uma lista ordenada de maneira
crescente devolvendo uma lista ordenada ascendentemente, oriunda da
inserção apropriada de x em xs. Por exemplo,
inserir 3 [2,7,12] == [2,3,7,12]
Wladimir Araújo Tavares (UFC) Programação Funcional Aula 6 - Funções de Ordem Superior24 de março de 2020 9 / 9