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')$