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.

3 thoughts on “The list monad is the free monoid monad.”

Pingback: Algebra, Order and Monads – Dan Marsden
Pingback: The Continuation Monad – Dan Marsden
Pingback: Monad Actions – Dan Marsden

Monad Morphisms

Lists and free monoids

Share this:

Like this:

Related

3 thoughts on “The list monad is the free monoid monad.”

Leave a Reply Cancel reply