Further Kleisli and Eilenberg-Moore laws

Previously, we encountered two special types of distributive laws. Recall that, for a pair of monads $\mathbb{S} : \mathcal{C} \rightarrow \mathcal{C}$ , $\mathbb{T} : \mathcal{D} \rightarrow \mathcal{D}$ , and a functor $H : \mathcal{C} \rightarrow \mathcal{D}$ :

An Eilenberg-Moore law is a natural transformation of type $\mathbb{T} \circ H \Rightarrow H \circ \mathbb{S}$ , which appropriately preserves the monad structure. Eilenberg-Moore laws were in bijective correspondence with Eilenberg-Moore liftings of $H$ to a functor $\overline{H} : \mathcal{C}^{\mathbb{S}} \rightarrow \mathcal{D}^{\mathbb{T}}$ commuting with the forgetful functors from the Eilenberg-Moore category.
A Kleisli-law is a natural transformation of type $H \circ \mathbb{S} \Rightarrow \mathbb{T} \circ H$ , which appropriately preserve the monad structure. These were in bijection with Kleisli liftings of $H$ to a functor $\underline{H} : \mathcal{C}_{\mathbb{S}} \rightarrow \mathcal{D}_{\mathbb{T}}$ , commuting with the free functors to the Kleisli category.

In this post, we are going to consider the special case of Kleisli and Eilenberg-Moore laws when $H$ is an endofunctor

$H : \mathcal{C} \rightarrow \mathcal{C}$

and both monads $\mathbb{S}$ and $\mathbb{T}$ are equal, which we will refer to as

$\mathbb{M} : \mathcal{C} \rightarrow \mathcal{C}$ .

We shall see that in this special case, both Kleisli and Eilenberg-Moore laws have further applications, beyond their natural use lifting functors to Kleisli and Eilenberg-Moore categories.

Connections to Endofunctor Algebras

As $H$ is now an endofunctor, we can consider the category of endofunctor algebras $\mathsf{Alg}(H)$ . Noting that our monad $\mathcal{M} : \mathcal{C} \rightarrow \mathcal{C}$ lives on the same category as $H$ , it is natural to ask if we can lift it to a monad on $\mathsf{Alg}(H)$ .

As a first step, we assume the existence of a natural transformation

$\lambda : H \circ \mathbb{M} \Rightarrow \mathbb{M} \circ H$

If such a natural transformation exists, this induces an endofunctor

$\overline{M} : \mathsf{Alg}(H) \rightarrow \mathsf{Alg}(H)$

with action on objects

$\overline{M}(A,a : H(A) \rightarrow A) := M(a) \cdot \lambda_A$

and on morphisms

$\overline{M}(h) := M(h)$

So we can at least lift the endofunctor component to the category of algebras. We need to find components for the unit $\overline{\eta} : \mathsf{Id} \Rightarrow \overline{\mathbb{M}}$ and multiplication $\overline{\mu} : \overline{\mathbb{M}} \circ \overline{\mathbb{M}}$ of the lifted monad. The obvious choices are to take:

$\overline{\eta}_{(A,a)} := \eta_{A} \quad\mbox{and}\quad \overline{\mu}_{(A,a)} = \mu_A$

Of course, we must verify that these morphisms are actually $H$ -algebra homomorphisms. It turns out that this is the case if $\lambda$ is a Kleisli law. It is also then straightforward to verify that these components form natural transformations, and satisfy the monad axioms, with the details following fairly directly from the same properties in the base category.

So we have shown that, given a Kleisli law $\lambda : H \circ \mathbb{M} \Rightarrow \mathbb{M} \circ H$

There is an induced monad $(\overline{\mathbb{M}} : \mathsf{Alg}(H) \rightarrow \mathsf{Alg}(H), \overline{\eta}, \overline{\mu})$ .
The forgetful functor $U : \mathsf{Alg}(H) \rightarrow \mathcal{C}$ commutes with the monad structure, in that $\mathbb{M} \circ U = U \circ \overline{\mathbb{M}}$ , $U \circ \overline{\eta} = \eta \circ U$ and $U \circ \overline{\mu} = \mu \circ U$ .

So, given a Kleisli law, the corresponding monad lifts in a very nice way to the category of endofunctor algebras.

Example: Given a commutative monad $\mathbb{M}$ , the canonical natural transformation

$\mathsf{dst}_X : \mathbb{M}(X) \times \mathbb{M}(X) \rightarrow \mathbb{M}(X \times X)$

is a Kleisli law. For example, for the powerset monad is commutative with:

$\mathsf{dst}_X(U,V) = \{ (u,v) \mid u \in U, v \in V \}$

Given an algebra $(A, a : A \times A \rightarrow A)$ , the action of the structure map of $\overline{M}(A, a : A \times A \rightarrow A)$ is:

$(U,V) \mapsto \{ a(u,v) \mid u \in U, v \in V \}$

That is, the algebra operation is applied pointwise on every possible combination of the inputs. A similar strategy can be used to lift any commutative monad to the category of algebras for any polynomial functor.

Connections to Endofunctor Coalgebras

As we have assumed $H$ is an endofunctor, it is equally natural to consider the category of endofunctor coalgebras $\mathsf{Coalg}(H)$ . Again, we should ask ourselves if it is possible to lift the monad $\mathbb{M}$ to the category of coalgebras. As before, as first step it is convenient to assume the existence of a natural transformation of an appropriate type, this time:

$\lambda : \mathbb{M} \circ H \Rightarrow H \circ \mathbb{M}$

With this in place, we can define a functor:

$\overline{\mathbb{M}} : \mathsf{Coalg}(H) \rightarrow \mathsf{Coalg}(H)$

with action on objects:

$\overline{\mathbb{M}}(A, a : A \rightarrow H(A)) := (M(A), \lambda_A \cdot M(a)$

and on morphisms:

$\overline{\mathbb{M}}(h) = \mathbb{M}(h)$

So the existence of any $\lambda$ of the right type allows us to lift endofunctor component of the monad. As in the case of algebras, the obvious choice for the components of the unit and multiplication is to define:

$\overline{\eta}_{(A,a)} := \eta_{A} \quad\mbox{and}\quad \overline{\mu}_{(A,a)} = \mu_A$

As before, we must confirm that these components are legitimate $\mathsf{Coalg}(H)$ -morphisms. This turns out to be the case when $\lambda$ satisfies the axioms of an Eilenberg-Moore law. As before, verifying naturality and the monad axioms can be reduced to the same properties in the base category.

So we have shown that, given an Eilenberg-Moore law $\lambda : \mathbb{M} \circ H \Rightarrow H \circ \mathbb{M}$

There is an induced monad $(\overline{\mathbb{M}} : \mathsf{Coalg}(H) \rightarrow \mathsf{Coalg}(H), \overline{\eta}, \overline{\mu})$ .
The forgetful functor $U : \mathsf{Coalg}(H) \rightarrow \mathcal{C}$ commutes with the monad structure, in that $\mathbb{M} \circ U = U \circ \overline{\mathbb{M}}$ , $U \circ \overline{\eta} = \eta \circ U$ and $U \circ \overline{\mu} = \mu \circ U$ .

So Eilenberg-Moore laws induce well-behaved monads on categories of coalgebras.

Example: For a fixed set $O$ , we consider the endofunctor

$H := O \times (-)$

A coalgebra of this functor is essentially a function of type:

$A \rightarrow O \times A$

From a computer science perspective, we can think of this as modelling a deterministic process with state space $A$ , and after each computation step outputs an element of $O$ , and continues in a new state. Given an Eilenberg-Moore algebra of the powerset monad $o: \mathbb{P}(O) \rightarrow O$ , there is an Eilenberg-Moore law:

$\lambda_X : \mathbb{P}(O \times X) \rightarrow O \times \mathbb{P}(X)$

such that

$\lambda_X(U) = (o(\{ \pi_1(u) \mid u \in U \}), \{ \pi_2(u) \mid u \in U\} )$

So the structure maps of the coalgebra $\overline{\mathbb{P}}(A, a)$ will evaluate a set of states pointwise, using the provided Eilenberg-Moore algebra to calculate a suitable output value from the set of available candidates.

Conclusion

It is interesting that these special cases of Kleisli and Eilenberg-Moore laws allow us to perform further constructions. The fact that Kleisli laws induce monads on categories of algebras is probably not that shocking, but that Eilenberg-Moore laws have something to do with monads on categories of coalgebras is a bit more of a surprise. Probably the main takeaway is that, yet again, the ability to suitably commute monad structure with a natural transformation arises in many situations and is an important idea.

Attendees at the recent Midlands Graduate School who attended my string diagrams course may recognise some of the ideas in this post, as the constructions and calculations are in my opinion significantly easier to grasp graphically.

Further reading: I am not aware of a source for the observations above, although I assume it is folklore / well-known if you hang out at the right sort of parties. I would be interested in knowing if there is a published source to cite. Bart Jacobs wonderful book “Introduction to Coalgebra” has inductive constructions for Kleisli and Eilenberg-Moore laws, which would be useful in playing with the ideas discussed in this post.

Acknowledgments: Thanks to Sjoerd Visscher for spotting a distracting typo in an earlier version.

Connections to Endofunctor Algebras

Connections to Endofunctor Coalgebras

Conclusion

Share this:

Like this:

Related

Leave a Reply Cancel reply