<figure><img src="image_1.png" /></figure>

HAL
open science

# Weakening and Iterating Laws using String Diagrams

Alexandre Goy

► To cite this version:

Alexandre Goy. Weakening and Iterating Laws using String Diagrams. MFPS XXXVIII, Jul 2022, Ithaca, NY, United States. 10.46298/entics.10482. hal-04085131

HAL Id: hal-04085131

https://hal.science/hal-04085131

Submitted on 28 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Weakening and Iterating Laws Using String Diagrams

Alexandre Goy<fnref n="1" />,<fnref n="2" />

LIP
ENS Lyon
France

## Abstract

Distributive laws are a standard way of combining two monads, providing a compositional approach for reasoning about computational effects in semantics. Situations where no such law exists can sometimes be handled by weakening the notion of distributive law, still recovering a composite monad. A celebrated result from Eugenia Cheng shows that combining *n* monads is possible by iterating more distributive laws, provided they satisfy a coherence condition called the Yang-Baxter equation. Moreover, the order of composition does not matter, leading to a form of associativity.

The main contribution of this paper is to generalise the associativity of iterated composition to weak distributive laws in the case of *n* = 3 monads. To this end, we use string-diagrammatic notation, which significantly helps make increasingly complex proofs more readable. We also provide examples of new weak distributive laws arising from iteration.

**Keywords:** monad, distributive law, weak distributive law, iterated distributive law, Yang-Baxter equation, string diagram

## 1 Introduction

Monads have been very successful in computer science to model computational effects [29,32,37]. In this context, being able to compose monads is of central importance. The primary framework for monad composition is undoubtedly Beck's celebrated theory of distributive laws [1]. In practice, finding distributive laws between monads is hard, although some recipes are known to build them [26,27]. In contrast, once a law is found, it often contains a significant semantic content – thus, it is common to find papers entirely dedicated to describing the construction and the consequences of a distributive law, see e.g. [21]. More generally, monad composition is still a very active field in the computer science community nowadays, with possible applications in coalgebra [34,22,40,5] or in the semantics of computation [14,30].

With the help of a distributive law, one can compose two monads. Composing more monads can be performed by *iterating* [11], *i.e.*, by using more distributive laws – yet, these must meet coherence axioms called the *Yang-Baxter equations*. While distributive laws are the first step towards monad compositionality, *iterated distributive laws* are all the following steps.

Although category theory is a language of choice to work on compositionality properties, there is one major obstacle in the field of distributive laws: monads may not always compose. And consequently,

<footnote n="1">¹ The author thanks Ana Sokolova and Daniela Petrişan for numerous discussions and support, Ralph Sarkis for bringing up the topic of string diagrams, and the anonymous reviewers for their helpful comments and suggestions. This work has been supported by the French project ANR-20-CE48-0005 QuaReMe.</footnote>

<footnote n="2">² Email: alexandre.goy@pm.me</footnote>
distributive laws may not always exist. The literature exhibits many such negative results, called *no-go theorems* [36,25,13,41,33,42]. A possible fix consists in *weakening* the notion of distributive law to recover transformations that, even if not satisfying all the usual axioms, still enable some weak kind of monad composition. This simple idea has received substantial coverage in the computer science community since the paper of Garner [15]. Simplifying earlier work from [35,9,10], Garner proposed to delete the one axiom that was obstructing, in many concrete cases, the existence of a law. Several papers followed on this revived notion of *weak distributive law* [17,18,4,31]. In general, finding examples of weak distributive laws remains difficult, and very few techniques are known to produce them. Moreover, for such a law to be relevant, it needs to fit into the sweet spot where no distributive law can exist, but there is still enough structure for a weak one. This situation arises in a handful of known cases, *e.g.*, when distributing the distribution monad over the powerset monad [17] or the powerset monad over itself [15,18].

Iterating weak distributive laws is a promising target: one would enable building new weak distributive laws out of some existing ones at low cost. However, two factors are now interacting with the basic theory of Beck. The proof of the iteration theorem [11, Appendix A], due to Eugenia Cheng, is not very difficult per se, but, already for the simplest case of three monads, it contains large commutative diagrams that are hard to comprehend in one glimpse. On the other hand, although weak distributive laws are conceptually close to distributive laws, they make the framework grow in complexity. Manipulating weak laws involves manipulating more natural transformations arising from splitting of idempotents, making proofs less transparent. In short, *iterating* adds one layer of complexity, *weakening* adds another layer, and computations become untractable using the traditional tools of category theory. For a similar situation, consider the paper of Winter [38] whose main result is to prove a variation of Cheng's theorem in the case of three monads. In a nutshell, the variation consists in modifying the type of *one* of the laws from $TF \Rightarrow FT$ into $TF \Rightarrow FST$ – with, of course, consequences for the coherence conditions. Despite this seemingly mild modification, one of the required commutative diagrams becomes so large that finding the appropriate tiling required Winter to use automation via a Prolog program, mainly because of the explosion in the number of naturality squares. As he insists on, the main difficulty is about finding the proof – verifying it remains straightforward.

In the present paper, we aim to illustrate yet another case where *string diagrams* bring conceptual clarity and simplicity. Under the name string diagrams, there are many graphical calculi based on topological operations such as string bending, dragging, and sliding. Such frameworks have raised more and more interest over the past years: we can mention, *e.g.*, the book of Coecke and Kissinger [12] and the line of work of Bonchi, Zanasi *et al.* [39,8,7,6,3,2]. String diagrams are nowadays recognised as a helpful tool. Inside published papers, commutative diagrams have long been preferred, even when they are less enlighting (see *e.g.* [35, Propositions 2.3, 3.3, and 4.1]). One of the aims of this paper is to emphasise the following point: when it comes to concepts that rely on several complexity layers, such as *iterating* plus *weakening*, string diagrams may even be *required* as a computation-assisting technology. The string diagrams we will make use of are those introduced in the style of Hinze and Marsden [28,20,19]. These were already used to produce new results within the theory of distributive laws by Zwart [41] and in the author's PhD thesis [16]. There seems to be also some work in progress concerning no-go theorems [24], showing that string diagrams are imposing themselves in the area to visualise categorical transformations, provide elegant proofs, and communicate ideas.

## Contributions.

This paper contains contributions of two kinds: technical (laws) and practical (strings). On the practical side, the paper introduces in Section 3 a convenient string-diagrammatic notation that helps manipulate concepts at play. In particular, we introduce a new notation for idempotents of the form $κ: ST \Rightarrow ST$ in equation (12), which is central in the whole development. The main technical contribution of the paper consists in generalising Cheng's Theorem 4.1 to weak distributive laws in the case of $n = 3$ monads. For clarity, this result is split into three distinct statements: Theorem 4.3, Theorem 4.5, and Theorem 4.6. Along the way, and building on a key technical tool which is Lemma 3.10, we derive several results of the theory of weak distributive laws, some of them already presented in [16], some of them unpublished. In Section 4.2, we also provide four families of examples where our main result applies:
trivial weak distributive laws, and generic distributive laws involving the exception monad, the reader monad, and the writer monad. Finally, in Section 4.3, we give a new perspective on algebras for a monad by identifying them as distributive laws (Proposition 4.16). In this vision, algebras for a distributive law are identified as iterated distributive laws (Proposition 4.17).

## Related Work.

The content of the present paper is partly based on the author's PhD thesis [16], with a slightly different perspective. In [16] the focus is put on the correspondence weak distributive laws - weak liftings - weak extensions. In contrast, in the present paper, we instead follow the approach of [35, Section 2] consisting in building the weak composite monad directly out of the weak distributive law. It has to be mentioned that iterated distributive laws have already been studied from a string-diagrammatic perspective in a paper from Hinze and Marsden [19].

# 2 Background

## 2.1 Preliminaries and Notation

Definitional equality is denoted by $\triangleq$. We assume basic knowledge of category theory, including: category, functor, natural transformation. Let $\mathcal{C}$ be a category and $S, T$ be endofunctors on $\mathcal{C}$. We use the Lie bracket notation $[S, T]$ as a shortcut for the type of natural transformations $TS \Rightarrow ST$. For example, $\lambda: [S, T]$ means that $\lambda$ is a natural transformation of type $TS \Rightarrow ST$. This notation is convenient because (a) laws $\lambda: [S, T]$ are related to composite monads $S \circ T$ and (b) the type $TS \Rightarrow ST$ looks like a logical version of the formal expression $-TS + ST$. Identity morphisms will be denoted by $1_X: X \to X$, the identity functor by $1: \mathcal{C} \to \mathcal{C}$, and the identity natural transformation on a functor $F$ by $1_F: F \Rightarrow F$.

In the whole paper we assume that $\mathcal{C}$ is idempotent complete, that is, for every morphism $k: X \to X$ in $\mathcal{C}$ such that $k \circ k = k$, there are morphisms $p: X \to Y$ and $i: Y \to X$ such that $i \circ p = k$ and $p \circ i = 1_Y$. A direct consequence is that for any functor $F: \mathcal{C} \to \mathcal{C}$, every idempotent natural transformation $\kappa: F \Rightarrow F$ splits. Explicitly, there are a functor $K$ and natural transformations $\pi: F \Rightarrow K$, $\iota: K \Rightarrow F$ such that $\iota \circ \pi = \kappa$ and $\pi \circ \iota = 1_K$. All the foregoing examples live in the category Set of sets and functions, which is idempotent complete. So are, e.g., toposes and the category of compact Hausdorff spaces [18]. We globally impose idempotent completeness to be able to split natural transformations denoted by $\kappa$ in the sequel – all our results remain valid by only asserting locally that these $\kappa$ split.

## 2.2 Introducing String Diagrams

We strongly encourage the reader to refer to [20, Sections 2 and 3] for a thorough introduction to string diagrams. In this short section, we will nonetheless provide a crash course in string diagrams, mainly to fix notations.

The following example sums up all useful notation. On the left part, we provide several basic natural transformations $\lambda: TS \Rightarrow ST$, $\nu: ST \Rightarrow U$, $\varepsilon: U \Rightarrow 1$, $\eta: 1 \Rightarrow T$. On the right part, we provide two equivalent string diagrams representing the same composite natural transformation $\nu \circ \lambda \varepsilon \circ \eta SU = \nu \circ \lambda \circ \eta S \circ S \varepsilon: SU \Rightarrow U$.

<figure><img src="image_3.png" /></figure>

We use the following convention: diagrams are read from right to left and from bottom to top (note that [20] rather uses top to bottom). A functor $F: \mathcal{C} \to \mathcal{D}$, represented by a vertical string, delineates two regions: the region on the right represents the category $\mathcal{C}$, while the region on the left represents
the category $\mathcal{D}$. In what follows, we only study endofunctors in $C^3$. Therefore all delineated regions remain blank and represent the category $C$. The identity functor $1: C \to C$ is not depicted. A natural transformation $\alpha: F \Rightarrow G$ is depicted by a symbol between functor $F$ (below) and functor $G$ (above). Using colours, we will define on-the-fly unambiguous symbols (typically, nodes) to distinguish between different natural transformations – see equation (1) for a first example. The identity natural transformation $1_F: F \Rightarrow F$ is a string with no symbol, i.e., it coincides with the representation of the functor $F: C \to C$.

Let $F, G, H, K$ be functors, and $\alpha: F \Rightarrow G, \beta: G \Rightarrow H, \gamma: H \Rightarrow K$ be natural transformations. Composition of functors is denoted by $GF$ and depicted by horizontal juxtaposition of strings. Vertical composition of natural transformations is denoted by $\beta \circ \alpha: F \Rightarrow H$, defined by $(\beta \circ \alpha)_X \triangleq \beta_X \circ \alpha_X$ for all objects $X$, and depicted by vertical glueing of string diagrams. Left (respectively right) composition of a functor and a natural transformation is denoted by $H\alpha: HF \Rightarrow HG$ (respectively $\alpha H: FH \Rightarrow GH$), defined by $(H\alpha)_X \triangleq H(\alpha_X)$ (respectively $(\alpha H)_X \triangleq \alpha_{HX}$) for all objects $X$, and depicted by horizontal juxtaposition of string diagrams. Horizontal composition of natural transformations is denoted by $\gamma\alpha: HF \Rightarrow KG$, defined by $\gamma\alpha \triangleq K\alpha \circ \gamma F = \gamma G \circ H\alpha$, and depicted by horizontal juxtaposition of string diagrams.

Each string diagram represents a natural transformation of some type. Two string diagrams of the same type are identified up to continuous operations such as dragging nodes and bending strings (provided it does not reverse the implicit bottom-up vertical direction). Discontinuous operations include sliding a node past another on the same string, crossing two strings, and deleting or adding strings or nodes. Such operations may be allowed punctually in the presence of a natural transformation that justifies them. For instance, a natural transformation $\lambda: [S, T]$, having type $TS \Rightarrow ST$, represents an *ad hoc* rule to cross the two strings representing $S$ and $T$. String-diagrammatic notation is coherent with the usual laws of category theory in the sense that two identified string diagrams always denote the same natural transformation.

It is customary, as done in [20], to specify the types of the functors below and above each string diagram. In this paper, only a few functors are in play, so that our colour code would be sufficient to infer all types. For the sake of clarity, we opt for some redundancy by always indicating types.

# 3 A String-Diagrammatic Theory of Weak Distributive Laws

The present section introduces weak distributive laws in string-diagrammatic style, starting back from the standard theory of monads and distributive laws.

## 3.1 Monads and Distributive Laws

**Definition 3.1** A *monad* is a triple $(T, \eta^T, \mu^T)$ comprising a *C*-endofunctor $T$ and two natural transformations, the *unit* $\eta^T: 1 \Rightarrow T$ and the *multiplication* $\mu^T: TT \Rightarrow T$, such that $\mu^T \circ \eta^T T = 1_T = \mu^T \circ T\eta^T$ (unitality) and $\mu^T \circ \mu^T T = \mu^T \circ T\mu^T$ (associativity).

String diagrammatically, these data are denoted by

<figure><img src="image_4.png" /></figure>

For the sake of readability, we may denote a monad $(T, \eta^T, \mu^T)$ simply by $T$. Let us give some examples of monads in the category Set.

<footnote n="3">³ To be precise, we are using the standard formalism of string diagrams for monoidal categories [23] within the category of *C*-endofunctors, where monoidal product is given by functor composition.</footnote>
**Example 3.2** The identity monad consists of the identity functor 1 with both the unit and the multiplication being the identity natural transformation $1 \Rightarrow 1$.

**Example 3.3** The exception monad E is defined as follows. Let $1 = \{*\}$ be a singleton set. For any set $X$, let $\text{inl}_X: X \to X+1$ and $\text{inr}_X: 1 \to X+1$ be the canonical injections. The functor E maps a set $X$ to the set $EX \triangleq X+1$ and a function $f: X \to Y$ to $Ef: X+1 \to Y+1$, defined by $Ef(\text{inl}_X(x)) \triangleq \text{inl}_Y(f(x))$ and $Ef(\text{inr}_X(*)) \triangleq \text{inr}_Y(*).$ The unit is $\eta^E \triangleq \text{inl}: 1 \Rightarrow E$ and the multiplication $\mu^E: EE \Rightarrow E$ is given by merging exceptions, i.e., $\mu_X^E(\text{inl}_{X+1}(z)) \triangleq z$ for all $z \in X+1$ and $\mu_X^E(\text{inr}_{X+1}(*)) \triangleq \text{inr}_X(*).$

**Example 3.4** The reader monad R is defined as follows. Let A be a set of labels. The functor R maps a set X to the set $RX \triangleq X^A$ and a function $f: X \to Y$ to $Rf: X^A \to Y^A$, defined by $Rf(h) \triangleq f \circ h$ for all $h \in X^A$. The unit $\eta^R: 1 \Rightarrow R$ produces a constant function $\eta_X^R(x) \triangleq (a \mapsto x)$. The multiplication $\mu^R: RR \Rightarrow R$ duplicates the input, i.e., $\mu_X^R(h) \triangleq (a \mapsto h(a)(a))$ for all $h \in (X^A)^A$.

**Example 3.5** The writer monad W is defined as follows. Let $(M, \cdot, e)$ be a monoid. The functor W maps a set X to the set $WX \triangleq M \times X$ and a function $f: X \to Y$ to $Wf: M \times X \to M \times Y$, defined by $Wf(m, x) \triangleq (m, f(x))$. The unit $\eta^W: 1 \Rightarrow W$ outputs the monoid unit $\eta_X^W(x) \triangleq (e, x)$. The multiplication $\mu^W: WW \Rightarrow W$ implements the monoid multiplication, i.e., $\mu_X^W(m, (n, x)) \triangleq (m \cdot n, x)$.

**Example 3.6** The powerset monad P is defined as follows. The functor P maps a set X to the set of its subsets $PX$ and a function $f: X \to Y$ to its direct image $Pf: PX \to PY$, defined by $Pf(U) \triangleq \{f(x) \mid x \in U\}$ for all $U \subseteq X$. The unit $\eta^P: 1 \Rightarrow P$ produces singletons $\eta_X^P(x) \triangleq \{x\}$. The multiplication $\mu^P: PP \Rightarrow P$ computes unions, i.e., $\mu_X^P(\mathcal{U}) \triangleq \bigcup \mathcal{U}$ for all $\mathcal{U} \in PPX$.

**Example 3.7** The distribution monad D is defined as follows. The functor D maps a set X to the set of all finitely-supported probability distributions on X, i.e.,

$$DX \triangleq \left\{ p: X \to [0,1] \mid \sum_{x \in X} p(x) = 1, \text{supp}_X(p) \text{ is finite} \right\} \qquad (3)$$

where $\text{supp}_X(p) = \{x \in X \mid p(x) > 0\}$. For a $p \in DX$, we may use the formal sum notation $p = \sum_{x \in X} p_x \cdot x$, where $p_x \triangleq p(x)$. A function $f: X \to Y$ is mapped to $Df: DX \to DY$, defined by $Df(\sum_{x \in X} p_x \cdot x) \triangleq \sum_{x \in X} p_x \cdot f(x)$. The unit $\eta^D: 1 \Rightarrow D$ produces Dirac distributions $\eta_X^D(x) \triangleq 1 \cdot x$. The multiplication $\mu^D: DD \Rightarrow D$ is a weighted average, defined by $\mu_X^D(q) \triangleq \sum_{p \in DX} q_p p_x \cdot x$ for all $q \in DDX$.

**Definition 3.8** Given two monads $S$, $T$ on $\mathcal{C}$, a distributive law is a $\lambda: [S, T]$ such that the four following axioms hold:

$$\lambda \circ T \eta^S = \eta^S T \qquad (\eta^+)$$

$$\lambda \circ T \mu^S = \mu^S T \circ S \lambda \circ \lambda S \qquad (\mu^+)$$

$$\lambda \circ \eta^T S = S \eta^T \qquad (\eta^-)$$

$$\lambda \circ \mu^T S = S \mu^T \circ \lambda T \circ T \lambda \qquad (\mu^-)$$

String diagrammatically, the monads $S$, $T$, and the distributive law $\lambda: [S, T]$ are pictured as

<figure><img src="image_5.png" /></figure>
and the distributive law axioms are

<figure><img src="image_6.png" /></figure>

Any distributive law $\lambda$: $[S, T]$ yields a monad $S \circ_{\lambda} T \triangleq (ST, \eta^S \eta^T, \mu^S \mu^T \circ S\lambda T)$, also denoted by $S \circ T$ when no confusion can arise, and pictured as

<figure><img src="image_7.png" /></figure>

## 3.2 Weak Distributive Laws

**Definition 3.9** Given two monads $S$, $T$ on $\mathcal{C}$, a weak distributive law is a $\lambda$: $[S, T]$ such that the axioms $(\eta^+)$, $(\mu^+)$ and $(\mu^-)$ hold.

In this definition, the weakening comes from dropping the $(\eta^-)$ axiom, as done in [15]. There are other possible weakenings that we briefly discuss in Remark 3.15. An interesting natural transformation emerges from the structure of a weak distributive law. Consider

$$ \kappa \triangleq ST \underset{ST}{\overset{\eta^T ST}{\rightleftharpoons}} TST \underset{ST}{\overset{\lambda T}{\rightleftharpoons}} STT \underset{ST}{\overset{S\mu^T}{\rightleftharpoons}} ST \quad (7) $$

If $\lambda$ were a distributive law, then $\kappa$ would be the identity. In the weak case though, $\kappa$ still is an idempotent that is compatible with units and multiplications in the following sense.

**Lemma 3.10** The natural transformation $\kappa$ satisfies the following equations.

$$ \kappa \circ \kappa = \kappa \quad (8) $$

$$ \kappa \circ \lambda = \lambda \quad (9) $$

$$ \kappa \circ \eta^S \eta^T = \eta^S \eta^T \quad (10) $$

$$ \kappa \circ \mu^S \mu^T \circ S\lambda T = \mu^S \mu^T \circ S\lambda T \circ \kappa\kappa \quad (11) $$

As $\kappa: ST \Rightarrow ST$ is an idempotent natural transformation and we assume $\mathcal{C}$ to be idempotent complete, there are a $\mathcal{C}$-endofunctor $K$ and two natural transformations $\pi: ST \Rightarrow K$ and $\iota: K \Rightarrow ST$ such that $\iota \circ \pi = \kappa$ and $\pi \circ \iota = 1_K$. Using these, one can build a monad that is to be interpreted as a weak composition of $S$ and $T$, namely $S \circledast_{\lambda} T = (K, \pi \circ \eta^S \eta^T, \pi \circ \mu^S \mu^T \circ S\lambda T \circ \iota)$, also denoted by $S \circledast T$ when the context is clear. See Appendix A for a proof that this is indeed a monad. We now introduce some string diagrammatic notation that will make computations practicable:

<figure><img src="image_8.png" /></figure>
• The map $\text{proj}^2: W \Rightarrow 1$ from the writer monad, defined by $\text{proj}_X^2(m, x) \triangleq x$ for any $(m, x) \in W X$, is a monad morphism. Therefore $\eta^W \circ \text{proj}^2: [W, 1]$, defined by $(m, x) \mapsto (e, x)$, is a weak distributive law.

• Given any letter $a \in A$, the map $\hat{a}: R \Rightarrow 1$ from the reader monad, defined by $\hat{a}_X(h) \triangleq h(a)$ for any $h \in RX$, is a monad morphism. Therefore $\eta^R \circ \hat{a}: [R, 1]$, defined by $h \mapsto (b \mapsto h(a))$, is a weak distributive law.

We provide two non-trivial examples of weak distributive laws, both of them arising from situations when no distributive law of their type exists [25,36].

**Example 3.13** The natural transformation $\lambda: [P, D]$ defined for any distribution of subsets $p = \sum_i p_i \cdot U_i$ by

$$ \lambda_X(p) = \left\{ \sum_i p_i q^i \mid q^i \in DX, \text{supp}(q^i) \subseteq U_i \right\} \qquad (16) $$

is the unique monotone weak distributive law of its type – see [17] for a detailed study.

**Example 3.14** The natural transformation $\lambda: [P, P]$ defined for any subset of subsets $\mathcal{U}$ by

$$ \lambda_X(\mathcal{U}) = \{V \subseteq \bigcup \mathcal{U} \mid \forall U \in \mathcal{U}, V \cap U \neq \emptyset\} \qquad (17) $$

is the unique monotone weak distributive law of its type – see [15,18] for more details.

One can see that the theory of weak distributive laws is very similar to Beck's theory of distributive laws [1] modulo the transformations $\pi$ and $\iota$. For example, if $\lambda: [S, T]$ is a distributive law, then the classical theory shows that $S\eta^T: S \Rightarrow S \circ_\lambda T$ and $\eta^S T: T \Rightarrow S \circ_\lambda T$ are monad morphisms. Similarly, if $\lambda: [S, T]$ is only weak, then $\pi \circ S\eta^T: S \Rightarrow S \circ_\lambda T$ and $\pi \circ \eta^S T: T \Rightarrow S \circ_\lambda T$ are monad morphisms. Whenever the base category is idempotent complete, as is assumed in this paper, the renowned correspondence distributive laws - extensions - liftings also generalises (see [15]).

**Remark 3.15** Deleting the $(\eta^-)$ axiom is one of the many ways of weakening the notion of distributive law. In recent years, this approach has been very fruitful for computer science applications [17,18,16,4]. One may ask, symmetrically, what happens by deleting the $(\eta^+)$ axiom instead. This idea gives rise to the notion of coweak distributive law developed by the author in [16]. Coweak distributive laws enjoy many symmetries with respect to weak distributive laws, but no non-trivial examples of them are known. Yet another way of weakening the notion of distributive law is the one of Street [35], who suggests keeping a weakened version of both the $(\eta^+)$ and the $(\eta^-)$ axiom. The presentation of the present paper – including the string diagrammatic approach – is greatly inspired by the one of Street-weak distributive laws in [35]. A broader, 2-categorical account of distributive law weakenings can be found in [9,10].

# 4 Iterating Laws

## 4.1 Adapting Cheng's Theorem

In this section, we are interested in what happens when combining more laws. For the sake of simplicity, we will only consider the case when three laws are in play. In the whole section, let $R$, $S$, $T$ be monads

<figure><img src="image_9.png" /></figure>

and $\lambda: [S, T]$, $\sigma: [R, S]$, $\tau: [R, T]$ be natural transformations such that the following equation holds.

$$ \sigma T \circ S \tau \circ \lambda R = R \lambda \circ \tau S \circ T \sigma \qquad (\text{YB}) $$
Equation (YB), known as the *Yang-Baxter equation*, intuitively states that these three natural transformations are coherent with each other. Diagrammatically, it means that when performing the three crossings in a row, their order does not matter:

$$ \lambda \triangleq \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$S$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$T$}; 
\node[below] at (RTBR) {$S$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} 
\qquad 
\sigma \triangleq \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$R$}; 
\node[above] at (R) {$S$}; 
\node[below] at (TBL) {$S$}; 
\node[below] at (RTBR) {$R$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} 
\qquad 
\tau \triangleq \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$R$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$T$}; 
\node[below] at (RTBR) {$R$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} 
= \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$RS$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$TS$}; 
\node[below] at (RTBR) {$R$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\end{tikzpicture} 
$$ (19)

Yang-Baxter

The result of Cheng [11, Theorem 1.6] can be rephrased as follows in the case of three monads.

**Theorem 4.1 (Cheng)** Let $R, S, T$ be monads and $\lambda: [S, T], \sigma: [R, S], \tau: [R, T]$ be distributive laws satisfying the *Yang-Baxter equation*. Then

* $R\lambda \circ \tau S: [R \circ S, T]$ is a distributive law,

* $\sigma T \circ S\tau: [R, S \circ T]$ is a distributive law,

* these two laws generate the same monad, i.e., $(R \circ S) \circ T = R \circ (S \circ T)$.

The result can be generalised to weak distributive laws. Let us consider separately what happens for the two possible composite laws. From now onwards, the natural transformations $\kappa, \pi$ and $\iota$ from Section 3 will mention explicitly which law they relate to – e.g., given a weak distributive law $\lambda: [S, T]$, they are denoted by $\kappa^\lambda, \pi^\lambda$ and $\iota^\lambda$.

### 4.1.1 First Composite Law

Assume $\sigma: [R, S]$ is a weak distributive law. We will derive which axioms on $\lambda$ and $\tau$ are sufficient for

$$ \varphi \triangleq T(R \bullet S) \underset{T \iota \sigma}{\overset{T \iota}{\longrightarrow}} TRS \underset{\tau S}{\overset{\tau S}{\longrightarrow}} RTS \underset{R \lambda}{\overset{R \lambda}{\longrightarrow}} RST \underset{\pi^\sigma T}{\overset{\pi^\sigma T}{\longrightarrow}} (R \bullet S)T \quad (20) $$

to be a (weak) distributive law. The natural $\varphi: [R \bullet S, T]$ can be depicted as follows, where $H$ is short notation for the functor $R \bullet S$:

$$ \varphi \triangleq \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$H$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$T$}; 
\node[below] at (RTBR) {$H$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} \quad (21) $$

The $(\eta^+)$ axiom for $\varphi$ can be derived from equation (10) which states compatibility between units and the idempotent, the $(\eta^+)$ axiom for $\tau$, and the $(\eta^+)$ axiom for $\lambda$:

$$ \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$H$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$T$}; 
\node[below] at (RTBR) {$H$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} 
\quad (22) $$

The $(\eta^-)$ axiom for $\varphi$ can be derived from the $(\eta^-)$ axiom for $\tau$, the $(\eta^-)$ axiom for $\lambda$, and the retract equation $\pi \circ \iota = 1_{R \bullet S}$:

$$ \begin{tikzpicture}[baseline=(current bounding box.center), scale=0.35, every node/.style={scale=0.8}] 
% Coordinates for vertices

% Top-left vertex
\coordinate (T) at (0,1); 
% Top-right vertex
\coordinate (R) at (1,1); 
% Bottom-left vertex
\coordinate (TBL) at (0,0); 
% Bottom-right vertex
\coordinate (RTBR) at (1,0); 

% Edges
\draw[thick, ->] (T) -- (R); 
\draw[thick, ->] (TBL) -- (RTBR); 
\draw[thick, ->] (R) -- (TBL); 
\draw[thick, ->] (RTBR) -- (TBR); 

% Labels
\node[above] at (T) {$H$}; 
\node[above] at (R) {$T$}; 
\node[below] at (TBL) {$T$}; 
\node[below] at (RTBR) {$H$}; 

% Arrows
\draw[thick, ->] (0.5,0.5) -- (0.5,-0.5); 
\draw[thick, ->] (0.5,0.5) -- (-0.5,0.5); 
\draw[thick, ->] (0.5,0.5) -- (0.5,1); 
\draw[thick, ->] (0.5,0.5) -- (0.5,0); 
\end{tikzpicture} 
\quad (23) $$

The $(\mu^+)$ axiom for $\varphi$ can be derived from equation (11) which states compatibility between multiplications and the idempotent, the retract equation $\pi \circ \iota = 1_{R \bullet S}$, the $(\mu^+)$ axiom for both $\tau$ and $\lambda$, the Yang-Baxter
equation, the retract equation again, and equation (11) again:

<figure><img src="image_10.png" /></figure>

To prove the last axiom, we need a technical lemma.

**Lemma 4.2** If $\lambda$'s axioms $(\eta^+)$ and $(\mu^+)$ hold, and the Yang-Baxter equation holds, then the idempotent $\kappa^\sigma$ commutes with the natural $R\lambda \circ \tau S$ in the sense that

$$ \kappa^\sigma T \circ R\lambda \circ \tau S = R\lambda \circ \tau S \circ T\kappa^\sigma \quad (25) $$

**Proof.** Easy to see using string diagrams:

<figure><img src="image_11.png" /></figure>

The $(\mu^-)$ axiom for $\varphi$ can then be derived from the retract equation $\pi \circ \iota = 1_{R\bullet S}$, the $(\mu^-)$ axiom for both $\tau$ and $\lambda$, and the lemma relying on $\lambda$'s axioms $(\eta^+)$ and $(\mu^+)$. □

<figure><img src="image_12.png" /></figure>

Table 2 sums up which axioms of $\tau$ and $\lambda$ are sufficient to make axioms hold for $\varphi$.

<table><caption>Table 2
Required axioms for the composite law $\varphi$</caption><thead><tr><th>φ</th><th>requires</th><th>τ</th><th>λ</th></tr></thead><tbody><tr><td>(η<sup>+</sup>)</td><td></td><td>(η<sup>+</sup>)</td><td>(η<sup>+</sup>)</td></tr><tr><td>(η<sup>-</sup>)</td><td></td><td>(η<sup>-</sup>)</td><td>(η<sup>-</sup>)</td></tr><tr><td>(μ<sup>+</sup>)</td><td></td><td>(μ<sup>+</sup>)</td><td>(μ<sup>+</sup>)</td></tr><tr><td>(μ<sup>-</sup>)</td><td></td><td>(μ<sup>-</sup>)</td><td>(μ<sup>-</sup>), (η<sup>+</sup>), (μ<sup>+</sup>)</td></tr></tbody></table>

Using the information contained in Table 2, we get the following result.

**Theorem 4.3** Let $R, S, T$ be monads and $\lambda: [S, T]$, $\sigma: [R, S]$, $\tau: [R, T]$ be weak distributive laws satisfying the Yang-Baxter equation. Then the composite $\varphi \triangleq \pi^\sigma T \circ R\lambda \circ \tau S \circ T\iota^\sigma: [R \bullet S, T]$ is a weak distributive law. If, additionally, $\tau$ and $\lambda$ are distributive laws, then $\varphi$ is a distributive law.
idempotent, as shown in the following diagrams (proved in Appendix B):

<figure><img src="image_13.png" /></figure>

Using these compatibility properties along with aforementioned properties of $κ$, it is then a matter of lengthy but straightforward computations to show that units and multiplications of $(R \bullet S) \bullet T$ and $R \bullet (S \bullet T)$ coincide (see Appendix B). □

## 4.2 Examples

In this section, we illustrate many cases where the results of the previous section can be applied by proving the Yang-Baxter equation for some usual monads and (weak) distributive laws.

### 4.2.1 Iterating with Trivial Weak Distributive Laws

When one of the three laws involved is trivial, the Yang-Baxter equation usually simplifies to a condition relating the underlying monad morphism to the other laws. We mention the two following cases.

**Proposition 4.7** Let $\tau: [R, T]$ be a weak distributive law.

* Let $\sigma: [R, S]$ be a distributive law and $\lambda \triangleq \eta^S \mu^T \circ T\gamma: [S, T]$ be a trivial weak distributive law arising from a monad morphism $\gamma: S \Rightarrow T$ such that $R\gamma \circ \sigma = \tau \circ \gamma R$. Then the Yang-Baxter equation is satisfied.

* Let $\lambda: [S, T]$ be a weak distributive law and $\sigma \triangleq \eta^R \mu^S \circ S\gamma: [R, S]$ be a trivial weak distributive law arising from a monad morphism $\gamma: R \Rightarrow S$ such that $\gamma T \circ \tau = \lambda \circ \gamma T$. Then the Yang-Baxter equation is satisfied.

### 4.2.2 Iterating with Exceptions

The exception monad $E$ from Example 3.3 can be described by seeing $\text{inl}: 1 \Rightarrow E$ and $\text{inr}: \underline{1} \Rightarrow E$ as natural transformations, where 1 is the identity functor and $\underline{1}$ is the constant functor $\underline{1}X \triangleq 1 = \{*\}$, $\underline{1}f \triangleq 1_{\{*\}}$. One can then define a well-known generic distributive law relying directly on these two coproduct injections.

**Example 4.8** For any Set monad $T$, there is a distributive law $\varepsilon^T: [T, E]$ defined by

$$ \varepsilon^T \circ \text{inl}T = T\eta^E \qquad (40) $$

$$ \varepsilon^T \circ \text{inr}T = \eta^T E \circ \text{inr} \qquad (41) $$

Moreover, for monads $S$ and $T$, the distributive laws $\varepsilon^S$ and $\varepsilon^T$ are coherent with each other in the sense of the next proposition.

**Proposition 4.9** Let $\lambda: [S, T]$ be a natural transformation such that either the $(\eta^+)$ or the $(\eta^-)$ axiom holds. Then the following Yang-Baxter equation holds:

$$ \lambda E \circ T \varepsilon^S \circ \varepsilon^T S = S \varepsilon^T \circ \varepsilon^S T \circ E \lambda \qquad (42) $$

**Remark 4.10** The above proposition still holds true when $E$ implements multiple exceptions. More generally, it can be generalised to any category with binary coproducts and any exception monad of the form $EX = X + e$, where $e$ is an object of exceptions.

Consequently, by applying Theorem 4.6, given any weak distributive law $[S, T]$, one can safely compose the resulting monad with the exception monad $E$ and get a monad $S \bullet T \circ E$. We give two explicit examples.
* Applying Theorem 4.5 to the weak distributive law $\lambda: [P, D]$ from Example 3.13, we derive a new weak distributive law $\lambda E \circ D \varepsilon^P: [P, D_\le]$ between the powerset monad $P$ and the subdistribution monad $D_\le = D \circ E$. The expression of this new law is as in (16).

* Remarking that $P = P_* \circ E$ where $P_*$ is the non-empty powerset monad, we identify the weak distributive law $\lambda: [P, P]$ from Example 3.14 as an iterated law built from $\varepsilon^P$, $\varepsilon^{P_*}$, and a weak distributive law of type $[P, P_*$] whose expression is as in (17).

### 4.2.3 Iterating with the Reader

Recall that $A$ is a set of labels and the reader monad in Set is defined as $RX = X^A$. For any $a \in A$, define the function $\hat{a}_X: RX \to X$ by $\hat{a}_X(h) = h(a)$.

**Example 4.11** For any Set monad $T$, there is a distributive law $\rho^T: [R, T]$ defined for any set $X$ and any $z \in TRX$ by

$$ \rho_X^T(z) \triangleq a \mapsto T\hat{a}_X(z) \qquad (43) $$

Moreover, for monads $S$ and $T$, the distributive laws $\rho^S$ and $\rho^T$ are coherent with each other in the sense of the next proposition.

**Proposition 4.12** Let $\lambda: [S, T]$ be a natural transformation. Then the following Yang-Baxter equation holds:

$$ \rho^S T \circ S \rho^T \circ \lambda R = R\lambda \circ \rho^T S \circ T \rho^S \qquad (44) $$

Applying Theorem 4.6 with e.g. the weak $\lambda: [P, D]$ from Example 3.13, we deduce that the monad $R \circ P \circ D$ can be obtained either using the distributive law $\psi = \rho^{P \circ D}: [R, P \circ D]$ or using the weak distributive law $\varphi \triangleq R\lambda \circ \rho^D P: [R \circ P, D]$ given by the expression

$$ \varphi_X \left( \sum_{h \in (PX)^A} p_h \cdot h \right) = a \mapsto \left\{ \sum_{h \in (PX)^A} p_h q^h \mid q^h \in DX, \text{supp}(q^h) \subseteq h(a) \right\} \qquad (45) $$

### 4.2.4 Iterating with the Writer

Recall that $M$ is a monoid and the writer monad in Set is defined as $MX = M \times X$. For any $m \in M$, let $\overline{m}_X: X \to M \times X$ be defined by $\overline{m}_X(x) = (m, x)$.

**Example 4.13** For any Set monad $T$, there is a distributive law $\omega^T: [T, W]$ defined for any set $X$ and any $(m, t) \in WTX$ by

$$ \omega_X^T(m, t) \triangleq T\overline{m}_X(t) \qquad (46) $$

Moreover, for monads $S$ and $T$, the distributive laws $\omega^S$ and $\omega^T$ are coherent with each other in the sense of the next proposition.

**Proposition 4.14** Let $\lambda: [S, T]$ be a natural transformation. Then the following Yang-Baxter equation holds:

$$ \lambda W \circ T\omega^S \circ \omega^T S = S\omega^T \circ \omega^S T \circ W\lambda \qquad (47) $$

Applying Theorem 4.6 with e.g. the weak $\lambda: [P, D]$ from Example 3.13, we deduce that the monad $P \circ D \circ W$ can be obtained either using the distributive law $\varphi = \omega^{P \circ D}: [P \circ D, W]$ or using the weak distributive law $\psi \triangleq \lambda W \circ T\omega^S: [P, D \circ W]$ given by the expression

$$ \psi_X \left( \sum_{i,j} p_{i,j} \cdot (m_i, U_j) \right) = \left\{ \sum_{i,j} p_{i,j} q^{i,j} \mid q^{i,j} \in DWX, \text{supp}(q^{i,j}) \subseteq \{(m_i, x) \mid x \in U_j\} \right\} \qquad (48) $$
## 4.3 Algebras as Distributive Laws, and Iterating them

In this short section we sketch how Eilenberg-Moore algebras are a particular kind of distributive laws, and how in this view $\lambda$-algebras are precisely Yang-Baxter equations. Given a monad $T$, an Eilenberg-Moore algebra – or $T$-algebra for short – is a pair $(A, t)$ where $A$ is an object of $C$ and $t: TA \to A$ is a morphism such that $t \circ \eta_A^T = 1_A$ (unitality) and $t \circ \mu_A^T = t \circ Tt$ (associativity). A morphism of $T$-algebras $f: (A, t) \to (B, u)$ is a morphism $f: A \to B$ in $C$ such that $f \circ t = u \circ Tf$. For any functor $F: C \to C$, an Eilenberg-Moore distributive law – or EM-law for short – is a natural transformation $\lambda: [F, T]$ such that the $(\eta^-)$ and $(\mu^-)$ axioms are satisfied. Let $S$ and $T$ be two monads and $\lambda: [S, T]$ be a natural transformation. A $\lambda$-algebra is a triple $(A, s, t)$ such that $(A, s)$ is an $S$-algebra, $(A, t)$ is a $T$-algebra, and the following condition is satisfied:

$$s \circ St \circ \lambda_X = t \circ Ts \qquad (\lambda\text{-condition})$$

A morphism of $\lambda$-algebras is a simultaneous $S$-algebra and $T$-algebra morphism.

The following result is widely known:

**Theorem 4.15 ([1,15])** Let $\lambda: [S, T]$ be a natural transformation.

* If $\lambda$ is a distributive law, then the categories of $(S \circled{\lambda} T)$-algebras and $\lambda$-algebras are isomorphic.

* If $\lambda$ is a weak distributive law, then the categories of $(S \circled{\lambda} T)$-algebras and $\lambda$-algebras are isomorphic.

Let $A$ be an object of $C$ and let $\underline{A}: C \to C$ be the constant functor $\underline{AX} \triangleq A$, $\underline{Af} \triangleq 1_A$.

**Proposition 4.16** Let $t: TA \to A$ be a morphism. The natural transformation $[t]: [\underline{A}, T]$ defined by $[t]_X = t$ is an EM-law if and only if $t$ is a $T$-algebra.

**Proof.** Naturality of $[t]$ amounts to the obvious equation $1_A \circ t = t \circ T(1_A)$. The $(\eta^-)$ axiom of $[t]$ is equivalent to the equation $[t]_X \circ \eta_{\underline{AX}}^T = \underline{A}\eta_X^T$ for all objects $X$, which simplifies into the unitality axiom $t \circ \eta_A^T = 1_A$. The $(\mu^-)$ axiom of $[t]$ is equivalent to the equation $\underline{A}\mu_X^T \circ [t]_{TX} \circ T[t]_X = [t]_X \circ \mu_{\underline{AX}}^T$ for all objects $X$, which simplifies into the associativity axiom $t \circ Tt = t \circ \mu_A^T$. $\square$

**Proposition 4.17** Let $(A, s)$ be an $S$-algebra, $(A, t)$ be a $T$-algebra, and $\lambda: [S, T]$ be a natural transformation. Then $(A, s, t)$ satisfies the $(\lambda$-condition) if and only if the Yang-Baxter equation holds between $[s]: [\underline{A}, S]$, $[t]: [\underline{A}, T]$ and $\lambda: [S, T]$.

**Proof.** The Yang-Baxter equation is $[s]_{TX} \circ S[t]_X \circ \lambda_{\underline{AX}} = \underline{A}\lambda_X \circ [t]_{SX} \circ T[s]_X$ for all objects $X$, which simplifies into the $(\lambda$-condition) $s \circ St \circ \lambda_A = 1_A \circ t \circ Ts$. $\square$

Therefore

* the functor $\lambda$-algebras $\to (S \circled{\lambda} T)$-algebras from Theorem 4.15 is a particular case of Theorem 4.1;

* the functor $\lambda$-algebras $\to (S \circled{\lambda} T)$-algebras from Theorem 4.15 is a particular case of Theorem 4.5.

Let us illustrate e.g. the second point. Let $\lambda: [S, T]$ be a weak distributive law and $(A, s, t)$ be a $\lambda$-algebra. According to Propositions 4.16 and 4.17, we are in the presence of a Yang-Baxter equation with one weak distributive law $\lambda$ and two EM-laws $[s]$ and $[t]$. By applying a mild variation of Theorem 4.5 – consisting in forgetting the monad structure of the functor $R = \underline{A}$ – we get an EM-law $\psi = \underline{A}\pi^\lambda \circ [s]T \circ S[t] \circ \iota^\lambda \underline{A}: [\underline{A}, S \circled{\lambda} T]$. That law satisfies $\psi_X = s \circ St \circ \iota_A^\lambda$ for all objects $X$. Via Proposition 4.16, we get that $s \circ St \circ \iota_A^\lambda$ is an $(S \circled{\lambda} T)$-algebra. As expected, this procedure amounts to the action of the functor $\lambda$-algebras $\to (S \circled{\lambda} T)$-algebras, that is, $(A, s, t) \mapsto s \circ St \circ \iota_A^\lambda$.

# 5 Discussion and Future Work

## 5.1 Advocating String Diagrams

One of the aims of this paper is to advocate string diagrams for proof research and communication. Let us provide two more examples that support our position.
### 5.1.1 Cheng's theorem

Let us begin with Cheng's result [11, Theorem 1.6], proved in [11, Appendix A]. The largest commutative diagram occurring in the proof for the initialisation case with 3 monads comprises 12 elementary commutative polygons, out of which 9 are naturality squares. Therefore, there are only 3 significant steps in the underlying proof. In an equivalent string-diagrammatic representation of the proof, these three steps are remarkably well identified:

<figure><img src="image_14.png" /></figure>

That computation (more precisely, its symmetric) has been generalised to weak distributive laws in the present paper: compare diagrams (49) and (24).

### 5.1.2 Winter's theorem

Another striking example arises from [38]. As already mentioned in the introduction, the proof of [38, Theorem 5] required a Prolog program to find a convenient tiling of the largest required commutative diagram, depicted in [38, Appendix A]. That diagram comprises $13 + 10 = 23$ elementary commutative polygons, out of which 15 are naturality squares. Therefore, there are only 8 significant steps in the underlying proof. An equivalent string-diagrammatic formalisation of the diagram in question is presented in Appendix C. As expected, it contains only 8 steps, and the computation can be carried out in one single line. Winter's proof research was obfuscated by what Hinze and Marsden call *bookkeeping* [20], i.e., administrative operations devoid of significant mathematical content.

## 5.2 Conclusion

This paper generalises iteration to weak distributive laws using the graphical calculus of string diagrams. It is an additional step in developing the theory of weak distributive laws, as is our line of research in [17,18,16]. The paper revolves around one main theoretical result, split in Theorems 4.3, 4.5 and 4.6, and provides several examples. A possible extension would be to derive – in the style of Section 4.2 – a generic Yang-Baxter equation stating compatibility of *monotone* laws. Monotone laws are a certain class of laws of type [*P*,*T*] and often carry significant semantic content. This direction is particularly interesting, as all known non-trivial examples of weak distributive laws are based on monotone laws. One may also ask whether the existence of a composite law entails the Yang-Baxter equation – this question has been positively solved by Winter in the case of distributive laws [38, Proposition 11].

As hinted in Section 4.3, our results easily adapt to EM-laws (and their duals, called Kleisli-laws), i.e., distributive laws between a monad and a *functor*. This paves the way for applications of iterated laws in coalgebra theory – as already attempted in [38] – where both EM-laws and Kleisli-laws are ubiquitous. Another possible follow-up to the vision developed in Section 4.3 is to *weaken algebras*. Indeed, as some EM-laws turn out to be algebras, some *weak* EM-laws turn out to be so-called *semialgebras* (as defined in [15]). Dually, *coweak* Kleisli-laws probably correspond to an interesting class of free algebras. Clarifying the whole picture will most likely enhance the still underdeveloped theory of *coweak* distributive laws.

Iteration of standard distributive laws has been heavily exploited in the context of categories-as-monads [39,8,7,6]. Phrasing our results in a 2-categorical setting, as did Cheng for iterated distributive laws [11], would enable new case studies to arise in that area.

On another level, our key message is to advocate string diagrams to deal with categorical proofs in contexts where traditional equational or commutative-diagrammatic proofs become unreadable. String diagrams are often more convenient in such proofs, as they allow to take a step further by hiding part of
the complexity in the graphical formalism. Nevertheless, they also have limitations. In the main result of Cheng [11, Theorem 1.6], iteration is performed not only for three monads but for any finite number *n* of monads: the *n* = 3 case does only initialise an induction. Generalising the *n* = 3 result to weak laws becomes reachable using string diagrams – though some diagrams in the proof of Theorem 4.6 already have substantial size. Even with a string-diagrammatic approach, generalizing further to *n* monads may require tedious proofs. Our opinion is that ingenious string-diagrammatic reasoning significantly pushes back the – fuzzy and subjective – boundary between proofs that are intelligible and those that are not.

## References

[1] Beck, J., *Distributive laws*, in: B. Eckmann, editor, *Seminar on Triples and Categorical Homology Theory*, pages 119–140, Springer Berlin Heidelberg, Berlin, Heidelberg (1969), ISBN 978-3-540-36091-9.
https://doi.org/10.1007/BFb0083084

[2] Bonchi, F., F. Gadducci, A. Kissinger, P. Sobocinski and F. Zanasi, *String diagram rewrite theory I: rewriting with frobenius structure*, J. ACM 69, pages 14:1–14:58 (2022).
https://doi.org/10.1145/3502719

[3] Bonchi, F., R. Piedeleu, P. Sobocinski and F. Zanasi, *Bialgebraic foundations for the operational semantics of string diagrams*, Inf. Comput. 281, page 104767 (2021).
https://doi.org/10.1016/j.ic.2021.104767

[4] Bonchi, F. and A. Santamaria, *Combining semilattices and semimodules*, in: S. Kiefer and C. Tasson, editors, *Foundations of Software Science and Computation Structures - 24th International Conference, FOSSACS 2021, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2021, Luxembourg City, Luxembourg, March 27 - April 1, 2021, Proceedings*, volume 12650 of *Lecture Notes in Computer Science*, pages 102–123, Springer (2021).
https://doi.org/10.1007/978-3-030-71995-1_6

[5] Bonchi, F., A. Silva and A. Sokolova, *Distribution Bisimilarity via the Power of Convex Algebras*, Logical Methods in Computer Science **Volume 17**, Issue 3 (2021).
https://doi.org/10.46298/lmcs-17(3:10)2021

[6] Bonchi, F., P. Sobocinski and F. Zanasi, *Deconstructing Lawvere with distributive laws*, J. Log. Algebraic Methods Program. 95, pages 128–146 (2018).
https://doi.org/10.1016/j.jlamp.2017.12.002

[7] Bonchi, F., P. Sobociński and F. Zanasi, *Interacting Hopf algebras*, Journal of Pure and Applied Algebra 221, pages 144–184 (2017), ISSN 0022-4049.
https://doi.org/10.1016/j.jpaa.2016.06.002

[8] Bonchi, F. and F. Zanasi, *Bialgebraic semantics for logic programming*, Log. Methods Comput. Sci. 11 (2015).
https://doi.org/10.2168/LMCS-11(1:14)2015

[9] Böhm, G., *The weak theory of monads*, Advances in Mathematics 225, pages 1–32 (2010), ISSN 0001-8708.
https://doi.org/10.1016/j.aim.2010.02.015

[10] Böhm, G., S. Lack and R. Street, *On the 2-categories of weak distributive laws*, Communications in Algebra 39, pages 4567–4583 (2011).
https://doi.org/10.1080/00927872.2011.616436

[11] Cheng, E., *Iterated distributive laws*, Mathematical Proceedings of the Cambridge Philosophical Society 150, page 459–487 (2011).
https://doi.org/10.1017/S0305004110000599

[12] Coecke, B. and A. Kissinger, *Picturing Quantum Processes: A First Course in Quantum Theory and Diagrammatic Reasoning*, Cambridge University Press (2017).
https://doi.org/10.1017/9781316219317

[13] Dahlqvist, F. and R. Neves, *Compositional semantics for new paradigms: probabilistic, hybrid and beyond*, arXiv preprint arXiv:1804.04145 (2018).
https://doi.org/10.48550/arXiv.1804.04145
[14] Dahlqvist, F., L. Parlant and A. Silva, *Layer by layer – combining monads*, in: B. Fischer and T. Uustalu, editors, *Theoretical Aspects of Computing – ICTAC 2018*, pages 153–172, Springer International Publishing, Cham (2018), ISBN 978-3-030-02508-3.
https://doi.org/10.1007/978-3-030-02508-3_9

[15] Garner, R., *The Vietoris monad and weak distributive laws*, Applied Categorical Structures **28**, pages 339–354 (2020), ISSN 0927-2852.
https://doi.org/10.1007/s10485-019-09582-w

[16] Goy, A., *On the compositionality of monads via weak distributive laws*, Ph.D. thesis, Université Paris-Saclay, Gif-sur-Yvette, France (2021).

[17] Goy, A. and D. Petrişan, *Combining probabilistic and non-deterministic choice via weak distributive laws*, in: *Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science*, LICS '20, page 454–464, Association for Computing Machinery, New York, NY, USA (2020), ISBN 9781450371049.
https://doi.org/10.1145/3373718.3394795

[18] Goy, A., D. Petrişan and M. Aiguier, *Powerset-like monads weakly distribute over themselves in toposes and compact Hausdorff spaces*, in: *Proceedings of the 48th International Colloquium on Automata, Languages, and Programming*, ICALP '21, Association for Computing Machinery (2021).
https://doi.org/10.4230/LIPIcs.ICALP.2021.132

[19] Hinze, R. and D. Marsden, *Dragging proofs out of pictures*, in: S. Lindley, C. McBride, P. W. Trinder and D. Sannella, editors, *A List of Successes That Can Change the World - Essays Dedicated to Philip Wadler on the Occasion of His 60th Birthday*, volume 9600 of *Lecture Notes in Computer Science*, pages 152–168, Springer (2016).
https://doi.org/10.1007/978-3-319-30936-1_8

[20] Hinze, R. and D. Marsden, *Equational reasoning with lollipops, forks, cups, caps, snakes, and speedometers*, J. Log. Algebraic Methods Program. **85**, pages 931–951 (2016).
https://doi.org/10.1016/j.jlamp.2015.12.004

[21] Jacobs, B., *From multisets over distributions to distributions over multisets*, in: *2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)*, pages 1–13 (2021).
https://doi.org/10.1109/LICS52264.2021.9470678

[22] Jacobs, B., A. Silva and A. Sokolova, *Trace semantics via determinization*, Journal of Computer and System Sciences **81**, pages 859–879 (2015), ISSN 0022-0000. 11th International Workshop on Coalgebraic Methods in Computer Science, CMCS 2012 (Selected Papers).
https://doi.org/10.1016/j.jcss.2014.12.005

[23] Joyal, A. and R. Street, *The geometry of tensor calculus, I*, Advances in Mathematics **88**, pages 55–112 (1991), ISSN 0001-8708.
https://doi.org/10.1016/0001-8708(91)90003-P

[24] Karamlou, A. and N. Shah, *No-go theorems for mixed distributive laws: extended abstract*, in: *CMCS short contributions*, Munich, Germany (2022).

[25] Klin, B. and J. Salamanca, *Iterated covariant powerset is not a monad*, Electronic Notes in Theoretical Computer Science **341**, pages 261–276 (2018), ISSN 1571-0661. Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV).
https://doi.org/10.1016/j.entcs.2018.11.013

[26] Manes, E. and P. Mulry, *Monad compositions. i: General constructions and recursive distributive laws*, Theory and Applications of Categories [electronic only] **18**, pages 172–208 (2007).

[27] Manes, E. and P. Mulry, *Monad compositions ii: Kleisli strength*, Mathematical Structures in Computer Science **18**, page 613–643 (2008).
https://doi.org/10.1017/S0960129508006695

[28] Marsden, D., *Category theory using string diagrams*, arXiv preprint arXiv:1401.7220 (2014).
https://doi.org/10.48550/arXiv.1401.7220

[29] Moggi, E., *Notions of computation and monads*, Information and Computation **93**, pages 55–92 (1991), ISSN 0890-5401. Selections from 1989 IEEE Symposium on Logic in Computer Science.
https://doi.org/10.1016/0890-5401(91)90052-4

[30] Parlant, L., *Monad Composition via Preservation of Algebras*, Ph.D. thesis, UCL (University College London) (2020).
https://discovery.ucl.ac.uk/id/eprint/10112228/1/Thesis_Louis_Parlant_UCL_upload.pdf
## B.2 Separate and Merge the Triple Functor

Let us prove the four equations displayed in (39), which we recall here:

<figure><img src="image_15.png" /></figure>

For once we may restate and prove these properties using plain equational reasoning – they will nonetheless be applied in string-diagrammatic form in the next section. Equationally, the properties are as follows:

$$Rl^{\lambda} \circ l^{\psi} = R\kappa^{\lambda} \circ l^{\sigma}T \circ l^{\varphi} \qquad (S1)$$

$$l^{\sigma}T \circ l^{\varphi} = \kappa^{\sigma}T \circ Rl^{\lambda} \circ l^{\psi} \qquad (S2)$$

$$\pi^{\psi} \circ R\pi^{\lambda} = \pi^{\varphi} \circ \pi^{\sigma}T \circ R\kappa^{\lambda} \qquad (M1)$$

$$\pi^{\varphi} \circ \pi^{\sigma}T = \pi^{\psi} \circ R\pi^{\lambda} \circ \kappa^{\sigma}T \qquad (M2)$$

To prove (S1) and (M1), recall that we defined $l^{\psi} = \beta \circ l^{\varphi}$ and $\pi^{\psi} = \pi^{\varphi} \circ \alpha$, where $\alpha = \pi^{\sigma}T \circ Rl^{\lambda}$ and $\beta = R\pi^{\lambda} \circ l^{\sigma}T$. Hence

$$Rl^{\lambda} \circ l^{\psi} = Rl^{\lambda} \circ \beta \circ l^{\varphi} \qquad (B.4)$$

$$= Rl^{\lambda} \circ R\pi^{\lambda} \circ l^{\sigma}T \circ l^{\varphi} \qquad (B.5)$$

$$= R\kappa^{\lambda} \circ l^{\sigma}T \circ l^{\varphi} \qquad (B.6)$$

and

$$\pi^{\psi} \circ R\pi^{\lambda} = \pi^{\varphi} \circ \alpha \circ R\pi^{\lambda} \qquad (B.7)$$

$$= \pi^{\varphi} \circ \pi^{\sigma}T \circ Rl^{\lambda} \circ R\pi^{\lambda} \qquad (B.8)$$

$$= \pi^{\varphi} \circ \pi^{\sigma}T \circ R\kappa^{\lambda} \qquad (B.9)$$

To prove (S2) and (M2), notice that $l^{\varphi} = \kappa^{\varphi} \circ l^{\psi} = \alpha \circ \beta \circ l^{\varphi} = \alpha \circ l^{\psi}$, and similarly $\pi^{\varphi} = \pi^{\psi} \circ \beta$. Hence

$$l^{\sigma}T \circ l^{\varphi} = l^{\sigma}T \circ \alpha \circ l^{\psi} \qquad (B.10)$$

$$= l^{\sigma}T \circ \pi^{\sigma}T \circ Rl^{\lambda} \circ l^{\psi} \qquad (B.11)$$

$$= \kappa^{\sigma}T \circ Rl^{\lambda} \circ l^{\psi} \qquad (B.12)$$

and

$$\pi^{\varphi} \circ \pi^{\sigma}T = \pi^{\psi} \circ \beta \circ \pi^{\sigma}T \qquad (B.13)$$

$$= \pi^{\psi} \circ R\pi^{\lambda} \circ l^{\sigma}T \circ \pi^{\sigma}T \qquad (B.14)$$

$$= \pi^{\psi} \circ R\pi^{\lambda} \circ \kappa^{\sigma}T \qquad (B.15)$$

## B.3 Units and Multiplications Coincide

At this point, we already know that the weak distributive laws $\varphi: [R \bullet S, T]$ and $\psi: [R, S \bullet T]$ generate respectively a monad $(R \bullet S) \bullet T$ and a monad $R \bullet (S \bullet T)$ whose underlying functors coincide. It remains to prove that the units and multiplications coincide. Let us begin with units.
equation, equation (11) and the retract equation again.

<figure><img src="image_16.png" /></figure>

Hence both multiplications are equal. This achieves the proof that $(R \bullet S) \bullet T$ and $R \bullet (S \bullet T)$ coincide as monads.

## C Proofs of Section 5

In this section we restate one implication of [38, Theorem 5] and prove it using string diagrams.

**Definition C.1** Let $F$ be a functor, $S$ and $T$ be monads, and $S \circ T$ be their composite monad with respect to some distributive law of type $[S, T]$. A Winter-law is a natural transformation $\lambda: TF \Rightarrow FST$ such that

$$ \lambda \circ \eta^T F = F \eta^{S \circ T} \qquad (\eta^*) $$

$$ \lambda \circ \mu^T F = F \mu^{S \circ T} \circ \lambda S T \circ T \lambda \qquad (\mu^*) $$

**Theorem C.2 (Winter's theorem converse implication)** Let $F$ be a functor, $S$ and $T$ be monads, $\lambda^0: [S, T]$ be a distributive law, $\lambda^1: TF \Rightarrow FST$ be a Winter-law and $\lambda^2: [F, S]$ be an EM-law. Assume the following coherence axiom is satisfied:

$$ F \mu^{ST} \circ F S \lambda^0 \circ \lambda^1 S \circ T \lambda^2 = F \mu^{ST} \circ \lambda^2 S T \circ S \lambda^1 \circ \lambda^0 F \qquad (\text{coh}) $$

Let

$$ \hat{\lambda} \triangleq STF \overset{S\lambda^1}{\Longrightarrow} SFST \overset{\lambda^2ST}{\Longrightarrow} FSST \overset{F\mu^{ST}}{\Longrightarrow} FST \qquad (C.1) $$

Then $\hat{\lambda}: [F, S \circ T]$ is an EM-law.

**Proof.** First, we express all available data using string diagrams.

<figure><img src="image_17.png" /></figure>

<figure><img src="image_18.png" /></figure>
Axioms specific to Winter's framework are displayed below:

<figure><img src="image_19.png" /></figure>

By definition, the natural transformation $\hat{\lambda}$ is as follows:

<figure><img src="image_20.png" /></figure>

The $(\eta^{-})$ axiom for $\hat{\lambda}$ can be proved using $\lambda^2$ $(\eta^{-})$ axiom, $\eta^S$ unitality and $\lambda^1$ $(\eta^*)$ axiom.

<figure><img src="image_21.png" /></figure>

The $(\mu^{-})$ axiom for $\hat{\lambda}$ can be proved using $\lambda^1$ $(\mu^*)$ axiom, $\lambda^2$ $(\mu^{-})$ axiom, $\mu^S$ associativity twice, equation (coh), $\mu^S$ associativity twice again, and $\lambda^0$ $(\mu^+)$ axiom.

<figure><img src="image_22.png" /></figure>