Playlists
Um Monoid é um conjunto de valores associados a um operador binário associativo e um elemento identidade:
+
e o elemento 0*
e o elemento 1++
e o elemento ’’''A classe Monoid é definida como:
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
mconcat = foldr mappend mempty
Para listas temos a seguinte instância de Monoid:
instance Monoid [a] where
mempty = []
mappend = (++)
Para o tipo Maybe podemos definir:
instance Monoid a => Monoid (Maybe a) where
mempty = Nothing
Nothing `mappend` my = my
mx `mappend` Nothing = mx
Just x `mappend` Just y = Just (x `mappend` y)
a
é um Monoid, podemos definir:fold :: Monoid a => [a] -> a
fold [] = mempty
fold (x:xs) = x `mappend` fold xs
Essa generalização pode ser feita para outras estruturas:
data Tree a = Leaf a | Node (Tree a) (Tree a)
deriving Show
fold :: Monoid a => Tree a -> a
fold (Leaf x) = x
fold (Node l r) = fold l `mappend` fold r
Podemos então criar a classe dos “dobráveis”:
class Foldable t where
fold :: Monoid a => t a -> a
foldMap :: Monoid b => (a -> b) -> t a -> b
foldr :: (a -> b -> b) -> b -> t a -> b
foldl :: (a -> b -> a) -> a -> t b -> a
Considere os seguintes tipos:
newtype Sum a = Sum a
deriving (Eq, Ord, Show, Read)
newtype Product a = Product a
deriving (Eq, Ord, Show, Read)
getSum :: Sum a -> a
getSum (Sum x) = x
getProd :: Product a -> a
getProd (Product x) = x
Considere os seguintes Monoids:
instance Num a => Monoid (Sum a) where
mempty = Sum 0
Sum x `mappend` Sum y = Sum (x+y)
instance Num a => Monoid (Product a) where
mempty = Product 1
Product x `mappend` Product y = Product (x*y)
Para efetuar a somatória e produtória de uma lista de números basta fazer:
getSum (foldMap Sum [1..10])
Saída:
getProduct (foldMap Product [1..10])
Saída:
Se definirmos a instância de Foldable
para o tipo Tree
, bastaria
fazer:
> getSum (foldMap Sum arvore)
> getProd (foldMap Prod arvore)
As funções são as mesmas!!!
A classe Foldable também define por padrão diversas funções auxiliares:
null :: t a -> Bool
length :: t a -> Int
elem :: Eq a => a -> t a -> Bool
maximum :: Ord a => t a -> a
minimum :: Ord a => t a -> a
sum :: Num a => t a -> a
product :: Num a => t a -> a
toList :: t a -> [a]
foldMap
Implemente toList
utilizando foldMap
.
toList :: t a -> [a]
Foldable
em uma lista!foldMap
para a instância e todo o
resto vem por padrão (mas nem sempre eficiente).Implemente toList
utilizando foldMap
:
toList = foldMap (x -> [x])
Considere a função:
average :: [Int] -> Int
average ns = sum ns `div` length ns
Ela agora pode ser generalizada para:
average :: Foldable t => t Int -> Int
average ns = sum ns `div` length ns
E agora podemos fazer:
> average (Node (Leaf 1) (Leaf 3))
2
duas vezes, uma para calcular o resultado de sum
e outra para
calcular o resultado de length
:
> average (Node (Leaf 1) (Leaf 3))
2
average :: Foldable t => t Double -> Double
average xs = getSum soma / getSum contagem
where (soma, contagem) = foldMap (\x -> (Sum x, Sum 1.0)) xs
foldMap (\x -> (Sum x, Sum 1.0, Prod x, And (x>0))) xs
Fold
:{-# LANGUAGE ExistentialQuantification #-}
import Data.Monoid
import Prelude hiding (sum)
import Data.Foldable (foldl')
data Fold i o = forall m . Monoid m => Fold (i -> m) (m -> o)
fold :: Fold i o -> [i] -> o
fold (Fold toMonoid summarize) is = summarize (foldl' (<>) mempty (map toMonoid is))
Baseado na palestra Beautiful Folds
sum'
como:sum' :: Num n => Fold n n
sum' = Fold Sum getSum
E agora podemos fazer:
fold sum' [1..10]
Saída:
fold sum [1, 2, 3, 4]
é expandida para:-- sum = Fold Sum getSum
= fold (Fold Sum getSum) [1, 2, 3, 4]
-- fold (Fold tally summarize) is = summarize (reduce (map tally is))
= getSum (reduce (map Sum [1, 2, 3, 4]))
-- reduce = foldl' (<>) mempty
= getSum (foldl' (<>) mempty (map Sum [1, 2, 3, 4]))
= getSum (foldl' (<>) mempty [Sum 1, Sum 2, Sum 3, Sum 4])
-- `foldl' (<>) mempty`
= getSum (mempty <> Sum 1 <> Sum 2 <> Sum 3 <> Sum 4)
-- mempty = Sum 0
= getSum (Sum 0 <> Sum 1 <> Sum 2 <> Sum 3 <> Sum 4)
-- Sum x <> Sum y = Sum (x + y)
= getSum (Sum 10)
-- getSum (Sum x) = x
= 10
Data.Monoid
pode ser escrito utilizando Fold
:import Prelude hiding (head, last, all, any, sum, product, length)
head :: Fold a (Maybe a)
head = Fold (First . Just) getFirst
last :: Fold a (Maybe a)
last = Fold (Last . Just) getLast
all :: (a -> Bool) -> Fold a Bool
all predicate = Fold (All . predicate) getAll
any :: (a -> Bool) -> Fold a Bool
any predicate = Fold (Any . predicate) getAny
sum :: Num n => Fold n n
sum = Fold Sum getSum
product :: Num n => Fold n n
product = Fold Product getProduct
length :: Num n => Fold i n
length = Fold (\_ -> Sum 1) getSum
Fold
s basta fazer:(<+>) :: Fold i a -> Fold i b -> Fold i (a, b)
(<+>) (Fold toMonoidL summarizeL) (Fold toMonoidR summarizeR) = Fold toMonoid summarize
where
toMonoid x = (toMonoidL x, toMonoidR x)
summarize (sL, sR) = (summarizeL sL, summarizeR sR)
(<.>) :: (o1 -> o2) -> Fold i o1 -> Fold i o2
(<.>) f (Fold t s) = Fold t (f.s)
avg :: Fractional n => Fold n n
avg = (uncurry (/)) <.> sum <+> count
Na próxima semana vamos melhorar esse exemplo!
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.