Programação Programação FuncionalFuncional

8a. Seção de Slides

Generalização em HaskellGeneralização em Haskell(2a. Parte)(2a. Parte)

2

Polimorfismo e Ordem Mais Alta• Importantes funções que são polimórficas e de

ordem mais alta, simultaneamente:– map (mapear: aplicar sobre) : uma lista L2 é criada a

partir de uma lista L1, aplicando uma operação sobre cada elemento de L1;

– fold (redução) : um valor é calculado, resultado da aplicação de uma operação binária ao longo de toda uma lista de elementos;

– filter (filtrar): uma lista L2 é criada a partir de uma lista L1, selecionando alguns elementos de L1 que satisfazem a uma determinada propriedade.

• As funções map , fold e filter não impõem qualquer restrição sobre os tipos envolvidos.

3

Map (aplicar sobre: mapear)

• Uma lista L2 é criada a partir de uma lista L1, aplicando uma operação sobre cada elemento de L1.

• Não há restrição sobre o tipo dos elementos de L1, que ainda pode ser diferente do tipo dos elementos de L2.

L1 = [ e1 , e2 , ... , ek ]

L2 = [ f(e1) , f(e2) , ... , f(ek) ]

f f f

4

Map (aplicar sobre: mapear)

Main> map times2 [2,3,4][4,6,8]Main> map times3 [2,3,4][6,9,12]

Main> map times2 [2,3,4][4,6,8]Main> map times3 [2,3,4][6,9,12]

1 .2 .3 .

1 .2 .3 .

times2, times3 :: Int -> Inttimes2 n = 2*ntimes3 n = 3*n

5

Map (aplicar sobre: mapear)1 .2 .3 .4 .

1 .2 .3 .4 .

isEven :: Int -> BoolisEven n | n `mod` 2 == 0 = True | otherwise = False

6

Map (aplicar sobre: mapear)

Main> map isEven [2,3,4][True,False,True]

Main> map isEven [2,3,4][True,False,True]

1 .2 .

1 .2 .

isEven :: Int -> BoolisEven n = (n `mod` 2 == 0)

7

Map (aplicar sobre: mapear)

Main> map small "ABC Esporte Clube""abc esporte clube"

Main> map small "ABC Esporte Clube""abc esporte clube"

1 .2 .3 .4 .5 .6 .

1 .2 .3 .4 .5 .6 .

offset = ord 'a' - ord 'A'isCapital ch = (ch >= 'A') && (ch <= 'Z')small :: Char -> Charsmall ch | isCapital ch = chr (ord ch + offset) | otherwise = ch

8

Map (aplicar sobre: mapear)

Main> map length ["ABC","Esporte","Clube"][3,7,5]Main> map length [2,3,4]ERRO DE TIPO!!!

Main> map length ["ABC","Esporte","Clube"][3,7,5]Main> map length [2,3,4]ERRO DE TIPO!!!

1 .2 .

1 .2 .

length [] = 0length (a:x) = 1 + length x

9

Map (aplicar sobre: mapear)

1 .2 .3 .

1 .2 .3 .

map :: (t -> u) -> [t] -> [u]map f [] = []map f (a:x) = f a : map f x

1 .2 .

1 .2 .

map :: (t -> u) -> [t] -> [u]map f l = [ f a | a <- l ]

• Definição:

• Alternativa:

10

Fold (“dobrar”, redução, resumir)

• Um valor é calculado, resultado da aplicação de uma operação binária ao longo de toda uma lista de elementos.

• Não há restrição sobre o tipo dos elementos da lista.

fold f [ e1 ] = e1

fold f [ e1 , e2 , ... , ek ]= e1 `f` (e2 `f` (... `f` ek) ...)= f e1 (fold f [ e2 , ... , ek ])

11

Fold (“dobrar”, redução, resumir)

Main> fold (+) [1..3]6Main> fold (||) [False,True,False]TrueMain> fold (++) ["ABC"," Esporte", " ", "Clube"]"ABC Esporte Clube"Main> fold (-) [1..3]2

Main> fold (+) [1..3]6Main> fold (||) [False,True,False]TrueMain> fold (++) ["ABC"," Esporte", " ", "Clube"]"ABC Esporte Clube"Main> fold (-) [1..3]2

12

Main> fold maxi [2,4,3]4Main> fold maxi [2]2Main> fold maxi []ERRO!!!

Main> fold maxi [2,4,3]4Main> fold maxi [2]2Main> fold maxi []ERRO!!!

1 .2 .3 .4 .

1 .2 .3 .4 .

maxi :: Int -> Int -> Intmaxi a b | a > b = a | otherwise = b

Fold (“dobrar”, redução, resumir)

13

1 .2 .3 .

1 .2 .3 .

fold :: (t -> t -> t) -> [t] -> tfold f [a] = afold f (a:b:x) = f a (fold f (b:x))

• Definição:

• Mas os tipos da definição podem ser mais gerais...• Qual a restrição sobre o tipo da operação f que será executada ao longo da lista?

Fold (“dobrar”, redução, resumir)

14

Fold (“dobrar”, redução, resumir)

fold f [ e1 , e2 , ... , ek ]= e1 `f` (e2 `f` (... `f` ek) ...)= f e1 (fold f [ e2 , ... , ek ])

tipo do primeiro argumento de f tem que ser t

tipo do segundo argumento de f tem que ser o mesmo do valor de

retorno de fold

• Supondo uma lista [e1,...,ek] de tipo [t] :

15

Fold (“dobrar”, redução, resumir)

fold f [ e1 , e2, e3 ]= f e1 (fold f [ e2 , e3 ])= f e1 (f e2 (fold f [ e3 ]))= f e1 (f e2 e3)

tipo do valor de retorno de f deve ser o mesmo tipo do segundo argumento de f

• Supondo uma lista [e1,...,ek] de tipo [t] :

16

Fold (“dobrar”, redução, resumir)

• Restrições:– tipo do primeiro argumento de f tem que ser t, o tipo dos elementos da lista.– tipo do segundo argumento de f tem que ser o mesmo tipo do valor de retorno de fold.

– tipo do valor de retorno de f deve ser o mesmo tipo do segundo argumento de f.

1 .2 .3 .

1 .2 .3 .

fold :: (t -> u -> u) -> [t] -> ufold f [a] = afold f (a:b:x) = f a (fold f (b:x))

17

Fold (“dobrar”, redução, resumir)

1 .2 .3 .4 .5 .

1 .2 .3 .4 .5 .

fold1 :: (t -> u -> u) -> u -> [t] -> ufold1 f s [] = sfold1 f s (a:x) = f a (fold1 f s x)

sumListInt l = fold1 (+) 0 l

• Acrescentando um argumento a fold:

Main> sumListInt [1..3]6Main> sumListInt [3]3Main> sumListInt []0

Main> sumListInt [1..3]6Main> sumListInt [3]3Main> sumListInt []0

18

Filter (Filtrar)

• Uma lista L2 é criada a partir de uma lista L1, selecionando alguns elementos de L1 que satisfazem a uma determinada propriedade.

• Não há restrição sobre o tipo dos elementos de L1, mas é o mesmo tipo dos elementos de L2.

L1 = [ e1 , e2 , ... , ek ]

L2 = [ e1 , e2 , ... , ek ]

p? ok p? não p? ok

19

Filter (Filtrar)

• Supondo uma lista [e1,...,ek] de tipo [t] , a propriedade p que é aplicada aos elementos da lista é do tipo:

t -> Bool

L1 = [ e1 , e2 , ... , ek ]

L2 = [ e1 , e2 , ... , ek ]

p? ok p? não p? ok

20

Filter (Filtrar)

Main> filter isEven [1..6][2,4,6]

Main> filter isEven [1..6][2,4,6]

1 .2 .

1 .2 .

isEven :: Int -> BoolisEven n = (n `mod` 2 == 0)

21

Filter (Filtrar)

Main> filter nonEmpty ["ABC","","Esporte Clube"]["ABC","Esporte Clube"]

Main> filter nonEmpty ["ABC","","Esporte Clube"]["ABC","Esporte Clube"]

1 .2 .

1 .2 .

nonEmpty :: String -> BoolnonEmpty st = (st /= "")

22

Filter (Filtrar)

1 .2 .3 .4 .5 .

1 .2 .3 .4 .5 .

filter :: (t -> Bool) -> [t] -> [t]filter p [] = []filter p (a:x) | p a = a : filter p x | otherwise = filter p x

• Definição:

1 .2 .

1 .2 .

filter :: (t -> Bool) -> [t] -> [t]filter p l = [ a | a <- l, p a ]

• Alternativa: