Composition and Distributive Laws

A common theme in many scientific disciplines is the desire to build up complicated objects out of simpler parts. This compositional perspective allows us to work in a modular fashion, rather than addressing each new problem as a monolith that must be investigated from scratch.

With this in mind, given two monads $\mathbb{T}, \mathbb{S}$ , it would be very convenient if the composite endofunctor $\mathbb{T} \circ \mathbb{S}$ was also a monad in some canonical way. Unfortunately, this is not always the case. Although this is initially disappointing, the study of when such composites are monads is a rich and interesting subject.

Composing Endofunctors

We begin with some simple concrete examples, to get a sense of the various possibilities when we try to compose two monads as endofunctors. We will say that an endofunctor $F$ can be given the structure of a monad, if there exists any $\eta : \mathsf{Id} \Rightarrow F$ and $\mu : F \circ F \Rightarrow F$ satisfying the unit and associativity axioms. We then note the following instructive examples:

Trivially, for any monad $\mathbb{S}$ , both the composites with the identity monad $\mathsf{Id} \circ \mathbb{S}$ and $\mathbb{S} \circ \mathsf{Id}$ carry the structure of a monad. As an equally trivial corollary of this observation, as there are endofunctors that carry multiple monad structures, this will also be a possibility for composite monads.
For any monad $\mathbb{S}$ , its post composition with the exception monad $\mathbb{S}(- + E)$ carries the structure of a monad.
The composition of the powerset monad with itself $\mathbb{P} \circ \mathbb{P}$ does not carry the structure of a monad. This was shown by Klin and Salamanca “Iterated Covariant Powerset is not a Monad” in 2018.

This is a pretty mixed picture. There are monads such that composition with their endofunctor on one or both sides results in a monad every time, and at the other extreme, some monads can’t even be composed with themselves.

Distributive Laws

Our aim now is to try and deduce some sufficient conditions under which monads compose. We will consider two monads $(\mathbb{S}, \eta^{\mathbb{S}}, \mu^{\mathbb{S}})$ and $(\mathbb{T},\eta^{\mathbb{T}}, \mu^{\mathbb{T}})$ on the same base category. Our notation is a bit fussier than normal, using superscripts on the unit and counit to make it clear which monad is intended.

We would like to find a monad structure on $\mathbb{T} \circ \mathbb{S}$ . There is an obvious choice for the unit:

$\eta^{\mathbb{T}} \circ \eta^{\mathbb{S}} : \mathsf{Id} \Rightarrow \mathbb{T} \circ \mathbb{S}$

If we trying composing the two multiplications together in the same way, we get:

$\mu^{\mathbb{T}} \circ \mu^{\mathbb{S}} : \mathbb{T} \circ \mathbb{T} \circ \mathbb{S} \circ \mathbb{S} \Rightarrow \mathbb{T} \circ \mathbb{S}$

We now see a problem, we have a natural transformation of type $\mathbb{T} \circ \mathbb{T} \circ \mathbb{S} \circ \mathbb{S} \Rightarrow \mathbb{T} \circ \mathbb{S}$ , not the type $\mathbb{T} \circ \mathbb{S} \circ \mathbb{T} \circ \mathbb{S} \Rightarrow \mathbb{T} \circ \mathbb{S}$ which we require. A natural attempt to address this problem would be to introduce some natural transformation $\lambda : \mathbb{S} \circ \mathbb{T} \Rightarrow \mathbb{T} \circ \mathbb{S}$ , and form the composite:

$(\mu^{\mathbb{T}} \circ \mu^{\mathbb{S}}) \cdot (\mathsf{Id}_{\mathbb{T}} \circ \lambda \circ \mathsf{Id}_{\mathbb{S}}) : \mathbb{T} \circ \mathbb{S} \circ \mathbb{T} \circ \mathbb{S} \Rightarrow \mathbb{T} \circ \mathbb{S}$

Of course, we can’t just use any old natural transformation $\lambda$ , it will need to satisfy some axioms in order for the resulting construction to be a monad. It is an interesting exercise to try and deduce these by attempting a proof, which I would highly recommend.

Sufficient conditions are two unit axioms:

$\lambda \cdot (\eta^{\mathbb{S}} \circ \mathbb{T}) = \mathbb{T} \circ \eta^{\mathbb{S}} \qquad \lambda \cdot (\mathbb{S} \circ \eta^{\mathbb{T}}) = \mathbb{S} \circ \eta^{\mathbb{T}}$

and two multiplication axioms:

$\lambda \cdot (\mathbb{T} \circ \mu^{\mathbb{S}}) = (\mathbb{T} \circ \mu^{\mathbb{S}}) \cdot (\lambda \circ \mathbb{S}) \cdot (\mathbb{S} \circ \lambda) \qquad \lambda \cdot (\mathbb{S} \circ \mu^{\mathbb{T}}) = (\mu^{\mathbb{T}} \circ \mathbb{S}) \cdot (\mathbb{T} \circ \lambda) \cdot (\lambda \circ \mathbb{T})$

A natural transformation $\lambda : \mathbb{S} \circ \mathbb{T} \Rightarrow \mathbb{T} \circ \mathbb{S}$ satisfying these four equations is known as a distributive law. This construction was first discovered by Jon Mock Beck, and they are sometimes referred to as Beck distributive laws for emphasis. Interestingly, the required axioms are exactly that $\lambda$ is both a Kleisli law and an Eilenberg-Moore law, which we encountered previously.

Of course, we haven’t actually demonstrated that such natural transformations can be found, so it’s time for some examples.

Example: For the free monoid (list) monad $\mathbb{L}$ , and the Abelian group monad $\mathbb{A}$ , there is a distributive law:

$\lambda : \mathbb{L} \circ \mathbb{A} \Rightarrow \mathbb{A} \circ \mathbb{L}$

We can think of the elements of $(\mathbb{L} \circ \mathbb{A})(X)$ as equivalence classes of products-of-sums, for example:

$(x_1 + x_2) \times (x_3 + x_4)$

If we apply the usual distributivity axiom for multiplication over addition, we get the term:

$x \times (y + z) = x \times y + x \times z$

our example term becomes a sum-of-products:

$x_1 \times x_3 + x_1 \times x_4 + x_2 \times x_3 + x_2 \times x_4$

which is an element of $(\mathbb{A} \circ \mathbb{L})(X)$ . This operation on terms is the idea behind the action of the distributive law, and also inspires the name distributive law. The resulting monad in the free ring monad.

Example: Again for the list and Abelian group monads, there is no distributive law composing in the opposite order, of the type:

$\mathbb{A} \circ \mathbb{L} \Rightarrow \mathbb{L} \circ \mathbb{A}$

This gives us an example of a pair of monads with a distributive law in one order, but not the other.

Example: Similarly to the ring monad example, there is a distributive law between the list and powerset monads:

$\mathbb{L} \circ \mathbb{P} \Rightarrow \mathbb{P} \circ \mathbb{L}$

The action of this distributive is:

$[X_1,\ldots,X_n] \mapsto \{ [x_1,\ldots,x_n] \mid x_i \in X_i \}$

As the powerset monad is the free complete join semilattice monad, and list is the free monoid monad, we can view the action of this distributive law algebraically as:

$\bigvee X_1 \otimes \ldots \bigvee X_n = \bigvee \{ x_1 \otimes \ldots \otimes x_n \mid x_i \in X_i \}$

Essentially, this distributive law comes from axioms of the form:

$x \otimes \bigvee Y = \bigvee \{ x \otimes y \in Y \} \qquad \bigvee X \otimes y = \{ x \otimes y \mid x \in X \}$

The algebras of the resulting monad are known as quantales.

Example: As a more computational example, consider the exception monad for any object $E$ , and and arbitrary monad $\mathbb{T}$ . There is a distributive law:

$\mathbb{T} + E \Rightarrow \mathbb{T}(- + E)$

Abstractly, this law has components:

$\mathbb{T}(X) + E \xrightarrow{[\mathbb{T}(\kappa_1), \eta^{\mathbb{T}} \circ \kappa_2]} \mathbb{T}(X + E)$

where $\kappa_1$ and $\kappa_2$ are the coproduct injections. For example, if we take monad $\mathbb{T}$ to be the list monad, the distributive law acts on the left component of the coproduct as:

$(0,[x_1,\ldots,x_n]) \mapsto [(0,x_1),\ldots,(0,x_n)]$

and on the right component:

$(1,e) \mapsto [(1,e)]$

The next example illustrates that distributive laws are only one aspect of the composition question for monads.

Example: As another negative result, there is no distributive law for the list monad over itself $\mathbb{L} \circ \mathbb{L} \Rightarrow \mathbb{L} \circ \mathbb{L}$ , but $\mathbb{L} \circ \mathbb{L}$ does carry the structure of a monad (as was pointed out by Bartek Klin). So the lack of a distributive law does not spell doom for finding any monad structure at all on the composite endofunctor.

Given the previous example, one might ask what are the advantages of knowing the composite monad $\mathbb{T} \circ \mathbb{S}$ arises via a distributive law? The key point is that we then get sensible relationships between the composite and its component parts. There are monad morphisms $\mathbb{S} \Rightarrow \mathbb{T} \circ \mathbb{S}$ and $\mathbb{T} \Rightarrow \mathbb{T} \circ \mathbb{S}$ . These in turn induce functors between the corresponding Kleisli and Eilenberg-Moore categories, as we have seen previously. Furthermore, $\mathbb{T}$ lifts to a monad on the Eilenberg-Moore category of $\mathbb{S}$ , and $\mathbb{S}$ lifts to a monad on the Kleisli category of $\mathbb{T}$ .

Conclusion

We have only touched on the topic of distributive laws in this post. Hopefully it’s fairly obvious to see that these ideas will generalise to the 2-categorical and bicategorical definitions of monads we recently discussed. There are results giving sufficient conditions, either for when a distributive laws does exist, or precluding that possibility. There is also a lot of open ground for new results in this area, showing that in some ways our understanding of monads is still rather naive.

For those interested in distributive laws, I would thoroughly recommend Jon Beck’s original 1969 paper, which is a very enjoyable read.

One final note of caution. Distributive laws are a notorious source of difficulty and errors in the literature. If you are working with them, or depending on the results of other, it is worth putting in extra effort to make sure you are on firm ground.

One thought on “Composition and Distributive Laws”

Pingback: Distributive Laws are Monads – Dan Marsden

Composing Endofunctors

Distributive Laws

Conclusion

Share this:

Like this:

Related

One thought on “Composition and Distributive Laws”

Leave a Reply Cancel reply