Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.
<blockquote class=“twitter-tweet” data-lang=“pt”>
<p lang=“en” dir=“ltr”>
there are entire subcultures of young men these days who just hang out online waiting for someone to ask a question about monads
</p>
— Monoid Mary (@argumatronic) 4 de março de 2019
</blockquote>
<script async src="https://platform.twitter.com/widgets.js" charset=“utf-8”></script>
O uso de Monads gerou diversos mitos entre os programadores por conta de seu uso em programação (não necessariamente em Haskell). Isso motivou a criação de diversos tutoriais traçando uma analogia de Monads com outros conceitos fora da computação ou com enfoque em uma de suas aplicações práticas.
De acordo com o Haskell wiki e sumarizado no texto What I wish I knew when learning Haskell, um Monad não:
A dificuldade em entender Monads é por sermos treinados em implementar um código de forma imperativa (mesmo em linguagens orientadas a objetos), ou seja, definimos variáveis auxiliares para armazenar valores intermediários e embutimos trechos de códigos de outra função em nossa função de interesse. Considere a função para calcular a magnitude de um vetor \(3D\):
double vmag (double * v) {
double d = 0.0;
int i;
for (i=0; i<3; i++)
d += v[i]*v[i];
return sqrt(d);
}
Quando pensamos em reestruturar nosso código, verificamos trechos que podem ser utilizados por outras funções e modularizamos:
double square(double x) {
return x*x;
}
double sum_with(double * v, std::function<double(double)> f) {
double sum = 0.0;
int i;
for (i=0; i<3; i++) {
sum += f(v[i]);
}
return sum;
}
double vmag (double * v) {
return sqrt(sum_with(v, square));
}
Que, de forma equivalente em Haskell temos:
vmag = sqrt . sum . fmap (^2)
Durante essa sequência de tutoriais vimos que a composição de funções
representa um padrão importante na programação para deixar seus códigos
mais organizados, livres de bugs e concisos. Porém, vimos também o caso
do nosso Writer w a que alterava a saída de nossas funções com um
embelezamento, de forma a evitar transformar uma função pura em
impura.
Essa estrutura nos obrigou a criar um operador de composição específico para esses casos, gerando a Categoria Kleisli, que detalharemos em seguida.
Relembrando nosso tipo Writer em Haskell:
data Writer w a = Writer (a, w)
podemos criar uma instância de Functor fazendo:
instance Functor (Writer w) where
fmap f (Writer (a,w)) = Writer (f a, w)
Utilizando esse tipo como saída de nossas funções temos que uma função
f :: a -> b se torna uma função f :: a -> Writer w b. Fazendo
Writer w = m, temos o padrão:
f :: a -> m b
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
Podemos então pensar na categoria Kleisli (\(\mathbf{K}\)) como:
Partindo de uma categoria \(C\) e um endofunctor \(m\), a categoria \(\mathbf{K}\) possui os mesmos objetos de \(C\), mas um morfismos \(a \rightarrow b\) é mapeada para \(a \rightarrow m b\) na categoria \(C\).
Para ser uma categoria precisamos de um operador de composição (já temos o nosso peixe) e um morfismo identidade \(a \rightarrow a\), que na categoria \(C\) representa \(a \rightarrow m a\). Com isso, dizemos que \(m\) é um Monad se:
class Monad m where
(>=>) :: (a -> m b) -> (b -> m c) -> (a -> m c)
return :: a -> m a
E apresenta as propriedades:
(f >=> g) >=> h = f >=> (g >=> h) = f >=> g >=> h
f >=> return = return >=> f = f
Em outras palavras, um Monad define como compor funções embelezadas.
Como ficaria a instância completa do nosso Monad Writer w?
instance Monoid w => Monad (Writer w) where
f >=> g = \a -> let Writer (b, s) = f a
Writer (c, s') = g b
in Writer (c, s `mappend` s')
return a = Writer (a, mempty)
Indicando que w deve ser um Monoid, generalizamos a definição para
outros tipos além de String. Dada essa definição, ele possui as
propriedades de composição e identidade?
(f >=> g) >=> h
\a -> let Writer (b, sb) = f a >=> h
Writer (c, sc) = g b
in Writer (c, sb `mappend` sc)
=
\a -> let Writer (c, sb `mappend` sc) = (f >=> g) a
Writer (d, sd) = h c
in Writer (d, sb `mappend` sc `mappend` sd)
f >=> (g >=> h)
f >=> \b -> let Writer (c, sc) = g b
Writer (d, sd) = h c
in Writer (d, sc `mappend` sd)
\a -> let Writer (b, sb) = f a
Writer (d, sc `mappend` sd) = (g >=> h) b
in Writer (d, sb `mappend` sc `mappend` sd)
(f >=> g) >=> h = f >=> (g >=> h)
(f >=> return) = \a -> let Writer (b, sb) = f a
Writer (b, mempty) = return b
in Writer (b, sb `mappend` mempty) = Writer (b, sb) = f a
Podemos perceber um padrão dentro do nosso operador >=> que nos
ajudará a simplificá-lo:
f >=> g = \a -> let mb = f a
in ...
O retorno da função deve ser uma função que recebe um m b e uma função
b -> m c e retorna um m c. Vamos criar o seguinte operador:
(>>=) :: m a -> (a -> m b) -> m b
Que no caso do Monad Writer w fica:
(Writer (a,w)) >>= f = let Writer (b, w') = f a
in Writer (b, w `mappend` w')
Tornando a definição do operador >=> como:
f >=> g = \a -> (f a) >>= g
Muito mais simples! O operador >>= é conhecido como bind e define
outra forma de instanciar um Monad:
class Monad m where
(>>=) :: m a -> (a -> m b) -> m b
return :: a -> m a
Lembrando que um Monad também é um Functor, ele permite o uso de fmap.
Se tivermos duas funções:
f :: a -> m b
fmap :: (a -> b) -> m a -> m b
Ao aplicar fmap f ma sendo ma um monad m a, temos como saída um
tipo m (m b). Precisamos de uma função que colapse a estrutura para
apenas um Monad:
join :: m (m a) -> m a
ma >>= f = join (fmap f ma)
Com isso podemos definir um Monad também como:
class Monad m where
join :: m (m a) -> m a
return :: a -> m a
A escolha de qual forma utilizar para instanciar um Monad depende da
própria estrutura que queremos instanciar. Escolhemos o que for mais
fácil definir e o resto é definido de graça! A função join do nosso
Monad Writer w fica:
join (Writer (Writer (a, w), w')) = Writer (a, w `mappend` w')
Fica como exercício verificar que join (fmap f ma) é equivalente a
ma >> f= para esse Monad.
Relembrando um exemplo inicial da categoria Kleisli, tínhamos:
notW :: Bool -> Writer Bool
notW b = (b, "not")
is_even :: Int -> Writer Bool
is_even x = (x `mod` 2 == 0, "even")
is_odd :: Int -> Writer Bool
is_odd = is_even >=> notW
O Haskell permite um syntactic sugar que transforma essa composição em uma notação similar ao paradigma imperativo:
is_odd x = do
ev <- is_even x
is_odd ev
Que é parseado em:
is_even x >>= \ev -> is_odd ev
A notação a <- f x é lida como a recebe o resultado de f x sem a
parte embelezada.
Para o caso do nosso Monad Writer w podemos também embelezar uma
função automaticamente durante a notação do:
even x = x `mod` 2 == 0
tell :: w -> Writer w ()
tell s = Writer ((), s)
is_odd x = do tell "even"
ev <- return (even x)
tell "not"
return (not ev)
Isso é traduzido para:
tell "even" >>= (\() -> return (even x) >>= \ev -> tell "not" >>= \() -> return (not ev))
Writer (f (), "even" ++ w')
Writer (g () (even x), "even" ++ "" + w'')
Writer (h () (even x) (), "even" ++ "" + "not" + w''')
Writer ((not.even) x, "even" ++ "" + "not" + "")
Writer ((not.even) x, "evennot")
Reparem que as funções \() -> return x não fazem uso do argumento de
entrada, apenas altera o embelezamento da saída da função, podemos
definir um operador específico para esses casos:
(>>) :: m a -> m b -> m b
Fazendo com que o desugaring acima fique:
tell "even" >> return (even x) >>= \ev -> tell "not" >> return (not ev)
Esse operador descarta o argumento mas executa o efeito colateral da função.
Monads estão aos poucos aparecendo nas linguagens de programação
orientadas a objetos. C++, por exemplo, está introduzindo o conceito de
resumable functions que o Python já implementa com yield e Haskell
com continuation Monad. Veremos alguns exemplos em seguida.
https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/