Monoids e Foldable

Playlists

1 Monoid

Um Monoid é um conjunto de valores associados a um operador binário associativo e um elemento identidade:

  • Valores inteiros com o operador + e o elemento 0
  • Valores inteiros com o operador * e o elemento 1
  • Valores String com o operador ++ 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)

2 Foldable

  • A importância dos Monoids está na generalização em como combinar uma lista de valores de um tipo que pertença a essa classe.
  • Sabendo que o tipo 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

2.1 Classe Foldable

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

2.2 Exemplo prático

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:


55
getProduct (foldMap Product [1..10])

Saída:


3628800

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!!!

2.3 Outras funções Foldable

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]

2.4 MapReduce

  • O MapReduce1 é um modelo de programação utilizado largamente em clusters.
    • Google, Amazon, Yahoo! e outros estão entre seus grandes utilizadores
  • Muitas ferramentas como Apache Hadoop e Apache Spark são baseadas neste modelo
  • O MapReduce nada mais é que a função foldMap
    • O Map é feito em paralelo e de maneira distribuída (o que é fácil já que o map é puro)
    • O Reduce corresponde ao fold
    • Como a redução ou folding é feito em uma ordem arbitrária é imprescindível que se trabalhe utilizando um monoid2 para que o resultado seja consistente!

2.5 Exercício 1

Implemente toList utilizando foldMap.

toList  :: t a -> [a]
  • Ela transforma qualquer estrutura Foldable em uma lista!
  • Uma vez que já temos todas as funções anteriores para Listas, basta fornecer a definição de foldMap para a instância e todo o resto vem por padrão (mas nem sempre eficiente).

2.6 Exercício 1 - Resposta

Implemente toList utilizando foldMap:

toList = foldMap (x -> [x])

2.7 Generalizações

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

3 Tipo de Dado Algébrico Fold

  • No exemplo anterior, a estrutura da árvore vai ser atravessada

duas vezes, uma para calcular o resultado de sum e outra para calcular o resultado de length:

> average (Node (Leaf 1) (Leaf 3))
2
  • Nada impede que façamos os dois procedimentos em uma única passagem da estrutura:
average :: Foldable t => t Double -> Double
average xs = getSum soma / getSum contagem
  where (soma, contagem) = foldMap (\x -> (Sum x, Sum 1.0)) xs
  • Em casos que a função `map` retorne vários monóides, nossa função `foldMap` começa a ficar ilegível e de difícil manutenção:
foldMap (\x -> (Sum x, Sum 1.0, Prod x, And (x>0))) xs
  • Vamos automatizar esse procedimento criando um tipo de dados 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

  • Por exemplo, podemos definir sum' como:
sum' :: Num n => Fold n n
sum' = Fold Sum getSum

E agora podemos fazer:

fold sum' [1..10]

Saída:


55
  • A expressão 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
  • Tudo em 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
  • Para combinar dois 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)
  • Também seria interessante aplicar uma função de sumarização que combinasse a tupla resultante:
(<.>) :: (o1 -> o2) -> Fold i o1 -> Fold i o2
(<.>) f (Fold t s) = Fold t (f.s)
  • Com isso temos:
avg :: Fractional n => Fold n n
avg = (uncurry (/)) <.> sum <+> count

Código no Repl.it

Na próxima semana vamos melhorar esse exemplo!

4 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.

  1. https://en.wikipedia.org/wiki/MapReduce ↩︎

  2. https://en.wikipedia.org/wiki/Monoid#MapReduce ↩︎