Mônadas

Esse post é baseado no livro Teoria das Categorias para Programadores, de Bartosz Milewski.

1 Monads

there are entire subcultures of young men these days who just hang out online waiting for someone to ask a question about monads

— Monoid Mary (@argumatronic) 4 de março de 2019

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:

  • Define funções impuras
  • Cria e gerencia estados de sistema
  • Permite sequenciamento imperativo
  • Define IO
  • É dependente de avaliação preguiçosa
  • É uma porta dos fundos para efeito colateral
  • É uma linguagem imperativa dentro do Haskell
  • Necessita de conhecimento de matemática abstrata para entender
  • Exclusivos do Haskell

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.

2 Categoria Kleisli

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

3 Dissecando o Peixe

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.

4 Notação do

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.

5 Referências

https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/