Software! Math! Data! The blog of R. Sean Bowman
The blog of R. Sean Bowman
January 04 2016

We previously looked at a generalization of the familiar algebraic concept of a monoid to a category. We’re now in a position to give the “mathematician’s definition” of a monad. People seem to have different opinions of this definition. I personally think that it’s simple, elegant, and captures the spirit of generality of category theory. I have heard that some people use this definition to belittle or confuse people. Perhaps it’s just that people feel belittled or confused by it. In any case, describing a monad isn’t easy, and we shouldn’t feel bad if we don’t understand it very well at first.

My aim here certainly isn’t to confuse or belittle, but to give a slightly different perspective of what a monad is (a mathematician’s perspective). It’s a very concise definition that says a lot in a few words, and in a few more posts we’ll see some applications, more definitions, and hopefully learn how monads can be used to structure computations. I should add that I’m no expert on monads in mathematics or in computer science, so please don’t take me as an authority in these matters.

Let’s review a little before. Recall that we’re fixing a category \(\CC\) of types. Think of these as nice types, like OCaml types. There are some builtin types like int and string, and also other composite types like int list and string * string * int, and so forth. These are the objects of the category. Arrows are functions between the types, in the sense of (say) OCaml. Crucially, \(\CC\) must have as objects the unit type (whose unique value is sometimes spelled “()”) and function types \(A\rightarrow B\) where \(A\) and \(B\) are objects in \(\CC\). Such a category is Cartesian closed since it contains a unit type, products, and function types (exponentials).

Functor Categories

OK, now we’re going to go up the ladder of abstraction one level. Fixing our category \(\CC\), consider the category \(\DD\) whose objects are endofunctors on \(\CC\) and where arrows are natural transformations between two functors. This is the endofunctor category on \(\CC\). (If you don’t remember some of the definitions, have a look at the Wikipedia category theory article.) This is a bit harder for me to get any intuition about, but a fairly simple definition nonetheless.

Monads

Now here’s the kicker: if we know what a monoid in a category is, and we know what an endofunctor category is, the definition of monad is really simple:

Mathematician's definition of a Monad

Fix a category of types \(\CC\). A monad is a monoid in the category of endofunctors on \(\CC\).

Very short, very nice! But let’s try to tease apart some of the definition. In order to get a monoid in a category, the category must be monoidal. Recall from the post on monoids in categories that a category is monoidal if

  • there is a bifunctor \(\otimes\colon \DD\times \DD\rightarrow\DD\) which is associative, and

  • there is an object \(I\) of \(\DD\) which is a left and right inverse for \(\otimes\).

So what are \(\otimes\) and \(I\) here? The first, \(\otimes\), is just composition of functors. That is, if we have an element \(D\) of \(\DD\) (which is a functor from \(\CC\) to \(\CC\)), \((D\otimes D)(C) = D(D(C))\) for any object \(C\) of \(\CC\). That doesn’t leave may choices for \(I\): \(I\) must be the identity functor on \(\DD\). (Or must it? Now I’m not quite sure… In any case, we’ll choose \(I\) to be the identity functor.) With these definitions it’s clear that \(\DD\) becomes a monoidal category. (Of course, this is also a good place to stop and convince yourself of that statement!)

So that’s the monoidal category structure on our endofunctor category \(\DD\); what do the monoid rules say?

To have a monoid, we need an object of \(\DD\) (let call it \(F\) for "functor"), a “multiplication” rule \(\mu\colon F^2\rightarrow F\), and a unit \(\eta\colon I\rightarrow F\).

First, the “multiplication is associative” cube looks like

\[ \begin{xy} \xymatrix{ F^3\ar[r]^{1\otimes \mu}\ar[d]_{\mu\otimes 1} & F^2\ar[d]^{\mu}\\ F^2\ar[r]_{\mu} & F } \end{xy} \]

Another way of writing this:

$ \mu\circ F\mu = \mu \circ \mu F$

where \(\left(F\mu\right)_X = F\mu_X\) and \(\left(\mu F\right)_X = \mu_{FX}\).

Yet another way of putting this: given any object \(X\in\CC\), when computing \(F(F(F(X)))\), it does not matter whether we use \(\mu\) to collapse the first two \(F\), or the innermost \(F\); after another application of \(\mu\), we arrive at the same answer.

Finally, we need a rule about “identities”, which looks like this in the monad case

\[ \begin{xy} \xymatrix{ I\otimes F\ar[r]^{\eta\otimes 1}\ar[dr] & F\otimes F\ar[d]^{\mu} & F\otimes I\ar[l]_{1\otimes\eta}\ar[dl]\\ & F & } \end{xy} \]

Another way to put this diagram:

$ \mu\circ (F\eta) = \mu\circ (\eta F) = id_F. $

Yet another way to look at this is that, given an object \(FX\), \(\eta\) gives a way to introduce another \(F\) (obtaining \(F(F(X))\)) so that application of \(\mu\) gives back the original \(FX\).

Examples of Monads

Sadly, I don’t know of a lot of monads in wide use in mathematics. As I mentioned in the history and context post, monads were first defined in a book on sheaf theory, which falls broadly under the algebraic geometry umbrella. This usage still seems pretty esoteric to me.

The closest thing I know of to examples of monads for mere mathematical mortals are generalizations of closure operators. Think of the closure operator in a category of your favorite topological spaces, and let \(C, \mu, \eta\) be an idempotet monad on \(\CC\); that is, \(\mu\) and \(\eta_C(-)\) are both isomorphisms. We say that \(CX\) is the closure of \(X\), \(\eta_X\colon X\rightarrow CX\) is the map to the closure, and \(X\) is closed exactly if \(\eta_X\) is an isomorphism. This matches with our intuition, for if \(X\) is not closed, then \(CX\) is, and so \(\eta_X\) cannot be an isomorphism. On the other hand, if \(X\) is already closed, then \(\eta_X(X)\) certainly is. This can be done for more general categories as well.

Finally, monads are closely related to operads, which I know very little about. You can read more of you like.

Next steps

Next we’d like to look at a couple of equivalent definitions of monad, including ones that are often used in programming languages. We’ll try to understand what the basic operators do, and maybe even see why monads can be a useful programming tool!

(Edits: the original version of this post contained mistakes in the commutative diagrams.)

Approx. 1073 words, plus code