Programação
Funcional
Generalização em Haskell
7a. Seção de Slides
Hoje
• Funções de mais alta ordem ou funções de ordem superior
(“higher order function”)
• Generalizações de funções
• Polimorfismos
2
Funções como Argumentos
• Assim como números, tuplas e listas, também
funções (já visto nas listas de exercício) podem ser
argumentos para outras funções.
• Funções que recebem outras funções como
argumentos são chamadas de:
funções de mais alta ordem ou
funções de ordem superior
(“higher order function”)
3
Motivação
• Função para retornar uma lista com os elementos
“vezes dois” :
1 .double :: [Int] -> [Int]
2 .double [] = []
3 .double (a:x) = (2*a) : double x
• Função para retornar uma lista com os elementos
"triplicados":
1 .treble :: [Int] -> [Int]
2 .treble [] = []
3 .treble (a:x) = (3*a) : treble x
4
Motivação
1 .double :: [Int] -> [Int]
2 .double [] = []
3 .double (a:x) = (2*a) : double x
1 .treble :: [Int] -> [Int]
2 .treble [] = []
3 .treble (a:x) = (3*a) : treble x
• O padrão (formato) de ambas as definições, é o
mesmo!
• A única coisa que muda é o modo de como os
elementos da lista são transformados (2*a ora 3*a).
5
Relembrando
1 .double :: [Int] -> [Int]
2 .double lista = [2*x | x <- lista]
3 .double [4, 8 .. 31]
[8,16,24,32,40,48,56]
1 .treble :: [Int] -> [Int]
2 .treble lista = [3*x | x <- lista]
3 . treble [4, 8 .. 31]
[12,24,36,48,60,72,84]
A proposta é: “seria possível termos funções que
generalizassem estas definições sobre parâmetros?”
6
Generalizando
• Uma função genérica para transformar listas de
inteiros deveria então ter dois argumentos:
– uma função que especifica a transformação a ser realizada
sobre cada elemento da lista;
– a lista a ser transformada.
• Exemplos de funções de transformação para
elementos (inteiros)...
– Do exemplo anterior teríamos que as funções de
transformação são do tipo:
1 .times2, times3 :: Int -> Int
2 .times2 n = 2*n
3 .times3 n = 3*n
7
Generalizando
• Função genérica para transformar listas de inteiros:
1 .mapInt f [] = []
2 .mapInt f (a:x) = (f a) : mapInt f x
• A função mapInt recebe como argumentos:
– Uma função f que especifica a transformação a ser
realizada em cada elemento da lista;
Mantenha em mente
– E a lista a ser transformada.
estas construções ..
8
Generalizando: outra solução
• Função genérica para transformar listas de inteiros:
1 .mapInt f [] = []
2 .mapInt f (a:x) = (f a) : mapInt f x
• Outra solução - usando “list comprehensions”:
1 .mapInt f lista = [ (f a) | a <- lista]
9
Exemplo
1
2
3
4
.mapInt f [] = []
.mapInt f (a:x) = (f a) : mapInt f x
.
.times2 n = 2*n
Ativando...
mapInt times2 [1,4]
= (times2 1) : mapInt times2 [4]
= 2 : mapInt times2 [4]
= 2 : ((times2 4) : mapInt times2 [])
= 2 : (8 : mapInt times2 [])
= 2 : (8 : [])
= [2,8]
10
Exemplo
1
2
3
4
.mapInt f [] = []
.mapInt f (a:x) = (f a) : mapInt f x
.
.times3 n = 3*n
Ativando...
MapInt times3 [1,4]
= (times3 1) : mapInt times3 [4]
= 3 : mapInt times3 [4]
= 3 : ((times3 4) : mapInt times3 [])
= 3 : (12 : mapInt times3 [])
= 3 : (12 : [])
= [3,12]
11
Redefinindo double e treble
1
2
3
4
5
6
7
8
9
.mapInt f [] = []
.mapInt f (a:x) = (f a) : mapInt f x
.
.times2, times3 :: Int -> Int
.times2 n = 2*n
.times3 n = 3*n
.
. double lista = mapInt times2 lista
. treble lista = mapInt times3 lista
Main> double [1,4]
[2,8]
Main> treble [1,4]
[3,12]
12
Definindo tipos
1 .mapInt :: t1??? -> t2??? -> t3???
2 .mapInt f [] = []
3 .mapInt f (a:x) = (f a) : mapInt f x
• Qual o tipo de mapInt ?
– o primeiro argumento é uma função que transforma um
inteiro em outro inteiro:
(2*Int ou 3*Int, resultando em Int, logo: Int -> Int)
– o segundo argumento é uma lista de inteiros: [Int];
– retorna outra lista de inteiros : [Int].
13
Definindo tipos
1 .mapInt :: (Int->Int) -> [Int] -> [Int]
2 .mapInt f [] = []
3 .mapInt f (a:x) = (f a) : mapInt f x
• Repetindo:
– o primeiro argumento é uma função que transforma um
inteiro em outro inteiro;
– o segundo argumento é uma lista de inteiros;
– retorna outra lista de inteiros.
14
Vantagens
• Ao usar funções de mais alta ordem, consegue-se
mais clareza e simplicidade nas definições.
• Fica mais fácil proceder modificações. Por exemplo,
se for necessário modificar apenas a função de
transformação de elementos.
• Permite reutilização (reusabilidade de código) de
definições. A função mapInt pode ser usada em
muitas outras situações.
15
Exemplo 1
1
2
3
4
5
6
7
sales :: Int -> Int
sales x
| x == 0
= 12
| x == 1
= 20
| x == 2
= 18
| x == 3
= 25
| otherwise
= 0
Função totalSales usa
uma definição
específica para sales.
8 totalSales :: Int -> Int
9 totalSales n
10
| n == 0
= sales 0
11
| otherwise
= totalSales (n-1) + (sales n)
16
Exemplo 1 - generalizando
8 .total :: (Int - > Int) -> Int -> Int
9 .total f n
10. | n==0
= f 0
11. | otherwise
= total f (n-1) +
12.
13.
totalSales n = total sales n
f n
• Contudo, “a genérica”, função total, pode ser usada
em muitas outras situações...
17
Exemplo 1 - generalizando
8 .total :: (Int - > Int) -> Int -> Int
9 .total f n
10. | n==0
= f 0
11. | otherwise
= total f (n-1) + f n
12.
13.totalSales n = total sales n
14.
Calcula a soma
15.sumSquares :: Int -> Int
dos quadrados
16.sumSquares n = total sq n
17.
de 0 a n.
18.sq :: Int -> Int
19.sq x = x*x
É o reuso de código !
18
Exemplo 2
• Soma dos elementos de uma lista de inteiros:
e1 + e2 + ... + ek
• Máximo elemento de uma lista de inteiros:
e1 'maxi' e2 'maxi' ... 'maxi' ek
• Tipos das funções aplicadas a pares de elementos:
(+), 'maxi'
::
Int -> Int -> Int
19
Exemplo 2 - generalizando
1 . foldInt
2 .
3 . foldInt
4 . foldInt
5 . ou
6 . foldInt
7 .
8
9
10 sumList
11
maxList
12 .
:: (Int -> Int -> Int) -> [Int] -> Int
f [a]
f (a:b:x)
= a
= f a (foldInt f (b:x))
f (a:x)
= f a (foldInt f
x)
lista = foldInt (+) lista
lista = folInt maxi lista
20
Detalhando
1 .
lista
2 . maior_da_LISTA lista = reduz maior_de_2
3 . reduz f [a] = a
4 .
reduz f (a : resto) = f a (reduz f resto)
5 .
6 . maior_de_2 x y
| x >= y = x
7 .
| otherwise = y
8
9
10
11 maior_da_LISTA [8,1,7,-3,9,-7]
12 .9
21
Exemplo 3
• Filtrar algarismos/números de um texto:
digits "29 February 1996"
= "291996"
• Filtrar letras de um texto:
letters "29 February 1996"
= "February"
• Tipos das funções aplicadas a cada elemento:
isDigit, isLetter
::
Char -> Bool
22
Exemplo 3 - generalizando
1 . filterString :: (Char -> Bool) -> [Char] -> [Char]
2 .
3 . filterString p [] = []
4 . filterString p (a:x)
5 . | p a
= a : filterString p x
6 . | otherwise
= filterString p x
7 .
8 . isDigit, isLetter :: Char -> Bool
9 . isDigit ch = ('0'<=ch && ch<='9')
10. isLetter ch = ('a'<=ch && ch <='z') ||
11.
('A'<=ch && ch <='Z')
12.
13. digits st = filterString isDigit st
14. letters st = filterString isLetter st
23
Exemplo 3 - outra solução
1 . filterString :: (Char -> Bool) -> [Char] -> [Char]
2 .
3 . filterString p x = [ a | a <- x , p a ]
4 .
5 . isDigit, isLetter :: Char -> Bool
6 . isDigit ch = ('0'<=ch && ch<='9')
7 . isLetter ch = ('a'<=ch && ch <='z') ||
8 .
('A'<=ch && ch <='Z')
9 .
10. digits st = filterString isDigit st
11. letters st = filterString isLetter st
24
Polimorfismo
• Função que calcula o comprimento de uma lista:
1 . length [] = 0
2 . length (a:x) = 1 + length x
• Qual o tipo de length ?
length
::
[t] -> Int
t = variável de tipo
25
Polimorfismo - Exemplo
1 .
2 .
comp_lista []
= 0
comp_lista (_:resto) = 1 + comp_lista resto
Listas> comp_lista [1 .. 20]
20
Listas> comp_lista ['a' .. 'z']
26
Listas> comp_lista ["a" .. "z"]
ERROR - Illegal Haskell 98 class constraint in inferred type
*** Expression : comp_lista (enumFromTo "a" "z")
*** Type
: Enum [Char] => Integer
Listas> comp_lista ["a" , "c",
3
Listas> comp_lista " xxxxxxx "
9
"z"]
26
Outros exemplos de polimorfismo
• Função que calcula o reverso de uma lista:
1 .rev [] = []
2 .rev (a:x) = rev x ++ [a]
• Qual o tipo de rev ?
rev
::
[t] -> [t]
Importante: retorna lista do mesmo tipo
que o argumento de entrada
27
Outros exemplos de polimorfismo
• Função para construir lista de pares:
1 .zip (a:x) (b:y) = (a,b) : zip x y
2 .zip _ _ = []
• Qual o tipo de zip ?
zip
::
[t] -> [u] -> [ (t,u) ]
Importante: os tipos t e u
não estão relacionados!
28
Vantagens
• Ao usar polimorfismo, as definições ficam mais
genéricas;
• As definições podem ser reutilizadas em muitas
situações diferentes;
• Por exemplo, a função length calcula o
comprimento de listas de qualquer tipo;
• Sem polimorfismo, seria necessário criar uma versão
de length para cada tipo de lista a ser utilizada.
29
Conclusões
• Funções de ordem superior exigem abstração,
contudo: elegantes!
• Temos 3 clássicas: reduzir (seleciona um da lista) filtrar
(seleciona nenhum, alguns ou todos), e mapear (sobre todos);
• Ao usar polimorfismo, as definições das funções
ficam mais genéricas: seria necessário criar uma
versão de comp_lista para cada tipo de lista a ser
utilizada.
30