Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
Relembrando o conceito de Monoid, temos um único objeto \(M\) equipados com um operador de multiplicação \(\cdot\) e um elemento neutro \(\epsilon\) tal que:
\(a, b \in M, a \cdot b \in M\)
\(a \cdot \epsilon = \epsilon \cdot a = a\)
\((a \cdot b) \cdot c = a \cdot (b \cdot c) = a \cdot b \cdot c\)
ou em Haskell:
class Monoid m where
mempty :: m
mappend :: m -> m -> m
Vimos que os números inteiros podem representar um Monoid com o operador de multiplicação e o elemento neutro \(1\) ou com o operador de soma e o elemento neutro \(0\). Uma lista é um Monoid com o operador de concatenação e o elemento neutro de lista vazia.
instance Monoid [] where
mempty = []
mappend = (++)
No caso dos números inteiros, além das propriedades dos Monoids, temos algumas propriedades extras, por exemplo \(2 \cdot 3 = 6\), ou seja, o elemento \(2 \cdot 3\) é equivalente ao elemento \(6\), ambos pertencentes a \(M\).
Já para o caso de listas, temos que [2] ++ [3] / [6]=, ou seja, uma
lista contém as propriedades dos Monoids e nada mais.
Um Monoid livre é um Monoid que consegue gerar outros Monoids, partindo de um gerador e adicionando novas operações e propriedades.
Em programação podemos utilizar uma lista como um Monoid livre. Dado um
tipo \(A\) podemos gerar o Monoid \([A]\) enumerando todas as
combinações de elementos agrupados em uma lista. Considere transformar
uma lista de Bool em um Monoid livre, começamos com o elemento neutro
da lista e as listas contendo um dos valores possíveis:
data Bool = True | False
m = [ [], [True], [False] ]
Ao aplicar o operador de concatenação entre cada par de elementos dessa lista inicial temos:
m = [ [], [True], [False], [True, True], [True, False], [False, True], [False, False] ]
Continuando tal operação, temos uma lista infinita de todos os elementos
do nosso Monoid livre. Para definir um novo Monoid a partir do Monoid
livre, basta definirmos um morfismo h :: [a] -> a de tal forma que:
h (mappend x y) = mappend (h x) (h y)
No nosso caso podemos definir h = and para a instância de Monoid de
Bool com &&:
and :: [Bool] -> Bool
and [] = True
and (b:bs) = b && (and bs)
instance Monoid Bool where
mempty = True
mappend = (&&)
Podemos verificar que essa é uma função que segue a propriedade:
h ([True] ++ [False]) = (h [True]) && (h [False])
h [True, False] = True && False
False = False
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/