SciTech.blog

26 Sep 2017, 07:00 • monads, theory

...a monoid in the category of endofunctors. This enigmatic sentence keeps perplexing beginner programmers. In this post we dissect it so you don't have to read a whole book on category theory in order to understand what it means.

To define a monoid in a category, we first need to know what a tensor category is. Formally, it's a triple $$(\mathcal{C},\otimes,I)$$ where $$\mathcal{C}$$ is a category, $$I \in \mathrm{Ob}(\mathcal{C})$$ and $$\otimes$$ is a bifunctor from $$\mathcal{C}^{\mathcal{C} \times \mathcal{C}}$$ such that

$\alpha: (A \otimes B) \otimes C \cong A \otimes (B \otimes C)$ $\rho: A \otimes I \cong A$ $\lambda: I \otimes A \cong A$

$$\alpha$$ is called the associator and $$\rho$$ and $$\lambda$$ are called the right and left unitor, respectively. (There are also a few coherence conditions we can ignore here.)

As an example, consider Set, the category of sets. It can easily be checked that $$(\mathbf{Set},\times,1)$$ (where $$1$$ is the terminal object) defines a tensor category (the Cartesian product is associative up to isomorphism).

We can now go on to define what a monoid object in a tensor category is—a triple $$(M,\mu,\eta)$$ where $$M \in \mathrm{Ob}(\mathcal{C})$$, $$\mu$$ is a morphism $$M \times M \rightarrow M$$ and $$\eta:1 \rightarrow M$$ such that

$\mu \circ \mu \otimes 1 = \mu \circ 1 \otimes \mu \circ \alpha$

and

$\lambda = \mu \circ \eta \otimes 1 \land \rho = \mu \circ 1 \otimes \eta$

In Set, monoids known from abstract algebra (i.e., semigroups with a unit element) are monoid objects.

Let's now consider a category $$\mathcal{C}$$ and a category of its endofunctors, $$[\mathcal{C},\mathcal{C}]$$. It can be easily checked that $$([\mathcal{C},\mathcal{C}],\circ,I)$$, where $$\circ$$ is functor composition and $$I$$ the identity functor, is a tensor category. An endofunctor $$T \in [\mathcal{C},\mathcal{C}]$$ together with two natural transformations, $$\mu:T^2 \rightarrow T$$ and $$\eta:I \rightarrow T$$, is a monad if it is a monoid object in $$([\mathcal{C},\mathcal{C}],\circ,I)$$.