Being Free is Certainly Ideal

In this post we shall introduce two particular classes of monad that arise in practice. As usual, we shall endeavour keep things simple, often restricting our attention to an algebraic perspective on $\mathsf{Set}$ monads.

Free Monads

We shall write $\mathsf{Mnd}(\mathcal{C})$ for the category of monads on a category $\mathcal{C}$ , and monad morphisms between them. We shall also write $[\mathcal{C},\mathcal{C}]$ for the category of endofunctors on $\mathcal{C}$ and natural transformations between them. There is an obvious forgetful functor:

$\mathsf{Mnd}(\mathcal{C}) \rightarrow [\mathcal{C},\mathcal{C}]$

This functor does not in general have a left adjoint, so we have to consider existence of free objects individually. Let $F$ be an endofunctor. The monad $F^*$ is the free monad over $F$ if there exists a universal natural transformation $\theta : F \Rightarrow F^*$ such that for every monad $\mathbb{T}$ and natural transformation $\alpha : F \Rightarrow \mathbb{T}$ there exists a unique monad morphism $\hat{\alpha} : F^* \Rightarrow \mathbb{T}$ such that

$\hat{\alpha} \circ \theta = \alpha$

Note this is the usual categorical notion of free object, relative to the forgetful functor above. It is important to emphasise that there are other forgetful functors from the category of monads for which we could consider free objects. This setting is normally what is intended when the term is used without qualification.

The notation $F^*$ is fairly common, and relates to the similar notation used for free monoids, as there are many analogies.

Example: For a set $E$ , the exception monad $(-) + E$ is the free monad over the constant endofunctor $K_E$ mapping everything to $E$ . For the usual encoding of coproducts in $\mathsf{Set}$ we have been using, the universal morphism is

$\theta(e) = (2,e)$

and for $\alpha : K_E \Rightarrow \mathbb{T}$ the unique fill-in morphism is:

$\hat{\alpha}(t) = \begin{cases} \eta(x), & \mbox{if } t = (1,x) \\ \alpha(e), & \mbox{if } t = (2,e) \end{cases}$

Having seen the abstract definition, and one example, it is natural to look for a more systematic strategy yielding free monads. For the approach we shall adopt, we are going to need a bit more machinery first.

For an endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ , there is a category of endofunctor algebras $\mathsf{Alg}(F)$ , with objects pairs $(A, a : F(A) \rightarrow A)$ , and a morphism $h : (A,a) \rightarrow (B,b)$ is a $\mathcal{C}$ -morphism $h : A \rightarrow B$ such that:

$h \circ a = b \circ F(h)$

Composition and identities are as in $\mathcal{C}$ . These conditions are similar to those we saw in discussion of the Eilenberg-Moore category in an earlier post. In fact, the category $\mathcal{C}^{\mathbb{T}}$ is the full subcategory of $\mathsf{Alg}(\mathbb{T})$ consisting of the objects satisfying the unit and multiplication axioms for an Eilenberg-Moore algebra.

There is a forgetful functor $R : \mathsf{Alg}(F) \rightarrow \mathcal{C}$ . If this functor has a left adjoint $L : \mathcal{C} \rightarrow \mathsf{Alg}(F)$ , then this induces a monad $R \circ L$ on $\mathcal{C}$ . Furthermore, we have an equivalence of categories

$\mathsf{Alg}(F) \simeq \mathcal{C}^{R \circ L}$

Recall that such an equivalence is certainly not automatic. This returns us to the topic of monadicity, that we touched upon in an earlier post. We have not introduced enough background on monadicity to discuss this properly yet, so we take this as a fact.

If a monad is of the form $R \circ L$ as in the discussion above, it is referred to as the algebraically free monad over $F$ . We can now state the main facts that we need:

If $\mathbb{T}$ is the algebraically free monad over $F$ , then it is the free monad over $F$ .
If $\mathcal{C}$ is a complete category, and for endofunctor $F : \mathcal{C} \rightarrow \mathcal{C}$ , $F^*$ exists, then the forgetful functor $\mathsf{Alg}(F) \rightarrow \mathcal{C}$ has a left adjoint, and $\mathcal{C}^\mathbb{F^*} \simeq \mathsf{Alg}(F)$ .

So in the case of $\mathsf{Set}$ monads, as the base category is complete, we can reduce the task of finding free monads to that of finding algebraically free monads.

To exploit this connection, we note that every algebraic signature $\Sigma$ induces a signature endofunctor, which we shall also write as $\Sigma : \mathsf{Set} \rightarrow \mathsf{Set}$ . This functor is given by the follow coproduct:

$\Sigma(X) = \coprod_{o \in \Sigma} X^{\mathsf{ar}(o)}$

where $\mathsf{ar}(o)$ denotes the arity of operation symbol $o$ .

Example: Let $\Sigma$ be a signature with a single binary operation and a constant. Then the corresponding endofunctor is:

$\Sigma(X) = X \times X + 1$

A $\Sigma$ -algebra is simply a pair $(A, a : A \times A + 1 \rightarrow A)$ . The function $a$ is equivalent to giving a binary function $A \times A \rightarrow A$ , corresponding to the binary operation symbol, and an element of $A$ , corresponding to the constant element. That is the same thing as specifying an algebra for the signature $\Sigma$ .

More generally, it is hopefully clear that for a signature $\Sigma$ , there is an isomorphism between the category of algebras for that signature, and the category of endofunctor algebras for the corresponding signature functor.

For a fixed signature, the free algebra over a set $X$ exists, and is given by the set of all $\Sigma$ -terms over $X$ . From the isomorphism above, this means that the left adjoint to the forgetful functor $\mathsf{Alg}(\Sigma) \rightarrow \mathsf{Set}$ exists, and so therefore does the free monad over $\Sigma$ , with $\Sigma^*(X)$ is the set of all terms over the signature. As usual, it is important to consider examples:

Example: As we have seen in earlier posts, the exception monad $(-) + E$ is induced by an equational presentation with a signature consisting of just constant elements for each exception, and no equations. The signature functor is then the constant functor $K_E$ , and so as we saw earlier, the exception monad is the free monad over this functor.

Example: Consider a signature with a single binary operation. This induces a functor:

$\Sigma(X) = X \times X$

For the free monad over this functor, if we write $+$ for the binary operation, the set $\Sigma^*(X)$ consists of terms such as

$x, x_1 + x_2, (x_1 + x_2) + (x_3 + x_4), \ldots$

We can identify these with binary trees, with the leaves labelled by elements of $X$ . So we have constructed a binary tree monad as the free monad over $(-) \times (-)$ .

Example: Extending the previous example, for an arbitrary signature $\Sigma$ , the resulting free monad will have $\Sigma^*(X)$ consisting of trees such that:

The leaves are labelled with elements of $X$ , or constant symbols from the signature.
The internal nodes of arity $n$ are labelled with an operation symbol of the same arity.

Of course, we could consider $\mathsf{Set}$ endofunctors that are not of the form of signature functors. There are certainly plenty of examples where the left adjoint we require exists. In order to get a concrete description of the induced monad, we would need an explicit description of these adjoints. This requires more technical machinery than we have had chance to introduce so far, so we shall defer this topic to a later post.

Ideal Monads

The free monad constructions in the previous section have some nice properties. If we fix an algebraic signature, and consider the free monad over the corresponding signature functor, as we observed, the elements of $\Sigma^*(X)$ can be thought of as certain labelled trees. Looking a bit more carefully:

The trees in the image of the monad unit are the trivial trees with just a leaf labelled by some element of $X$ .
The functor action $\Sigma^*(h)$ just relabels the leaves of trees, according to the function $h$ .
The functor $\Sigma^*$ can be restricted to the non-trivial trees, as these are preserved by the functor action. We shall denote this functor $\Sigma^+$ .
There is a natural isomorphism $\Sigma^*(X) \cong X + \Sigma^+(X)$ .
Using this isomorphism, the monad unit is the left coproduct injection.
The monad multiplication restricts to non-trivial terms as a natural transformation $\mu' : \Sigma^+ \circ \Sigma^* \Rightarrow \Sigma^+$ in the sense that $\mu \circ \kappa_2 \Sigma^* = \kappa_2 \circ \mu'$ .

So free monads “keep the variables separate” in a well behaved way. The categorical structure above allow us to separate the variables from the non-trivial terms. We now abstract these observations to recover another well-studied class of monads.

An ideal monad is a monad $(\mathbb{T},\eta,\mu)$ such that:

There exists an endofunctor $\mathbb{T}^+$ with $\mathbb{T} = \mathsf{Id} + \mathbb{T}^+$ .
The unit is the left coproduct injection.
There exists $\mu' : \mathbb{T}^+ \circ \mathbb{T} \Rightarrow \mathbb{T}^+$ such that $\mu \circ \kappa_2 \mathbb{T} = \kappa_2 \circ \mu'$ .

Example: Free monads are ideal monads. This is clearly true for those induced by signature functors as discussed above, but in fact this result holds for free monads yielded by more general constructions.

Obviously there would be no need for a separate notion if the only examples were free monads.

Example: The list monad we have discussed previously restricts to a non-empty list monad, and this monad is ideal. The list monad is not ideal. If we consider the list monad as the free monoid monad, we can see this algebraically, as $x = x * 1$ , so the unit is not a coproduct injection. Similarly, the non-ideal multiset monad restricts to the non-empty multiset monad, which is ideal.

We do need to be a little bit careful though. The non-empty finite powerset monad is not ideal. Algebraically this monad is the free join semilattice (without unit element) monad. The idempotence equation $x = x \vee x$ then ensures the monad unit cannot be a coproduct injection.

Algebraically, the ideal monads are the ones where no non-trivial equation of the form $x = t$ is provable, as we have seen in the example above.

There are other interesting classes of ideal monads, making conceptual use of this idea of being able to separate the non-trival terms from the variables. These examples are a whole topic in themselves, and we shall reserve them for a later post.

Further background: For those interested in the mathematics of free monads, a good place to start is the final chapter of Barr and Well’s book “Toposes, Triples and Theories”. A good source for background on ideal monads is Ghani and Uustalu’s paper “Coproducts of Ideal Monads”.

Acknowledgements: Ralph Sarkis pointed out several typos in a previous version of this post, which has greatly improved the content.

5 thoughts on “Being Free is Certainly Ideal”

Pingback: Completely Iterative Monads – Dan Marsden
Pingback: Coproducts of Monads – Dan Marsden
Pingback: Graded Monads – Dan Marsden
Pingback: Comonads – Monads Upside Down – Dan Marsden
Pingback: Further Kleisli and Eilenberg-Moore laws – Dan Marsden

Free Monads

Ideal Monads

Share this:

Like this:

Related

5 thoughts on “Being Free is Certainly Ideal”

Leave a Reply Cancel reply