Grupo de Estudos em Haskell da UFABC > Introdução à Programação Funcional em Haskell > Monoids e Foldable

Monoids e Foldable

Playlists

1 Semigrupos e monoides

Antes de definir um monoide, vamos definir um semigrupo. Um Semigrupo é um par (\(C\), \(\diamond\)) onde:

\(C\) é um conjunto de valores;
\(\diamond\) é um operador binário associativo fechado em \(C\).

Ou em outras palavras:

\(\forall a, b \in C \implies a \diamond b \in C\)
\(\forall a, b, c \in C \implies a \diamond b \diamond c = (a \diamond b) \diamond c = a \diamond (b \diamond c)\)

Exemplos:

O par (\(\mathbb{N}\), \(+\)) forma um semigrupo onde o conjunto de valores é \(\mathbb{N}\) e operador o associativo é o \(+\);
O par (\(\mathbb{Z}\), \(*\)) forma um semigrupo onde o conjunto de valores é \(\mathbb{Z}\) e operador associativo é \(*\);
O par (\(\mathbb{R}\), \(/\)) NÃO forma um semigrupo, pois a operação \(/\) não é associativa.

Em Haskell semigrupos são representados como uma classe de tipos (typeclass) com a seguinte definição:

class Semigroup a where
  (<>) :: a -> a -> a

Dado um tipo:

newtype UmInteiro = MkInteiro Int

Podemos definir uma instância da classe Semigroup para o nosso tipo SGSoma da seguinte maneira:

instance Semigroup UmInteiro where
  (MkInteiro x) <> (MkInteiro y) =  MkInteiro $ x + y

Nesta definição, o conjunto de valores é dado pelo tipo Int e a operação (<>) (lê-se mappend ou diamond) é dada pela implemetação fornecida no momento da definição da instância.

Quando a operação associativa de um semigrupo (\(C\), \(\diamond\)) também possui um elemento neutro/identidade \(e \in C\) à esquerda e à direita, ou seja: \(\forall a \in C \implies e \diamond a = a \diamond e = a\), podemos dizer que temos um monoide. Em outras palavras, um monoide é uma trinca (\(C\), \(\diamond\), \(e\)) onde:

\(C\) é um conjunto de valores;
\(\diamond\) é um operador binário associativo fechado em \(C\);
\(e\) é um elemento neutro, à esquerda e à direita, para \(\diamond\)

Os dois primeiros pontos já são satisfeitos quando temos um semigrupo. O terceiro é a novidade. Vejamos alguns exemplos:

A trinca (\(\mathbb{N}\), \(+\), \(0\)) forma um monoide onde o conjunto de valores é \(\mathbb{N}\) e operador o associativo é o \(+\) e o elemento neutro é o \(0\);
O par (\(\mathbb{Z}\), \(*\), \(1\)) forma um monoide onde o conjunto de valores é \(\mathbb{Z}\) e operador associativo é \(*\) e o elemento neutro é \(1\).

Em Haskell, representamos monoides como uma classe de tipos cuja definição é:

class Semigroup a => Monoid a where
  mempty :: a

Note que para participar da classe de tipos Monoid, um tipo precisa antes participar da classe de tipos Semigroup. O método mempty da definição acima devolve o valor em a do elemento neutro da operação associativa (<>).

Para o nosso exemplo poderíamos definir um monoide para o semigrupo que já criamos como:

instance Monoid UmInteiro where
  mempty = MkInteiro 0

Como para ser um monoide um tipo também deve ser um semigrupo, já temos a definição de cada uma das três componentes que definem um monoide: (UmInteiro, (+), 0).

Repare que criamos um tipo novo (UmInteiro) para definir as instâncias de monoide e semigrupo para o que é essencialmente um Int. De fato, seria possível criar instâncias para Int diretamente, sem termos que recorrer a estes tipos novos. Isto, contudo, não seria uma boa prática.
O problema todo é que como um tipo só pode ter uma insância de cada classe, se em qualquer momento alguém quisesse definir uma outra instância de monoide para Int, digamos (Int, (*), 1), não seria possível pois já haveria uma outra instância de monoide definida. Ao criar tipos diferenciados contornamos este problema.

Em Haskell, podemos definir outros monoides como por exemplo: (String, (++), "") ou (Bool, (||), False).

Outro exemplo são as listas. Para elas temos a seguinte instância de semigrupo e monoide:

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty  = []

Já para o tipo Maybe podemos definir:

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> my      = my
  mx      <> Nothing = mx
  Just x  <> Just y  = Just (x <> y)

instance Semigroup a => Monoid (Maybe a) where
  mempty  = Nothing

Note que neste caso, como precisamos utilizar o operador (<>) para o tipo a contido em Maybe, somos obrigados a incluir a restrição Semigroup a na declaração das instâncias de semigrupo e monoide.

As definições completas de semigrupo e monoide presentes no Haskell têm outras funções úteis (que são dadas automaticamente a partir do (<>) e do mempty):

class Semigroup a where
  (<>) :: a -> a -> a
  sconcat :: NonEmpty a -> a
  stimes :: Integral b => b -> a -> a
  {-# MINIMAL (<>) #-}

A função sconcat (semigroup concat), recebe uma lista de valores não vazia e devolve o resultado da combinação destes valores utilizando o operador (<>). Já a função stimes combina n cópias do valor do tipo a fornecido.

Já a definição completa de monoide é dada abaixo:

class Semigroup a => Monoid a where
  mempty :: a
  mappend :: a -> a -> a
  mconcat :: [a] -> a
  {-# MINIMAL mempty #-}

Note que a definição de monoide também contém uma função mappend, que por padrão é exatamente a mesma que (<>). Isto é um artefato histórico do tempo que não existia a necessidade de que um tipo fosse um semigrupo antes de ser um monoide em Haskell. Ou seja, era preciso fornecer tanto o elemento neutro quanto a operação associativa na declaração da instância.

Já a função mconcat é equivalente à função sconcat para semigrupo com a diferença de que a lista não é necessariamente não vazia. Caso a lista seja vazia, a operação devolve simplesmente o elemento neutro (que não existe em um semigrupo, daí a restrição anterior).

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:

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

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 MapReduce¹ é 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 monoid² 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:

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.