Funções de Alta Ordem

Playlists

1 Funções como tipos

  • Em Haskell, podemos pensar em uma função como um tipo de dado. Esse tipo tanto pode ser utilizado como argumento de entrada assim como o argumento de saída da função.
  • Para perceber isso, considere a seguinte função que soma dois números:
soma :: Int -> Int -> Int
soma x y = x+y
  • Podemos reescrever a assinatura da função explicitando os parênteses nos tipos:
soma :: Int -> (Int -> Int)
soma x y = x+y
  • Isso significa que a função soma recebe um argumento do tipo inteiro e retorna uma função que recebe um argumento do tipo inteiro e retorna um inteiro.
soma :: Int -> (Int -> Int)
soma x y = x+y
  • Ou seja, o tipo da saída da função é uma função Int -> Int.
soma :: Int -> (Int -> Int)
soma x y = x+y
  • Dessa forma, no código abaixo, soma3 se torna uma função que recebe um valor inteiro e soma 3 a esse valor:
soma3 = soma 3
soma3 2

Saída:


5

1.1 Aplicação Parcial

  • Isso é chamado de aplicação parcial e pode ser utilizado em qualquer função com mais do que um argumento:
soma3 = (+3)
soma3 2

Saída:


5

Outro exemplo:

dobra = (*2)
print (dobra 2)

Saída:


4

2 Funções de alta ordem

  • Vimos anteriormente que o Haskell permite que passemos funções como argumento:
duasVezes :: (a -> a) -> a -> a
duasVezes f x = f (f x)
  • Essas funções são aplicáveis em diversas situações:
> duasVezes (*2) 3
12

> duasVezes reverse [1,2,3]
[1,2,3]
  • Além disso podemos fazer uma aplicação parcial da função, com apenas um argumento, para gerar outras funções:
quadruplica = duasVezes (*2)

2.1 Funções de alta ordem

  • As funções que…
    • recebem uma ou mais funções como argumento, ou
    • devolvem uma função
  • … são denominadas funções de alta ordem (_ high order functions _).
  • O uso de funções de alta ordem permite aumentar a expressividade do Haskell quando confrontamos padrões recorrentes.

2.2 Funções de alta ordem para listas

  • Considere o padrão:

    [f x | x <- xs]

  • Que é muito comum quando queremos gerar uma lista de números ao quadrado, somar um aos elementos de uma lista, etc.

2.3 Map

  • Podemos definir a função map como:

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

  • Uma função que transforma uma lista do tipo a para o tipo b utilizando uma função f :: a -> b.

  • Com isso temos uma visão mais clara das transformações feitas em listas: 
    > map (+1) [1,2,3]
[2,3,4]

> map even [1,2,3]
[False, True, False]

> map reverse ["ola", "mundo"]
["alo", "odnum"]
  • map funciona para listas genéricas, de qualquer tipo.
  • map também funciona para qualquer função f :: a -> b
  • Logo, ela pode ser aplicada a ela mesma, ou seja, aplicável em listas de listas
> map (map (+1)) [[1,2],[3,4]]
   => [ map (+1) xs | xs <- [[1,2],[3,4]] ]
   => [ [x+1 | x <- xs] | xs <- [[1,2],[3,4]] ]
  • Uma definição recursiva de map é dada como:
map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

2.4 Filter

  • Outro padrão recorrente observado é a filtragem de elementos utilizando guards nas listas:
> [x | x <- [1..10], even x]
[2,4,6,8,10]

> [x | x <- [1..10], primo x]
[2,3,5,7]
  • Podemos definir a função de alta ordem filter da seguinte forma:
filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]
  • filter devolve uma lista de todos os valores cujo o predicado p de x devolve True.
  • Reescrevendo os exemplos anteriores:
> filter even [1..10]
[2,4,6,8,10]

> filter primo [1..10]
[2,3,5,7]
  • Podemos passar funções parciais também como argumento:
> filter (>5) [1..10]
[6,7,8,9,10]

> filter (/= ' ') "abc def ghi"
"abcdefghi"

Porque o exemplo acima (>5) funciona?

  • Da mesma forma que map podemos definir filter recursivamente como:
filter :: (a -> Bool) -> [a] -> [a]
filter p []                 = []
filter p (x:xs) | p x       = x : filter p xs
		| otherwise = filter p xs

2.5 Map e Filter

  • As duas funções map e filter costumam serem utilizadas juntas, assim como na compreensão de listas:
somaQuadPares :: [Int] -> Int
somaQuadPares ns = sum [n^2 | n <- ns, even n]

somaQuadPares :: [Int] -> Int
somaQuadPares ns = sum (map (^2) (filter even ns))

2.6 Operador pipe

  • Podemos utilizar o operador $ para separar as aplicações das funções e remover os parênteses:
> :t ($)
($) :: (a -> b) -> a -> b

somaQuadPares :: [Int] -> Int
somaQuadPares ns = sum
		 $ map (^2)
		 $ filter even ns
  • Diferentemente do pipe do Unix, no nosso caso a execução é de baixo para cima.

2.7 Outras funções de alta ordem

  • Outras funções úteis durante o curso:
> all even [2,4,6,8]
True

> any odd [2,4,6,8]
False

> takeWhile even [2,4,6,7,8]
[2,4,6]

> dropWhile even [2,4,6,7,8]
[7,8]

3 Folding

3.1 Função foldr

  • Vamos recapitular algumas das funções recursivas da aula anterior:
sum []     = 0
sum (x:xs) = x + sum xs

product []     = 1
product (x:xs) = x * product xs

length []     = 0
length (_:xs) = 1 + length xs
  • Podemos generalizar essas funções da seguinte forma:
f [] = v
f (x:xs) = g x (f xs)
  • Essa função é chamada de foldr:
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
  • O nome dessa função significa dobrar, pois ela justamente dobra a lista aplicando a função f em cada elemento da lista e um resultado parcial.
foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)
  • Pense nessa lista não-recursivamente a partir da definição de listas:
a1 : (a2 : (a3 : []))
  • Trocando : pela função f e [] pelo valor v:
a1 `f` (a2 `f` (a3 `f` v))

Ou seja:

foldr (+) 0 [1,2,3]

se torna:

1 + (2 + (3 + 0))

Que é nossa função sum:

sum = foldr (+) 0

3.2 Exercício 1

  • Defina product utilizando foldr.

3.3 Exercício 1 - Solução

product = foldr (*) 1

3.4 Função length

  • Como podemos implementar length utilizando foldr?
length :: [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

Para a lista:

1 : (2 : (3 : []))

devemos obter:

1 + (1 + (1 + 0))

Da assinatura de foldr:

foldr :: (a -> b -> b) -> b -> [a] -> b

Percebemos que na função f o primeiro argumento é um elemento da lista e o segundo é o valor acumulado.

  • Dessa forma podemos utilizar a seguinte função anônima:
length = foldr (\_ n -> n + 1) 0

length = foldr (+1) 0 funciona?

3.5 Exercício 2

  • Reescreva a função reverse utilizando foldr:
reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

3.6 Exercício 2 - Solução

1 : (2 : (3 : []))
  => (([] ++ [3]) ++ [2]) ++ [1]

snoc x xs = xs ++ [x]
reverse = foldr snoc []

3.7 Folding caudal

  • Na aula sobre recursão, implementamos muitas dessas funções em sua versão caudal:
sum :: Num a => [a] -> a
sum ns = sum' 0 ns
  where
    sum' v []     = v
    sum' v (x:xs) = sum' (v+x) xs

3.8 Função foldl

  • Esse padrão é capturado pela função foldl:
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []     = v
foldl f v (x:xs) = foldl f (f v x) xs
  • Da mesma forma podemos pensar em foldl não recursivamente invertendo a lista:
1 : (2 : (3 : []))
  => (([] : 1) : 2) : 3
  => ((0 + 1) + 2) + 3

Quando f é associativo, ou seja, os parênteses não fazem diferença, a aplicação de foldr e foldl não se altera:

sum = foldl (+) 0

product = foldl (*) 1

3.9 Função length

  • Como ficaria a função length utilizando foldl?
length = foldr (\_ n -> 1+n) 0
length = foldl (??) 0
  • Basta inverter a ordem dos parâmetros:
length = foldr (\_ n -> n + 1) 0
length = foldl (\n _ -> n + 1) 0

3.10 Função reverse

  • E a função reverse?

3.11 Resposta

1 : (2 : (3 : []))
  => (([] `f` 3) `f` 2) `f` 1

f xs x = ???
reverse = foldl f []

1 : (2 : (3 : []))
  => (([] f 3) f 2) f 1

f xs x = x:xs
reverse = foldl f []

-- ou se quiser usar uma lambda
reverse = foldl (\xs x -> x:xs) []

3.12 O que eu uso? foldr ou foldl

  • A escolha entre foldr e foldl, quando é possível escrever uma função utilizando qualquer um dos dois, é feita após um estudo cuidadoso sobre o desempenho das duas versões.

  • Esse tipo de análise nem sempre é trivial e será discutida no final do curso.

  • Por enquanto, utilizaremos um exemplo para mostrar a razão desta discussão.

3.13 Exercício 3

  • Dada a definição do operador &&:
(&&) False _ = False
(&&) _ False = False
(&&) _ _ = True
  • Expanda as seguintes expressões:
foldl (&&) False [False, False, False, False]
foldr (&&) False [False, False, False, False]

3.14 Exercício 3 - Solução

(&&) False _ = False
(&&) _ False = False
(&&) _ _ = True

foldl:

> False : (False : (False : (False : [])))
    => ((([] : False) : False) : False) : False
    => ((([] && False) && False) && False) && False
    => ((False && False) && False) && False
    => (False && False) && False
    => False && False
    => False

(&&) False _ = False
(&&) _ False = False
(&&) _ _ = True

foldr:

> False : (False : (False : (False : [])))
  => False && (False && (False && (False && [])))
  => False

3.15 foldr vs foldl

Uma regra do dedão para trabalharmos por enquanto é:

  • Se a lista passada como argumento é infinita, use foldr
  • Se o operador utilizado pode gerar curto-circuito, use foldr
  • Se a lista é finita e o operador não irá gerar curto-circuito, use foldl
  • Se faz sentido trabalhar com a lista invertida, use foldl
  • Bônus! E temos ainda uma outra função chamada foldl' que aprenderemos mais para frente.

4 Composição de funções

  • Na matemática a composição de função \(f \circ g\) define uma nova função \(z\) tal que \(z(x) = f(g(x))\).

  • No Haskell temos o operador (.):

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)
  • A assinatura da função (.) merece um pouco mais de atenção
  • Dada uma função que mapeia do tipo b para o tipo c, e outra que mapeia do tipo a para o tipo b, gere uma função que mapeie do tipo a para o tipo c.
(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

4.1 Propriedades da composição

  • A composição de função é associativa:
(f . g) . h == f . (g . h)
  • Temos também um elemento neutro que é a função id:
f . id = id . f = f
  • Essas duas propriedades são importantes durante a construção de programas, pois elas permitem o uso do foldr (dentre outras funções de alta ordem):
-- cria uma função que é a composição de uma lista
-- de funções
compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

4.2 Exemplo do uso de composição

-- A função fn
fn x = ceiling (negate (tan (cos (max 50 x))))
-- Pode ser reescrita
fn = ceiling . negate . tan . cos . max 50

somaDosQuadradosImpares :: Integer
somaDosQuadradosImpares =
  sum (takeWhile (<10000) (filter odd (map (^2) [1..])))
-- ou
somaDosQuadradosImpares =
  sum . takeWhile (<10000) . filter odd . map (^2) $ [1..]
-- ou
somaDosQuadradosImpares =
     let oddSquares = filter odd $ map (^2) [1..]
	 belowLimit = takeWhile (<10000) oddSquares
     in  sum belowLimit
  • Quando em dúvida sobre qual usar se o desempenho for o mesmo opte pela versão mais legível.

4.3 ($) vs. (.)

> :t ($)
($) :: (a -> b) -> a -> b
> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c
  • Observe o código abaixo
f x = sin $ abs x
g = sin . abs
h x = (sin . abs) x
i x = sin . abs $ x

Quais são os tipos de f, g, h e i?

5 Disclaimer

Estes slides foram preparados para os cursos de Paradigmas de Programação e Desenvolvimento Orientado a Tipos na UFABC.

Este material pode ser usado livremente desde que sejam mantidos, além deste aviso, os créditos aos autores e instituições.