Dan Marsden

The list monad is the free monoid monad.

The title of this post is a common sort of remark that is made about monads. Similar examples might be:

The multiset monad is the free commutative monoid monad.
The finite powerset monad is the free join semilattice monad.

Sorting out what statements such as these mean is our current purpose. In order to do so, we need to admit to being a little bit naughty up until now. Any good category theory book or course will quickly tell you that it is important not to just consider mathematical structures, but also the transformations between them. In the earlier posts, there was a lot of discussion of monads, but no mention of what the morphisms between them might be. Without pinning this down, we cannot compare monads in any meaningful way.

Monad Morphisms

There are actually a few choices for maps between monads. We shall consider the simplest case, morphisms between monads over some fixed base category $\mathcal{C}$ . More complex notions of transformation of monads are also useful, and tend to form 2-categories rather than mere categories. We shall return to this topic again later.

A monad morphism $\sigma : \mathbb{S} \rightarrow \mathbb{T}$ is a natural transformation between the underlying endofunctors $\sigma : \mathbb{S} \Rightarrow \mathbb{T}$ satisfying two axioms:

Unit axiom: $\sigma \circ \eta^{\mathbb{S}} = \eta^{\mathbb{T}}$ .
Multiplication axiom: $\sigma \circ \mu^{\mathbb{S}} = \mu^{\mathbb{T}} \circ \sigma_{\mathbb{T}} \circ \mathbb{T}\sigma$ .

We mentioned in an earlier post that a monad can be seen as a monoid in a precise sense. From that point of view, monad morphisms are exactly monoid morphisms. Again, we shall avoid getting into the details of these statements. For now, it is sufficient to think of a monad morphism as a natural transformation between the underlying endofunctors that interacts well with the additional monad structure.

Example: For any monad $\mathbb{T}$ , the monad unit is a monad morphism $\mathsf{Id} \rightarrow \mathbb{T}$ , from the identity monad into $\mathbb{T}$ .

Example: The identity natural transformation is a monad morphism, and monad morphisms are closed under composition as natural transformations. That is, monads on $\mathcal{C}$ and monad morphisms between them form a category.

Example: If $\sigma: \mathbb{S} \rightarrow \mathbb{T}$ is a monad morphism, and it has an inverse as a natural transformation, the inverse is also a monad morphism.

Lists and free monoids

Now we have addressed the issue of monad morphisms, we are ready to show how the list monad is the free monoid monad. Recall that the free monoid monad was given forming equivalence classes of terms induced by an equational presentation $(\Sigma,E)$ of the theory of monoids. We shall denote this monad $\mathbb{T}$ . The list monad has universe $\mathbb{L}(X)$ consisting of (some set theoretic encoding of) lists of elements from $X$ . $\mathbb{T}(X)$ and $\mathbb{L}(X)$ aren’t equal, so we must consider a more liberal notion of being “the same”. There is a natural transformation $\sigma : \mathbb{T} \Rightarrow \mathbb{L}$ given inductively by:

$\sigma([1]) = []$ .
$\sigma([x]) = [x]$ .
$\sigma([t_1 + t_2]) = \mathsf{concat}(\sigma([t_1]), \sigma([t_2]))$ .

Here, $\mathsf{concat}(xs,ys)$ denotes the concatenation of the two input lists. The notation is also a bit unfortunate as square brackets denote both equivalence classes of terms, and lists of values. Intuitively, all $\sigma$ does is form a list of all the variables appearing in any representative of the equivalence class, in the order which they appear from left to right. The axioms of the theory of monoids ensure this is a well defined map, and in fact it is a monad morphism. $\sigma$ has an inverse given inductively on lists by:

$\sigma^{-1}([]) = [1]$ .
$\sigma^{-1}(x:xs) = [x] +^{F(X)} \sigma^{-1}(xs)$ .

Here $x:xs$ is list formation via the usual cons operation you might see in Haskell for example.

So we have seen that the list monad “is” the free monoid monad in that they are isomorphic as monads on $\mathsf{Set}$ . The analogous statements about the free commutative monoid and free join semilattice monads arise via similar arguments. (Of course, there is a lot more to check than I’ve done explicitly here, that the maps are well defined, that they are natural, that the monad morphism axioms hold,…).

There are other senses in which the list monad is the free monoid monad, but to discuss those, we will need to introduce the Eilenberg-Moore category of a monad, which we shall discuss in a later post.

Monads via Algebra

A bit of univeral algebra

We will need some basic universal algebra for todays constructions. Intuitively what we are doing capturing classes of structures given by operations and equations they must satisfy, such as groups, rings and monoids.

We consider a signature $\Sigma$ of operation symbols. The elements of the signature are operation symbols, each with a specified arity in the natural numbers. Given a signature, and a set of variables $X$ , the set of $\Sigma$ –terms is defined inductively as follows:

Each $x \in X$ is a term.
If $t_1,\ldots,t_n$ are terms, and $o \in \Sigma$ has arity $n$ , then $o(t_1,\ldots,t_n)$ is a term.

We will generalize this notation to allow infix application of operations, writing $x + y$ rather than $+(x,y)$ when it is clearer to do so.

A $\Sigma$ –algebra consists of:

A set $A$ , the universe.
For each $o \in \Sigma$ of arity $n$ , a function $o^A : A^n \rightarrow A$ .

$\Sigma$ -algebras form a category $\mathsf{Alg}(\Sigma)$ , with morphisms functions $h : A \rightarrow B$ between algebra universes, such that for every $o \in \Sigma$ :

$h(o^A(a_1,\ldots,a_n)) = o^B(h(a_1),\ldots,h(a_n))$ .

For each term $t$ with variables in $X$ , and variable assignment $(-)^A : X \rightarrow A$ , we define the interpretation of $t$ in $A$ , denoted $t^A$ , as follows:

If $t$ is a variable $x$ , then $t^A = x^A$ .
If $t = o(t_1,\ldots,t_n)$ , then $t^A = o^A(t^A_1,\ldots,t^A_n)$ .

For a fixed $\Sigma$ , a set of formal equations $E$ is a set of pairs of terms over some set of variables $X$ . A pair $(\Sigma,E)$ is referred to as an equational presentation for a class of algebras. A $(\Sigma,E)$ -algebra is a $\Sigma$ -algebra such that for each $(t_1,t_2) \in E$ and variable assignment $(-)^A : X \rightarrow A$ :

$t^A_1 = t^A_2$

Example: A monoid is a $(\Sigma,E)$ -algebra where $\Sigma = \{ 1, \times \}$ and $E = \{ (1 \times x, x), (x \times 1, x), ((x \times y) \times z, x \times (y \times z)) \}$ . Here, $1$ has arity 0 (is a constant), and $\times$ has arity $2$ (is a binary operation). A morphism of $\Sigma$ -algebras is then a monoid morphism.

The category $\mathsf{Alg}(\Sigma,E)$ , of $(\Sigma,E)$ -algebras, is the obvious full subcategory of $\mathsf{Alg}(\Sigma)$ .

Back to adjunctions and monads

We now have enough abstract machinery in place to return to our efforts to construct monads. For an equational presentation $(\Sigma,E)$ , there is a forgetful functor

$U : \mathsf{Alg}(\Sigma,E) \rightarrow \mathsf{Set}$

sending an algebra to its underlying universe. The key fact that we need is that this forgetful functor always has a left adjoint

$F : \mathsf{Set} \rightarrow \mathsf{Alg}(\Sigma,E)$

which is also relatively easy to describe. $F(X)$ is called the free algebra on $X$ . For a set $X$ , the universe of $F(X)$ is the set of terms with variables in $X$ , quotiented by provable equality in equational logic, from the equations in $E$ . In general, describing these equivalence classes may be extremely difficult, although is manageable in many examples of interest. Writing $[t]$ for the equivalence class containing $t$ , for an algebra $B$ , and function $f : X \rightarrow U(B)$ , we define $\hat{f} : F(X) \rightarrow B$ inductively on representatives as follows:

$\hat{f}([x]) = f(x)$ .
$\hat{f}([o(t_1,\ldots,t_n)]) = o^B(\hat{f}([t_1]),\ldots,\hat{f}([t_n]))$ .

With this in place, we see that every equational presentation $(\Sigma,E)$ induces a monad $\mathbb{T}$ , with:

Endofunctor: $\mathbb{T}(X)$ is the set of equivalence classes of terms.
Unit: The unit maps variables to their equivalence classes $\eta(x) = [x]$ .
Multiplication: The multiplication is a flattening operation on nested equivalence classes. Formally, $\mu_X = U( \widehat{\mathsf{id}_{UF(X)}})$ .

The multiplication is probably easier to follow from an example.

Example: Returning to the equational presentation of monoids above, an example of the multiplication would be $\mu([w + [y + z] ]) = [w + (y + z)]$ .

Any choice of operations and equations then produces a monad on the category $\mathsf{Set}$ , yielding boundless examples.

Example: There are monads on $\mathsf{Set}$ induced by the equational presentations of monoids, commutative monoids, groups, Abelian groups, rings, join semilattices, semigroups…

The monads that arise from equational presentations are known as the finitary monads. We may return to the question of exactly what that means in a future post. Possibly more important to note is that if we consider sufficiently liberal generalizations of the arities in our equational presentations, every $\mathsf{Set}$ monad can be described in such a way.

Where do monads come from?

Last time, we saw several ad-hoc examples of monads. Now we look for a more uniform way to produce them. This is our first step into a wider world, in which connections with other mathematical constructions start to arise.

For an adjunction $L \dashv R$ , write $\eta : \mathsf{Id} \Rightarrow R \circ L$ and $\epsilon : L \circ R \Rightarrow \mathsf{Id}$ , for the unit and counit of the adjunction respectively. If $R : \mathcal{D} \rightarrow \mathcal{C}$ , then there is a monad on $\mathcal{C}$ with:

Endofunctor: $R \circ L$ .
Unit: $\eta : \mathsf{Id} \Rightarrow R \circ L$ .
Multiplication: $R \epsilon_L : (R \circ L)^2 \Rightarrow R \circ L$ .

In fact, every monad arises in this way, although we wont see the details of the other direction until we discuss Kleisli and Eilenberg-Moore categories in later posts.

Example: The category $\mathsf{Set}$ is Cartesian closed. We therefore have for a fixed $S$ , an adjunction $(-) \times S \vdash S \Rightarrow (-)$ . The resulting monad $S \Rightarrow (-) \times S$ is known as the state monad.

The construction above can be generalized. If we have an adjunction as before, and a monad $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ , then there is a monad on $\mathcal{C}$ with:

Endofunctor: $R \circ \mathbb{T} \circ L$ .
Unit: $R \eta^{\mathbb{T}}_L \circ \eta$ .
Multiplication $R \mu^{\mathbb{T}}_L \circ R \mathbb{T} \epsilon \mathbb{T} L$ .

Example: For a monad $\mathbb{T}$ on $\mathsf{Set}$ , by Cartesian closure, we get a monad $S \Rightarrow \mathbb{T}(- \times S)$ . This construction is sometimes known as the state monad transformer.

Those familiar with a bit more category theory should note that both the state monad and the corresponding transformer generalize to any Cartesian closed, and in fact any monoidal closed category.

So we have seen that finding monads can be reduced to finding adjunctions, and in a sense this is the only trick we need. It does have the disadvantage that to get a concrete description of the resulting monad, we need a good understanding of both the left and right adjoints.

So for example, to find lots of monads on the category $\mathsf{Set}$ , we just need a source of lots of right adjoint functors $\mathcal{C} \rightarrow \mathsf{Set}$ . Ideally, we would like a nice concrete description of both adjoints, in order to get a clear formulation the composite monad.

Next time, we will look at a conceptually important way in which we can find such functors.

What is a monad?

Now we’ve seen a bit of motivation, it’s time to knuckle down and be specific. A monad on a category $\mathcal{C}$ , referred to as the base category, has three components:

An endofunctor $\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}$ .
A unit natural transformation $\eta : \mathsf{Id} \Rightarrow \mathbb{T}$ .
A multiplication natural transformation $\mu : \mathbb{T}^2 \Rightarrow \mathbb{T}$ .

Furthermore, the unit and multiplication must satisfying the following axioms:

Left unitality: $\mu \circ \eta_{\mathbb{T}} = \mathsf{id}$ .
Right unitality: $\mu \circ \mathbb{T}\eta = \mathsf{id}$ .
Associativity: $\mu \circ \mu_{\mathbb{T}} = \mu \circ \mathbb{T}\mu$ .

The names of the natural transformations and axioms reflect the fact that a monad is actually a monoid in a precise sense. To avoid pulling in lots of definitions to explain the details, we shall postpone discussing this point for now. Instead, we shall move straight to some standard examples:

On any category, the identity functor $\mathsf{Id} : \mathcal{C} \rightarrow \mathcal{C}$ is a monad. Although this example is trivial, it is useful to have in mind, as this monad crops up in various constructions.
On any category with a terminal object, the functor mapping every object to the terminal object is a monad in a unique way.
On the category of sets and functions:
- The functor $\mathbb{L}$ , with $\mathbb{L}(A)$ the set of lists of elements from $A$ is a monad. The unit has $\eta(a) = [a]$ , and the multiplication concatenates a list-of-lists to a list.
- The functor $\mathbb{M}$ , with $\mathbb{M}(A)$ the set of (finite) multisets or bags of elements from $A$ . A multiset is a set in which elements can appear more than once. The unit maps an element to the corresponding singleton set, and the multiplication is given unions of multisets.
- The functor~ $\mathbb{P}$ mapping a set to its finite powerset is a monad, in a similar way to the monad $\mathbb{M}$ .
On any preorder $A$ , a closure operator is a monotone function $c$ such that $a \leq c(a)$ and $cc(a) = c(a)$ . If we view $A$ as a category, closure operators and monads on $A$ are the same thing.

Also, we must point out a very important non-example:

If $\mathbb{S}$ and $\mathbb{T}$ are monads, the composite endofunctor $\mathbb{T} \circ \mathbb{S}$ is not necessarily a monad.

The examples we have opened with are fairly standard, and commonly crop up in early discussion of monads. This is not because there is a shortage of monads out there, but rather that these examples don’t require any complex machinery or background knowledge.

Rather than just trying things and seeing if the monad axioms hold, it is natural to ask if there are more systematic ways of getting our hands on monads. This is the question we shall look at next.

Why monads?

Before looking at monads in any detail at all, it is worth considering why they might be an interesting subject to know about. In this post I will allow myself to mention a lot of complicated mathematical structures as illustrations. Many of these may be unfamiliar, depending on your background. We shall return to ground level in the next post.

Monads are lots of things

Monads can be considered from many different points of view. Depending on your perspective, a monad is:

A monoid in the category of endofunctors.
A categorification of a closure operator.
A (strict) 2-functor with domain the monoidal category of finite ordinals.
A (lax) 2-functor with domain the terminal bicategory.
A single object category enriched in a bicategory.
A functional programming abstraction for computational effects.
A presentation independent formulation of an algebraic theory.
A mapping of objects to term objects, with coherent insertion of generators and composition of families of terms.
A mapping of objects to term objects, with coherent insertion of generators and extension operations.
…

Although much of the terminology is probably baffling at this point, the key point is that this variety gives us many ways to start attacking a problem. The different viewpoints also suggest alternative ways in which the notion of monad can be generalized. For example, there are graded monads, indexed monads, pseudo-monads, relative monads to name but a few.

Lots of things are monads

For any mathematical abstraction to be useful, there should be plenty of examples. A surprisingly wide range of structures can be seen as monads:

Many “container like” structures, such as lists, sets, multisets and trees form monads.
Closure operators in order theory and topology are monads.
Free object constructions for algebraic theories form monads.
Preorders and categories themselves are monads.
Enriched and internal categories are monads.
Distributive laws for monads are themselves monads.
Monoids.
…

Monads come with useful things

Part of the richness of monad theory is that a monad comes with several associated mathematical structures:

A category of algebras, the Eilenberg-Moore category of the monad.
A category of free algebras, the Kleisli category of the monad.
Adjunctions between the base category and the Kleisli and Eilenberg-Moore categories.
A functor identifying the Kleisli category within the Eilenberg-Moore category.

Much of the richness of monad theory is derived from the interplay between the monad and these related mathematical structures. Although some of the terminology may currently be mysterious, we shall look at these constructions in detail in later posts.

Apart from the mathematical structures associated with a monad, there is also a large body of accompanying theory. Instantiating this theory appropriately can allow use to deduce lots of nice mathematical properties in many situations, whilst alleviating the need for lots of lower level manual work checking the details directly.

Hello Monads!

I plan to do a series of blog posts discussing monads. Obviously the internet is not short of monad guides and other discussion of monads, so why another one?

My perspective will be from the point of view of mathematics and theoretical computer science.
There will be very little mention of Haskell – there are many excellent Haskell programming guides around the internet that cover the topic from that point of view.
Monads are one of my favourite mathematical topics, so I’d like to talk about something I enjoy.

The level at which I pitch things will almost certainly evolve over time. For now, I intend to assume some knowledge of category theory, but I will try to avoid being “expert friendly” if at all possible.