Aula 20

assuma a seguinte funcao

soma1 :: (Num b) => a -> [(a,b)] -> [(a,b)]

soma1: soma 1 no valor (b) associado a chave (a) num dicionario implementado como uma lista de duplas (a,b) (chave,valor)

Implemente a funcao

maisfreq :: (Num b) => [a] -> (a,b)

que retorna uma tupla (chave, valor) com a chave mais frequente na lista [a] e o numero de vezes que ela aparece.

Solucao:

maisfreq :: (Eq a, Ord b, Num b) => [a] -> (a,b)
maisfreq l = maior $ montadic [] l

maior :: (Ord b) => [(a,b)] -> (a,b)
maior (x:xs) = maior' x xs
   where 
      maior' (ch,val) ((a,b): xs) 
         | val > b = maior' (ch,val) xs 
         | otherwise = maior' (a,b) xs  

montadic (Eq a, Num b) => [a] -> [(a,b)]
montadic dic [] = dic
montadic dic (x:xs) =  montadic (soma1 x dic) xs

soma1 :: (Eq a, Numb b) => a -> [(a,b)] -> [(a,b)]
soma1 ch [] = [(ch,1)]
soma1 ch ((a,b):xs) 
     | ch==a = (a,b+1) : xs            
     | otherwise = (a,b) : soma1 ch xs

map:

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

map (-20) [30,10,20,40]

filter

filter :: (a -> Bool) -> [a] -> [a]
filter _ [] = []
filter f (x:xs) 
   | f x = x : filter f xs 
   | otherwise =  filter xs

zipWith (map de 2 listas)

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith _ [] _ = []
zipWith _ _  [] = []
zipWith f (x:xs) (y:ys) = f x y : zipWith f xs ys

\x -> x + 4

\x y -> if x<y then y+1 else x*y

"fold" (+) [1,2,3,4,5]
=> 1+2+3+4+5

"fold" (-) [1,2,3,4,5]
=> 1-2-3-4-5   ???

foldr ->  1 - (2 - (3 - (4 - ( 5 - init)))

foldl -> (((init - 1) - 2) - 3) - 4) - 5

ver figura

foldl funcao\_combinacao valor\_inicial lista

passeia pela lista da esquerda para a direita, combinando o acumulador com o valor na lista. A funcao retorna o novo acumulador, Valor\_inical é o primeiro acumulados

foldr f init [] = init
foldr f init (X:xs) = f x (foldr f init xs)

foldl f init [] = init
foldl f init (x:xs) = foldl f (f init x) xs

soma l = foldl (\acc x -> x+acc) 0 l

map' f  l = foldr (\x acc -> f x : acc) [] l

Diferenças entre foldl e foldr (e ha um foldl') pagina

Foldr pode nao percorrer a lista toda:

tempar l = foldr (\x a -> if even x then True else a) False l
tempar [3,5,7,6,5]++[101,103..]

a funcao de combinacao em algumas situacoes nao usa o acumulador/valor inicial / valor que "vem vindo" da direita!

(f . g) x = f (g x)
tambem:
(f . g) x = f $ g x

(f . g . h) x = f ( g (h x))

f x = .... x

pode ser escrito como

f = ....

exemplo

maior l = foldl1 (\a x = if a>x then a else x) l

maior = foldl1 (\a x = if a>x then a else x)

makeneg = negate . abs

• implemente o soma1 e a lista 10 usando folds
• implemente os exercicios de matrizes (lista de linhas) do Lisp em haskell