Commutative Monads

A commutative monad is a monoid in the category of lax symmetric monoidal endofunctors

We have seen the standard result that monad on a category $\mathcal{C}$ is a monoid in the endofunctor category

([\mathcal{C},\mathcal{C}],\otimes, \mathsf{Id})

We also discussed a similar result that a strong monad is a monoid in the category of strong endofunctors. That result allowed us to very directly read off what a distributive law of strong monads should be. The aim of this post is to continue this pattern for commutative monads, with the aim of recovering the definition of distributive law of commutative monads. This will turn out to take a bit more effort.

What we are not going to do

The first thing we should note is that we are not heading towards a result of the form:

A commutative monad is a commutative monoid in…

Unfortunately the term commutative monad hints at the wrong intuition in this regard.

Commutative Monads are Monoidal Monads

Now we have avoided a potential banana skin, onto the main story.

For a strong monad

(\mathbb{T} : \mathcal{C} \rightarrow \mathcal{C}, \eta, \mu, \mathsf{st} : X \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(X \otimes Y))

on a symmetric monoidal category

(\mathcal{C}, \otimes, I)

if the monad is commutative, the induced double strength

\mathsf{dst} : \mathbb{T}(X) \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(X \otimes Y)

gives our monad a symmetric monoidal structure. That is, $\mathbb{T}$ is a lax symmetric monoidal functor, and the unit and multiplication are monoidal natural transformations. In fact, we can also go in the other direction, given a symmetric monoidal monad with coherence map

\varphi : \mathbb{T}(X) \otimes \mathbb{T}(X) \rightarrow \mathbb{T}(X \otimes Y)

we can recover a corresponding left and right strength as the composites:

\varphi \cdot (\mathsf{id} \otimes \eta) : \mathbb{T}(X) \otimes Y \rightarrow \mathbb{T}(X \otimes Y)\quad\text{and}\quad \varphi \cdot (\eta \otimes \mathsf{id}) : X \otimes \mathbb{T}(Y) \rightarrow \mathbb{T}(X \otimes Y)

and we can travel back and forth between these two points of view. That is, a commutative monad is the same thing as a symmetric monoidal monad. Rephrasing again, for a symmetric monoidal category:

A commutative monad is a monoid in the category of lax symmetric monoidal endofunctors.

Distributive Laws of Commutative Monads

With the above observation in mind, a distributive law of commutative monads should be an ordinary distributive law

\lambda : \mathbb{S} \otimes \mathbb{T} \Rightarrow \mathbb{T} \otimes \mathbb{S}

which is also a monoidal natural transformation. Concretely, this means

\mathbb{T} \mathsf{dst}^{\mathbb{S}} \cdot \mathsf{dst}^{\mathbb{T}} \cdot \lambda \otimes \lambda = \lambda \cdot \mathbb{S} \mathsf{dst}^{\mathbb{T}} \cdot \mathsf{dst}^{\mathbb{S}}

The definition of a distributive law of commutative monads appearing in the literature in independent work of Wolff and Jacobs is a distributive law of strong monads, satisfying the additional equation

\lambda \cdot \mathbb{S}\mathsf{st’}^{\mathbb{T}} \cdot \mathsf{st}^{\mathbb{S}} = \mathbb{T}\mathsf{st}^{\mathbb{S} \cdot \mathsf{st’}^{\mathbb{T}}}

which involves a slightly odd combination of left and right strengths. Its not immediately obvious how the equation we have derived relates to the Wolff Jacobs conditions. So we have work to do.

A reasonably straightforward direct calculation shows that our equation implies the Wolff Jacobs conditions. Trying to proceed directly in the other direction proves significantly more painful.

Instead, we proceed indirectly. It is not too hard to show that composing two commutative monads using a distributive law of commutative monads result in a commutative monad. This is not a big shock, as it is their very purpose. By an observation of Beck, we can recover a distributive law from its composite monad by suitably precomposing the composite multiplication with the units of the component monads. We then note

The component monads are commutative by assumption, and so their units are monoidal.
The composite monad is commutative as a result of the Wolff Jacobs conditions, and so its multiplication is monoidal.
Becks composite recovering the distributive law combines only monoidal components.

Therefore, a distributive law satisfying the Wolff Jacobs conditions is a monoidal natural transformation.

Summing up, a distributive law of commutative monads is an ordinary distributive law that equivalently either:

Satisfies the Wolff Jacobs equations directly involving strength, or
Is a monoidal natural transformation

Summary

Monads and their distributive laws are 2-categorical phenomena, and so the correct definition of distributive law should be inevitable.

In a previous post we saw that the notion of distributive of strong monads appearing in the literature drops out directly from the abstract framework. In this post we moved on to look at the accepted notion of distributive law of commutative monads. The situation was more subtle, but it is reassuring that after a bit of massaging, instantiating the abstract definition yields the same construction.

Distributive laws of commutative monads appear in:

Wolff “Commutative Distributive Laws”
Jacobs “Semantics of weakening and contraction”

Quotients of Commutative, Affine and Relevant Monads

We have seen that nice properties such as being commutative, affine, or relevant can be transferred to strong submonads. A natural question to ask is whether something similar applies to quotients? In fact, we can apply the tricks we’ve already seen to get straight to some answers.

As strong monad morphisms commute with double strengths, if

\varphi : (\mathbb{T}, \mathsf{st}) \Rightarrow (\mathbb{Q}, \mathsf{st})

is a strong monad morphism, and $\mathbb{T}$ is commutative, we can immediately show

\mathsf{dst}^{\mathbb{Q}} \cdot \varphi \otimes \varphi = \mathsf{dst}^{\mathbb{Q}’} \cdot \varphi \otimes \varphi

If $\varphi \otimes \varphi$ is component-wise epimorphic, then

\mathsf{dst}^{\mathbb{Q}} = \mathsf{dst}^{\mathbb{Q}’}

and $\mathbb{Q}$ is commutative. Even if we restrict attention to where the monoidal structure is products, this condition is not as straightforward as that for monomorphisms. Fortunately there are many special cases where $\varphi$ being a component-wise epimorphism implies $\varphi \times \varphi$ is. In particular, this works nicely for $\mathsf{Set}$ -monads. As all natural transformation are strong in that case, we have

Quotients of commutative monads are commutative.

Affine, Relevant and Cartesian Monads

\varphi : (\mathbb{T}, \mathsf{st}) \Rightarrow (\mathbb{Q}, \mathsf{st})

is a strong monad morphism, and $\mathbb{T}$ is affine, then using the same calculational properties as we did for submonads, but in reverse, we can conclude

\langle \mathbb{Q}\pi_1, \mathbb{Q}\pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{Q}} \cdot \varphi \times \varphi = \varphi \times \varphi

and so if $\varphi \times \varphi$ is component-wise epimorphic

\langle \mathbb{Q}\pi_1, \mathbb{Q}\pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{Q}} = \mathsf{id}

If we restrict attention to $\mathsf{Set}$ -monads, using the result of the previous section, we can conclude

Quotients of affine monads are affine.

A very similar argument allows us to conclude that for $\mathsf{Set}$ -monads

Quotients of relevant monads are relevant.

Combining both these observations gives

Quotients of Cartesian monads are Cartesian.

Algebraic Interpretation

As usual, it pays to see if we use algebraic intuition to justify our conclusions. If we consider $\mathsf{Set}$ -monads presented by operations and equations, being commutative, affine, relevant or Cartesian requires that certain equations between terms hold. We can think of quotient monads as imposing extra equations between terms, so it is unsurprising quotient monads continue to have these nice properties.

Summary

The conclusions above are less general than for submonads. This is because epimorphisms do not interact as nicely with products as monomorphisms do. In the case of $\mathsf{Set}$ -monads everything was about as well-behaved as we could possibly hope.

Affine and Relevant Strong Submonads

We have seen that we can transfer commutativity to strong submonads. Can we transfer other good properties, such as being an affine or relevant monad as well?

Another Commutativity Property

As we are now interested in affine and relevant monads, this post will assume we are working in a category with finite products. We have seen that strong natural transformations commute with double strength. This property will be crucial again today, but we will also need another simple equation.

For a natural transformation

\varphi : F \Rightarrow G

the following equation holds

\varphi \times \varphi \cdot \langle F \pi_1, F \pi_1 \rangle = \langle G \pi_2, G \pi_2 \rangle \cdot \varphi

The proof is a straightforward combination of properties of products and naturality.

Affine Monads

Assume that $\mathbb{T}$ is a affine monad. That is, it is a commutative monad such that the following equation holds

\langle \mathbb{T} \pi_1, \mathbb{T} \pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{T}} = \mathsf{id}

\varphi : (\mathbb{S}, \mathsf{st}) \Rightarrow (\mathbb{T}, \mathsf{st})

a strong monad morphism, then

\varphi \times \varphi \cdot \langle \mathbb{S}\pi_1, \mathbb{S}\pi2 \rangle \cdot \mathsf{dst}^{\mathbb{S}} = \langle \mathbb{T}\pi_1, \mathbb{T}\pi2 \rangle \cdot \varphi \cdot \mathsf{dst}^{\mathbb{S}} = \langle \mathbb{T} \pi_1, \mathbb{T} \pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{T}} \cdot \varphi \times \varphi = \varphi \times \varphi

If $\varphi$ is component-wise a monomorphism, then so is $\varphi \times \varphi$ , and so

\langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle \cdot \mathsf{dst}^{\mathbb{S}} = \mathsf{id}

Combining this with the results of the previous post, $\mathbb{S}$ is then an affine monad. In categories with pullbacks, we can strengthen this to

Strong submonads of affine monads are affine.

When the base category is set we can go further, to the slogan

Submonads of affine monads are affine.

Relevant Monads

The argument for relevant monads is even easier. Assume $\mathbb{T}$ is a relevant monad, so the following equation holds:

\mathsf{dst}^{\mathbb{T}} \cdot \langle \mathbb{T} \pi_1, \mathbb{T} \pi_2 \rangle = \mathsf{id}

\varphi : (\mathbb{S}, \mathsf{st}) \Rightarrow (\mathbb{T}, \mathsf{st})

is a strong monad morphism, then:

\varphi \cdot \mathsf{dst}^{\mathbb{S}} \cdot \langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle = \mathsf{dst}^{\mathbb{T}} \cdot \varphi \times \varphi \cdot \langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle = \mathsf{dst}^{\mathbb{T}} \cdot \langle \mathbb{T} \pi_1, \mathbb{T} \pi_2 \rangle \cdot \varphi = \varphi

and so if $\varphi$ is component-wise a monomorphism

\mathsf{dst}^{\mathbb{S}} \cdot \langle \mathbb{S} \pi_1, \mathbb{S} \pi_2 \rangle = \mathsf{id}

and from the results of the previous post, $\mathbb{S}$ is relevant. For categories with pullbacks, we have the slogan

Strong submonads of relevant monads are relevant.

and in the case of set monads we get the punchier

Submonads of relevant monads are relevant.

Cartesian Monads

As Cartesian monads are simply monads which are both affine and relevant, we can combine the previous two results to deduce that:

Strong submonads of Cartesian monads are Cartesian.

Algebraic Intuitions

For set monads, being affine or relevant requires that certain equations hold between terms. If we think of a submonad as dropping some of the algebraic structure whilst retaining all applicable equations, intuitively we would expect being affine or relevant to still hold.

Summary

Commutative, affine, relevant and Cartesian monads were important when we discussed both well-known and more recent sufficient conditions for the existence of distributive laws. These results allow us to extract new such monads from those we already understand.

Commutativity of Strong Submonads

In this post we begin to explore transferring nice properties of monads to their submonads. A key tool will be strong monad morphisms. These are monad morphisms which are also strong natural transformations.

Strong Natural Transformations and Right-Strength

In a symmetric monoidal category $\mathcal{C}$ , given a strong endofunctor

(F, \mathsf{st} : X \otimes F(Y) \Rightarrow F(X \otimes Y)

we can define a right-strength natural transformation

\mathsf{st}’ : F(X) \otimes Y \Rightarrow F(X \otimes Y)

by pre and post-composition with the symmetry of $\mathcal{C}$ .

For strong endofunctors

(F,\mathsf{st})\quad\text{and}\quad (G, \mathsf{st})

requiring that an ordinary natural transformation

\varphi : F \Rightarrow G

be a strong natural transformation is equivalent to requiring it commutes with the left-strengths as follows:

\mathsf{st}’ \cdot \varphi \otimes \mathsf{id} = \varphi \cdot \mathsf{st}’

We see that in this case, being a strong natural transformation can equivalently be phrased in terms of commuting with either the left or right strength. This gives us another convenient equation we can apply in calculations.

Strong Monad Morphisms and Double Strengths

Recall for a strong monad on a monoidal category, using the left and right strength, and the monad multiplication, we can define two double strength natural transformations:

\mathsf{dst}, \mathsf{dst}’ : \mathbb{T}(X) \otimes \mathbb{T}(Y) \Rightarrow \mathbb{T}(X \otimes Y)

A monad is commutative when the double strengths are equal.

For a strong monad morphism

\varphi : (\mathbb{S},\mathsf{st}) \Rightarrow (\mathbb{T}, \mathsf{st})

we can apply commutativity with respect to the left and right strength, and the monad morphism assumption to show that $\varphi$ commutes with both double strengths. That is:

\mathsf{dst}^{\mathbb{T}} \cdot \varphi \otimes \varphi = \varphi \cdot \mathsf{dst}^{\mathbb{S}} \quad\text{and}\quad \mathsf{dst}^{\mathbb{T}’} \cdot \varphi \otimes \varphi = \varphi \cdot \mathsf{dst}^{\mathbb{S}’}

We have added explicit superscripts to indicate to which monad each double strength corresponds.

This is a key property of strong monad morphisms that allows us to prove some interesting results.

Strong Submonads of Commutative Monads

If we have a $\varphi$ as above, assuming the monad $\mathbb{T}$ is commutative, we can calculate:

\varphi \cdot \mathsf{dst}^{\mathbb{S}} = \mathsf{dst}^{\mathbb{T}} \cdot \varphi \otimes \varphi = \mathsf{dst}^{\mathbb{T}’} \cdot \varphi \otimes \varphi = \varphi \cdot \mathsf{dst}^{\mathsf{S}’}

where the middle equality uses the commutativity assumption. Now if $\varphi$ is component-wise a monomorphism, we can conclude that:

\mathsf{dst}^{\mathbb{S}} = \mathsf{dst}^{\mathbb{S}’}

and so the monad $\mathbb{S}$ is commutative.

In full generality, we need the component-wise monomorphism assumption, but if the base category has pullbacks, this is equivalent to requiring $\varphi$ be a monomorphism. In this case it seems appropriate to use the following slogan:

A strong submonad of a commutative monad is commutative.

It is not hard to verify that every natural transformation between set endofunctors is strong. We then get the snappier slogan:

A submonad of a commutative monad is commutative.

Algebraic Intuitions

If we present a set monad by algebraic operations and equations, we have seen that commutativity of a monad is equivalent to all the algebraic operations commuting with each other. If we think of a submonad as dropping some of the algebraic structure whilst retaining all the applicable equations, it is perhaps unsurprising that the monad remains commutative.

Summary

Commutativity is a valuable property to identify in a monad. As verifying commutativity can be a bit of a pain, being able to transfer it to strong submonads can be very convenient.

We will see in forthcoming posts that this is not the only nice property we can transfer along strong monad morphisms.

Commutativity Algebraically

Recall the substitution notation we have been using:

$t[t_x / x \mid x \in X]$

denotes the term $t$ , with each $x \in X$ simultaneously replaced by the term $t_x$ . For an equational presentation $(\Sigma, E)$ , inducing a monad $\mathbb{T}$ , consider a pair:

$([s],[t]) \in \mathbb{T}(X) \times \mathbb{T}(Y)$

where $[t]$ denotes an equivalence class with representative term $t$ . We can then write the action of the first double strength map in terms of representatives and substitutions as:

$\mathsf{dst}([s],[t]) = [t[s[(x,y)/x \mid x \in X] / y \mid y \in Y]]$

and the second:

$\mathsf{dst}'([s],[t]) = [s[t[(x,y)/y \mid y \in Y] / x \mid x \in X]]$

Therefore, the resulting monad is commutative if and only if for all $s,t$ , the following equality is provable in equational logic:

$t[s[(x,y)/x \mid x \in X] / y \mid y \in Y] = s[t[(x,y)/y \mid y \in Y] / x \mid x \in X]$

We shall call this the commutativity condition.

The substitutions can be made a bit easier to read with a change of notation. For two terms $s,t$ , let $x_1,\ldots,x_m$ and $y_1,\ldots,y_n$ be a choice of enumeration of the variables appearing in the two terms. We can then write them as

$s(x_1,\ldots, x_m) \quad\mbox{ and }\quad t(y_1,\ldots,y_n)$

and writing substitution in the natural way, the commutativity condition becomes:

$t(s((x_1,y_1),\ldots,(x_m,y_1)),\ldots, s((x_1,y_n),\ldots,(x_m,y_n))) = s(t((x_1,y_1),\ldots,(x_1,y_n)),\ldots,t((x_m,y_1),\ldots,(x_m,y_n)))$

That’s an awful lot of formal notation and brackets to deal with. Let’s consider some implications of this condition to build intuition for what it means in practice.

Example: Consider a presentation with binary operations $+$ and $\times$ . The action of the double strengths on $[x + x'] \in \mathbb{T}(X)$ and $[y \times y'] \in \mathbb{T}(Y)$ are:

$\mathsf{dst}([x + x'], [y \times y']) = [((x,y) + (x',y)) \times ((x,y') + (x',y'))]$

and

$\mathsf{dst}'([x + x'], [y \times y']) = [((x,y) \times (x,y')) + ((x',y) \times (x',y'))]$

If the monad $\mathbb{T}$ is commutative, the following equality must be provable in equational logic:

$((x,y) + (x',y)) \times ((x,y') + (x',y')) = ((x,y) \times (x,y')) + ((x',y) \times (x',y'))$

As a special case of this observation, any monad presented by a binary operation must satisfy the following equation:

$((x,y) + (x',y)) + ((x,y') + (x',y')) = ((x,y) + (x,y')) + ((x',y) + (x',y'))$

If $+$ is associative, this boils down to:

$(x,y) + (x',y) + (x,y') + (x',y') = (x,y) + (x,y') + (x',y) + (x',y')$

The only difference between the two terms is the order of the middle two constants, so this equality will certainly hold for any associative commutative binary operation. This condition is satisfied in many natural algebraic structures, and does exhibit a very weak relationship between commutative operations and commutative monads.

An instructive boundary case is the following.

Example: Consider two terms $s,t$ in which no variables appear. These are constants in our equational theory. The commutativity condition implies that:

$s = t$

as all the variable substitutions become trivial. Therefore any equational presentation of a commutative monad can have at most one distinct constant term. We have already encountered this phenomenon. The exception monad is only commutative when there is at most one exception constant.

“Constant counting” can be a quick way to discount the possibility that a monad for an equational presentation is commutative. For example the monads corresponding to commutative rings or rigs (semirings) cannot be commutative as they have distinct constant symbols for the additive and multiplicative structures. These are further natural examples of monads with all the binary operations in the signature commutative, but the resulting monads are not commutative.

Another simple case is worth considering.

Example: Let $s \in \mathbb{T}(X)$ and $t \in \mathbb{T}(Y)$ be terms in which only one variable appears, say $x_0$ and $y_0$ respectively. Then the left hand side of the commutativity condition is:

$t[s[(x,y)/x \mid x \in X] / y \mid y \in Y] = t(s((x_0,y_0)))$

and the right hand side is:

$s[t[(x,y)/y \mid y \in Y] / x \mid x \in X] = s(t((x_0,y_0)))$

So for $\mathbb{T}$ to be commutative, each pair of unary terms must satisfy $s(t(x)) = t(s(x))$ .

As an application of this special case, we introduce another commonly considered monad. For a fixed monoid $(M,\times,1)$ the writer monad has:

Endofunctor: The endofunctor is the product $M \times (-)$ .
Unit: $\eta(x) = (1,x)$ .
Multiplication: $\mu(m,(n,x)) = (m \times n, x)$ .

Computationally, this monad can be seen as encoding computations that also record some additional output such as logging. The monoid structure combines the outputs from successive computations. Algebraically, it corresponds to actions of the monoid $M$ .

The writer monad has an equational presentation with one unary operational symbol for each element of the monoid, and equations:

$1(x) = x$ .
$p(q(x)) = r(x)$ if and only if $p \times q = r$ in the monoid.

Using our observation above, the writer monad is commutative if and only if the monoid $M$ is commutative. So in this case, we do see a strong connection between the monadic and algebraic notions of commutativity.

Another useful boundary case is to consider what the commutativity condition means for variables.

Example: Consider a variable $x_0$ and an an arbitrary term $t$ . The left hand side of the commutativity condition is:

$t[x_0[(x,y)/x \mid x \in X] / y \mid y \in Y] = t[(x_0,y) \mid y \in Y]$

and the right hand side is:

$x_0[t[(x,y)/y \mid y \in Y] / x \mid x \in X] = t[(x_0,y) \mid y \in Y]$

So variables always satisfy the commutativity condition with respect to any other term. With hindsight, maybe we should not find this too surprising.

We will now consider an important example, which will point the way to getting a better handle on the unpleasant looking general commutativity condition we deduced above.

Example: We now consider an equational presentation with a constant term $0$ and a binary term $x + x'$ and a unary term $h$ . The equations yielded by the commutativity condition for the pairs $([h],[0])$ and $([h],[x + x'])$ are:

$h(0) = 0 \quad\mbox{ and }\quad h((x,y) + (x',y)) = h((x,y')) + h((x',y'))$

we can simplify the second condition by renaming variables, and we arrive at the conditions:

$h(0) = 0\quad\mbox{ and }\quad h(x + x') = h(x) + h(x')$

These conditions should hopefully look familiar, they are exactly the equations we require for $h$ to be a homomorphism with respect to $+$ and $0$ .

We now aim to make the connection with homomorphisms from the previous example precise by making two observations:

For positive natural $k$ and set $Z$ , the term $s(x_1,\ldots,x_m)$ induces an $m$ -ary operation on $\mathbb{T}^k(Z)$ with action $(([t_{1,1}],\ldots,[t_{1,k}]),\ldots,([t_{m,1},\ldots,t_{m,k}])) \mapsto ([s(t_{1,1},\ldots,t_{m,1})],\ldots,[s(t_{1,k},\ldots,t_{m,k})])$ .
Similarly, the term $t(y_1,\ldots,y_m)$ induces an $n$ -ary function $\mathbb{T}(Z)^{n} \rightarrow \mathbb{T}(Z)$ with action $([t_1],\ldots, [t_n]) \mapsto [t(t_1,\ldots,t_n)]$

The homomorphism condition is equivalent to saying that the $n$ -ary function $\mathbb{T}(X \times Y)^{n} \rightarrow \mathbb{T}(X \times Y)$ induced by $t$ is a homomorphism with respect to the $m$ -ary operation induced by $s$ . In this sense, the commutativity conditions can be rephrased as all the terms are homomorphisms with respect to each other.

From the algebraic perspective a monad is commutative in the sense that all terms can be commuted past each other as homomorphisms.

Being commutative has nothing to do with being commutative

In explanations about commutative monads, it is common to see a passing remark such as “as we’d expect, the Abelian monoid monad is commutative”. Now I might be over-interpreting these comments, but they seem to imply that the monad being commutative is related to the algebraic structure having a commutative binary operation. Now it is true that the Abelian monoid (a.k.a. multiset) monad is commutative, and several other commutative monads are induced by algebraic structures with commutative binary operations, but how well does this intuition hold together more generally?

Firstly, we consider if being a commutative monad implies commutativity of the binary operations in equational presentations.

Counterexample: We saw last time that the finite distribution monad is commutative. This monad is isomorphic to the monad presented by a family of binary operations $\{+^r \mid r \in (0,1) \}$ satisfying the following equations:

Idempotence: For all $r \in (0,1)$ , $x +^r x = x$ .
Pseudo-commutativity: For all $r \in (0,1)$ , $x +^r y = y +^{1 - r} x$ .
Pseudo-associativity: For all $r,s \in (0,1)$ , $x +^r (y +^s z) = (x +^{\frac{r}{r + (1-r)s}} y) +^{r + (1-r)s} z$

Algebras for this theory are called convex algebras. Intuitively, the operation $x +^r y$ forms the probabilistic mixture $rx + (1-r)y$ and the axioms can be understood from this point of view. The pseudo-associativity axiom is particularly unpleasant to look at, but is easier to understand in terms of re-bracketing weighted binary combinations.

The axioms presenting convex algebras don’t have explicit commutativity equations for all the binary operations, but they might be derivable. To make sure this isn’t the case, we consider the concrete description of the free algebras that we get from the isomorphism to the finite distribution monad.

Specifically, the free algebra on $X$ has universe finitely supported convex sums over $X$ , and the operations are the obvious weighted sums:

$(\sum_i p_i x_i) +^r (\sum_j q_j y_j) = \sum_i (r \times p_i) x_i + \sum_j ((1-r) \times q_j) y_j$

This operation is clearly not commutative, except when $r = \frac{1}{2}$ . So there is a commutative monad presented by an algebraic theory with (many different) non-commutative algebraic operations.

(I thank Maaike Zwart for suggesting this natural concrete counterexample)

What about the other direction, does an equational presentation where all the binary operations are commutative imply commutativity?

Counterexample: We have already seen that the exception monad $(-) + E$ is only commutative if $E$ is a singleton set. The exception monad is isomorphic to the monad for an equational theory with constant symbols the elements of $E$ , and no equations. So there are both commutative and non-commutative monads with presentations containing no binary operations at all.

The previous counterexample is a bit too trivial to be satisfactory, as there are no binary operations involved at all, and we’re quantifying over the empty set when making statements about commutativity in the algebraic sense.

As a second attempt, we shall synthesise an equational presentation in which the only components involved are commutative binary operations.

Counterexample: Consider an equational presentation with two binary operations $\oplus$ and $\otimes$ , with the only equations being those requiring both operations are commutative. We consider the action of the double strengths on the equivalence classes $[w \oplus x]$ and $[y \otimes z]$ . For the first:

$\mathsf{dst}([w \oplus x], [y \otimes z]) = [((w,y)\oplus(x,y)) \otimes ((w,z)\oplus(x,z))]$

and for the second:

$\mathsf{dst}'([w \oplus x], [y \otimes z]) = [((w,y)\otimes(w,z)) \oplus ((x,y)\otimes(x,z))]$

If this monad is commutative, we must have equality of equivalence classes:

$[((w,y)\oplus(x,y)) \otimes ((w,z)\oplus(x,z))] = [((w,y)\otimes(w,z)) \oplus ((x,y)\otimes(x,z))]$

We note that the provable equalities $t = t'$ in our theory must have the same number of occurrences of $\oplus$ and $\otimes$ on both sides. Therefore the two equivalence classes are distinct, and the monad is not commutative.

So we have seen that there is a monad that is not commutative, presented by an equational theory containing only commutative binary operations.

The previous two counterexamples reflect the fact that commutative binary operations should not have anything essential to do with monad commutativity. Monads presented by theories with just constants may or may not be commutative. Theories just involving just binary operations may or may not be commutative. Obviously there are other arities of operation to consider, but by this point hopefully it’s clear that there’s no tight relationship.

In fact, a monad being commutative does imply that certain equations must hold. In the case of binary operations, it is sufficient for the operation to be commutative to satisfy some of these equations. In simple cases, for example theories with a single binary operation, this might explain some of the misleading patterns that emerge.

We shall examine commutative monads from an algebraic perspective in a later post, and see exactly what it is that can be commuted that inspires the terminology.

Commutative Monads

We saw the two double strength natural transformations in the previous post:

$\mathsf{dst}, \mathsf{dst}' : \mathbb{T}(A) \otimes \mathbb{T}(B) \rightarrow \mathbb(T)(A \otimes B)$

A commutative monad is a strong monad for which $\mathsf{dst} = \mathsf{dst}'$ . We saw last time that the list monad is not commutative, but the powerset monad is. In this post we will restrict ourselves to examining some more instructive examples. This will help build our intuitions, and the examples lay the groundwork for discussions in later posts.

Example: For a set $E$ , there is a monad with:

Endofunctor: $(-) + E$ .
Unit: The unit maps an element into the left component of the coproduct $x \mapsto (1,x)$ .
Multiplication: The multiplication: $\mu_X : (X + E) + E \Rightarrow X + E$ does the “obvious thing”, $(1,(1,x)) \mapsto (1,x)$ , $(1,(2,e)) \mapsto (2,e)$ and $(2,e) \mapsto (2,e)$ .

The monad is sometimes referred to as the exception monad. Computationally, we can interpret a Kleisli morphism $X \rightarrow Y + E$ as a function that transforms elements of $X$ to elements of $Y$ , but may return error or exception values captured by $E$ . The first double strength for this monad is defined by the following cases:

$\mathsf{dst}((1,x), (1,y)) = (1, (x,y))$ .
$\mathsf{dst}((2,e),(1,y)) = (2,e)$ .
$\mathsf{dst}((1,x),(2,e)) = (2,e)$ .
$\mathsf{dst}((1,e_1),(1,e_2)) = (2,e_2)$ .

Notice that exception values are preferred, but there is rather arbitrary choice that has to be made in the fourth case. The second double strength agrees with the first, except for the final case, where it makes the other choice of exception to prefer:

$\mathsf{dst}'((1,e_1),(1,e_2)) = (2,e_1)$ .

So we see that the exception monad is only commutative if there’s exactly one exception. This special case is sometimes referred to as the maybe monad, as computationally it encodes functions that may fail.

Example: The multiset monad is commutative. To describe this, we shall introduce the notation

$\{ x_1 : k_1,\ldots, x_n : k_n \}$

for a multiset where element $x_i$ appears with multiplicity $k_i$ . The action of both double strength maps sends the pair of multisets:

$(\{ x_1 : k_1, \ldots, x_n : k_n \}, \{ y_1 : l_1,\ldots, y_m : l_m \})$

to the multiset:

$\{ (x_i , y_j) : k_i \times l_j \mid 1 \leq i \leq n, 1 \leq j \leq m \}$ .

The multiset monad is (isomorphic to) the Abelian monoid monad, so this monad is also commutative.

Example: Another monad that occurs commonly in practice is the finite probability monad on $\mathsf{Set}$ . This has:

Endofunctor: $\mathbb{D}(X)$ has elements finitely supported formal convex sums $\sum_i p_i x_i$ . These are weighted sum of elements of $X$ such that for each weight $p_i$ , $1 \leq p_i \leq 1$ , $\sum_i p_i = 1$ and only finitely many $p_i$ are non-zero. Alternatively, these can be thought of as functions $X \rightarrow [0,1]$ satisfying the previous conditions on the weights.
Unit: $\eta_X(x) = x$ . That is, the unit maps an element of $X$ to the corresponding trivial sum.
Multiplication: $\mu_X(\sum_i p_i (\sum_j q_{i,j} x_{i,j})) = \sum_i \sum_j (p_i \times q_{i,j}) x_{i,j}$ . This is simply flattening out a sum of sums.

This monad is commutative, with the action of both double strengths being:

$(\sum_i p_i x_i, \sum_j q_j y_j) \mapsto \sum_i \sum_j (p_i \times q_j) (x_i,y_j)$

For example:

$(\frac{1}{4}x + \frac{3}{4}x', \frac{1}{3} y + \frac{2}{3} y') \mapsto \frac{1}{12}(x,y) + \frac{1}{4}(x',y) + \frac{1}{6}(x,y') + \frac{1}{2}(x',y')$

In the next post we will explore a slightly misleading intuition that is commonly hinted at in the literature.