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

HAL
open science

Semialgebras and Weak Distributive Laws

Daniela Petrişan, Ralph Sarkis

► To cite this version:

Daniela Petrişan, Ralph Sarkis. Semialgebras and Weak Distributive Laws. 2021. hal-03261093v2

HAL Id: hal-03261093

https://hal.science/hal-03261093v2

Preprint submitted on 8 Sep 2021

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.
# Semialgebras and Weak Distributive Laws

Daniela Petrişan<fnref n="2" />

IRIF
Paris, France

Ralph Sarkis<fnref n="3" />

ENS de Lyon
Lyon, France

## Abstract

Motivated by recent work on weak distributive laws and their applications to coalgebraic semantics, we investigate the algebraic nature of semialgebras for a monad. These are algebras for the underlying functor of the monad subject to the associativity axiom alone — the unit axiom from the definition of an Eilenberg–Moore algebras is dropped. We prove that if the underlying category has coproducts, then semialgebras for a monad $M$ are in fact the Eilenberg–Moore algebras for a suitable monad structure on the functor $id + M$, which we call the semifree monad $M^s$. We also provide concrete algebraic presentations for semialgebras for the maybe monad, the semigroup monad and the finite distribution monad.

A second contribution is characterizing the weak distributive laws of the form $MT \Rightarrow TM$ as strong distributive laws $M^sT \Rightarrow TM^s$ subject to an additional condition.

Keywords: weak distributive law, semialgebra, convex semialgebra, convex algebra

## 1 Introduction

Distributive laws [3] are a standard approach to composing monads. A distributive law of the monad $M$ over the monad $T$ is a natural transformation $\lambda: MT \Rightarrow TM$ satisfying four axioms that stipulate its interactions with the units and the multiplications of the two monads. Unfortunately, such laws do not exist in several instances relevant for the semantics of programming languages and for the composition of computational effects. For example, there is no distributive law of the finite distribution monad (used for modeling probabilistic choice) over the powerset monad (used for modeling non-determinism), see [21, 22]. Similarly, there is no distributive law of the powerset monad over itself [14]. The absence of such laws renders it difficult to reason in a compositional way about systems combining non-determinism and probabilistic choice, as emphasized in a series of works in domain theory [12, 17] or in coalgebraic semantics [5, 7, 16].

Recently, weaker notions of distributive laws have been considered [4, 8, 19]. In particular, Garner [8] introduces a notion of weak distributive law $\lambda: MT \Rightarrow TM$ in which he drops the axiom related to the unit of the monad $M$, while maintaining the three other axioms. He proves that weak distributive laws correspond under mild assumptions to a suitable notion of weak liftings of the monad $T$ to the Eilenberg–Moore algebras of $M$. The main example in loc. cit. is a canonical weak distributive law of the ultrafilter monad over the

This document is a preprint.

<footnote n="1">¹ We thank Christine Tasson and Martin Hyland for discussion on these topics once upon a time in the wake of the pandemic when IRIF was still filled with people and thesis were defended on campus. This work was performed within the framework of the LABEX MILYON (ANR-10-LABX-0070) of Université de Lyon, within the program "Investissements d'Avenir" (ANR-11-IDEX-0007) operated by the French National Research Agency (ANR).</footnote>

<footnote n="2">² Email: petrisan@irif.fr</footnote>

<footnote n="3">³ Email: ralph.sarkis@ens-lyon.fr</footnote>
powerset monad. The corresponding weak lifting of the powerset monad is the Vietoris monad on the category of compact Hausdorff spaces.

In [9], the same techniques were employed to find a canonical weak distributive law of the finite distribution monad $\mathcal{D}$ over the powerset monad $\mathcal{P}$. The corresponding weak lifting of the powerset is the convex powerset monad on the category of convex algebras — the Eilenberg–Moore algebras for $\mathcal{D}$. This weak distributive law enables a neat compositional approach to the coalgebraic semantics of systems featuring both non-determinism and probabilistic choice. This line of work was further extended to a continuous setting in [10] where a weak distributive law of the Vietoris monad over itself was given. Furthermore, [6] provides a weak distributive law between the powerset monad and the left-semimodule monad.

One of the technical ingredients in Garner's paper was to use the fact that a weak distributive law $\lambda: MT \Rightarrow TM$ induces a lifting of the monad $T$ to the category of semialgebras for the monad $M$, where a semialgebra is a morphism $a: MX \to X$ satisfying only the associativity axiom from the standard definition of an Eilenberg–Moore algebra. The weak lifting of the monad $T$ is then obtained by splitting a certain idempotent in the category of semialgebras for $M$.

For example, the weak law of [9] corresponds to a lifting of $\mathcal{P}$ to the category of semialgebras for the monad $\mathcal{D}$, which we refer to as convex semialgebras. A natural question arising in these examples is what are concrete descriptions of semialgebras. Even if it may seem surprising at first, dropping the unit axiom alone does not considerably impair the structure given by operations and equations.

Let us illustrate this with a simpler example, namely the semialgebras for the maybe monad — which maps $X$ to $X + 1$ where $1 = \{\star\}$. All the details will be given in Section 5. First, recall that algebras for the maybe monad are pointed sets. Indeed, such an algebra is a map $a: X + 1 \to X$ satisfying the usual unit axiom ($a \circ \eta_X = \text{id}_X$) and an associativity axiom. Already the unit axiom entails that the first component of $a$ is the identity on $X$, hence to give an algebra structure $a$ amounts to give one point $\bullet: 1 \to X$.

Let us consider now semialgebras $a: X+1 \to X$ for the maybe monad. We no longer have that $a \circ \eta_X = \text{id}_X$, but using the associativity axiom, we can infer that $a \circ \eta_X$ is the first component of $a$, it is idempotent, and furthermore, it preserves the point $\bullet: 1 \to X$. We can prove that the semialgebras for the maybe monad are pointed sets equipped with an idempotent unary operation that preserves the point. This algebraic theory corresponds to a monad structure on the functor $X+X+1$, that is, the coproduct of the identity functor and the underlying functor of the maybe monad. Perhaps surprisingly, this result generalizes to arbitrary monads on categories with coproducts.

**Contributions.**

A first contribution of our paper is to unravel the algebraic nature of semialgebras. Given a monad $M$ on a category $\mathbf{C}$ with coproducts, we exhibit a monad structure $\mathcal{M}^s$ on the functor $\text{id} + M$ (Theorem 3.3) and we show that the category of Eilenberg–Moore semialgebras for $M$ is isomorphic to the category of Eilenberg–Moore algebras for $\mathcal{M}^s$ (Theorem 3.4). In Section 5 we consider several examples: the maybe monad, the semigroup monad and the finite distribution monad. In each case we provide concrete algebraic presentations for the semialgebras.

A second contribution of our paper can be summed up in the slogan “Weak distributive laws are strong”. Indeed, we can characterize the liftings of the monad $T$ to the category of semialgebras for $M$ that correspond to weak distributive laws $MT \Rightarrow TM$, obtaining a correspondence theorem akin to that of Beck, Theorem 4.1. Combining this result with the isomorphism between semialgebras for $M$ and algebras for $\mathcal{M}^s$, we prove a correspondence between weak distributive laws $MT \Rightarrow TM$ and strong distributive laws $\mathcal{M}^s T \Rightarrow TM^s$ that satisfy an additional constraint (Theorem 4.3).

**Related work.**

A similar question has been addressed in [11] in a 2-dimensional setting. In loc. cit. left semialgebras for a 2-monad were shown to be the algebras for another 2-monad, which was obtained using a colax colimit construction, see [11, Proposition 27].

# 2 Background

In this section, we present some definitions and results about monads, distributive laws, coproducts and universal algebra. We assume some familiarity with basic concepts in category theory — [1, 15, 18] are standard references.

## 2.1 Monads and Distributive Laws

**Definition 2.1** A **monad** on a category **C** is a triple comprised of an endofunctor $M: \mathbf{C} \to \mathbf{C}$ and two natural transformations $\eta: \text{id}_{\mathbf{C}} \Rightarrow M$ and $\mu: \mathcal{M}^2 \Rightarrow M$ called the **unit** and **multiplication** respectively that make (1) and (2) commute. We refer to (2) as the associativity of $\mu$.
$$ M \xrightarrow[M\eta]{M\eta} M^2 \xleftarrow[\mu]{\eta^M} M \qquad (1) $$

$$ \begin{array}{ccc} M^3 & \xrightarrow{\mu^M} & M^2 \\ M\mu & \downarrow & \downarrow^\mu \\ M^2 & \xrightarrow{\mu} & M \end{array} \qquad (2) $$

**Definition 2.2** Let $(M, \eta, \mu)$ be a monad on $\mathbf{C}$, an $M$-algebra is a pair $(X, x)$ consisting of an object $X$ and morphism $x: MX \to X$ in $\mathbf{C}$ such that (3) and (4) commute. We refer to (3) as the unit axiom of $x$ and to (4) as the associativity of $x$.

$$ X \xrightarrow[\text{id}_X]{\eta_x} MX \xrightarrow[x]{x} X \qquad (3) $$

$$ \begin{array}{ccc} M^2 X & \xrightarrow{\mu_x} & MX \\ M_x & \downarrow & \downarrow^x \\ MX & \xrightarrow[x]{x} & X \end{array} \qquad (4) $$

**Definition 2.3** Given two $M$-algebras $(X, x)$ and $(Y, y)$, an $M$-algebra homomorphism $h: (X, x) \to (Y, y)$ is a morphism $h: X \to Y$ in $\mathbf{C}$ making (5) commute.

$$ \begin{array}{ccc} MX & \xrightarrow{Mh} & MY \\ x & \downarrow & \downarrow^y \\ X & \xrightarrow{h} & Y \end{array} \qquad (5) $$

For a monad $M$, the category of $M$-algebras and their homomorphisms is called the **Eilenberg–Moore** category of $M$ and denoted $\text{EM}(M)$. We denote $U^M: \text{EM}(M) \to \mathbf{C}$ the forgetful functor sending an $M$-algebra $(X, x)$ to $X$ and a homomorphism to its underlying morphism. A morphism $x: MX \to X$ that satisfies associativity (4) (but not necessarily the unit axiom (3)) is called an **$M$-semialgebra**. We denote $\text{EM}_s(M)$ the category of $M$-semialgebras and their homomorphisms (defined as for $M$-algebras). We denote $U_s^M: \text{EM}_s(M) \to \mathbf{C}$ the forgetful functor sending an $M$-semialgebra $(X, x)$ to $X$ and a homomorphism to its underlying morphism.

Distributive laws between two monads, introduced in [3], are the category theoretic tool for composing monads and for representing that the corresponding algebraic structures interact in a suitable way via distributivity axioms.

**Definition 2.4** Let $(M, \eta^M, \mu^M)$ and $(T, \eta^T, \mu^T)$ be two monads, a natural transformation $\lambda: MT \Rightarrow TM$ is called a **(monad) distributive law of $M$ over $T$** if it makes the following diagrams commute.

$$ MT \xrightarrow[\lambda]{\eta^M T} T \xrightarrow[T\eta^M]{T\eta^M} TM \qquad (6) $$

$$ \begin{array}{ccc} MMT & \xrightarrow{M\lambda} & MTM \xrightarrow{\lambda M} TMM \\ \mu^M T & \downarrow & \downarrow^{T\mu^M} \\ MT & \xrightarrow[\lambda]{\lambda} & TM \end{array} \qquad (8) $$

$$ MT \xrightarrow[\lambda]{M\eta^T} T \xrightarrow[T\eta^T]{\eta^T} TM \qquad (7) $$

$$ \begin{array}{ccc} MTT & \xrightarrow{\lambda T} TMT & TMT \xrightarrow{T\lambda} TTM \\ M\mu^T & \downarrow & \downarrow^{\mu^T M} \\ MT & \xrightarrow[\lambda]{\lambda} & TM \end{array} \qquad (9) $$

In [4, 19], the authors investigated weaker notions of monad distributive laws motivated by work on weak entwining operators. More recently, Garner [8] used one of them to exhibit the Vietoris monad on the category of compact Hausdorff spaces as a weak lifting of the powerset monad. In the sequel, we adopt the terminology and definitions of [8].

**Definition 2.5** A weak distributive law of $M$ over $T$ is a natural transformation $\lambda: MT \Rightarrow TM$ making (7), (8) and (9) commute (but not necessarily (6)).

**Definition 2.6** A lifting of $T$ to $\text{EM}(M)$ is a monad $(\tilde{T}, \tilde{\eta}, \tilde{\mu})$ on $\text{EM}(M)$ such that the functor, unit and multiplication commute with the forgetful functor $U^M$, i.e., the following equations hold.

$$ U^M \circ \tilde{T} = T \circ U^M \qquad U^M \tilde{\eta} = \eta^T U^M \qquad U^M \tilde{\mu} = \mu^T U^M $$

A lifting of $T$ to $\text{EM}_s(M)$ is a monad $(\tilde{T}, \tilde{\eta}, \tilde{\mu})$ satisfying $U_s^M \tilde{T} = T U_s^M$, $U_s^M \tilde{\eta} = \eta^T U_s^M$ and $U_s^M \tilde{\mu} = \mu^T U_s^M$.
A standard result that goes back to the work of Beck is the correspondence between distributive laws and liftings to Eilenberg–Moore categories. We recall below the transformation of a law into a lifting and its inverse as we will later use them in the weak setting.

**Proposition 2.7** Distributive laws $\lambda : MT \Rightarrow TM$ are in correspondence with liftings of $T$ to EM($M$).

**Proof.** Given a distributive law $\lambda : MT \Rightarrow TM$, we construct a lifting $\tilde{T}$ sending $(X, x)$ to $(TX, Tx \circ \lambda_X)$. Its action on morphisms is determined by the equation $U^M \circ \tilde{T} = T \circ U^M$, it must send $f$ to $Tf$. Given a lifting $(\tilde{T}, \tilde{\eta}, \tilde{\mu})$, we construct a distributive law whose components are $\lambda_X = \tilde{T}\mu_X^M \circ MT\eta_X^M$ where $\tilde{T}\mu_X^M : MTMX \to TMX$ is the image of the free algebra $\mu_X^M : MMX \to MX$ under the functor $\tilde{T}$. $\square$

**Remark 2.8** There is a slight abuse of notation when writing $\tilde{T}\mu_X^M$. To avoid any ambiguity, we will reserve writing $\tilde{T}a$ only in the situations when $a$ is an algebra or semialgebra structure, but not when $a$ is a morphism of algebras. Notice that if $f$ is a morphism of algebras, then the morphism $\tilde{T}(f)$ is carried by $Tf$, since $\tilde{T}$ is a lifting. In this situation we simply write $Tf$ instead of $\tilde{T}(f)$.

## 2.2 Coproducts

We recall here the definition of coproducts in order to present our notation and useful equations.

**Definition 2.9** Let $X$ and $Y$ be objects of $\mathbf{C}$, the coproduct of $X$ and $Y$ is an object $X + Y$ and morphisms $\text{inl}^{X+Y} : X \to X + Y$ and $\text{inr}^{X+Y} : Y \to X + Y$ such that for any pair of morphisms $k_X : X \to K$ and $k_Y : Y \to K$, there is a unique mediating morphism $! : X + Y \to K$ making (10) commute.

$$ X \xrightarrow[\text{k}_Y]{\text{inl}^{X+Y}} X + Y \xrightarrow[\text{k}_Y]{\text{inr}^{X+Y}} Y \qquad (10) $$

We may omit the superscripts on $\text{inl}$ and $\text{inr}$ when the codomain is clear from context. We denote $[k_X, k_Y]$ the unique morphism $X + Y \to K$ satisfying $[k_X, k_Y] \circ \text{inl} = k_X$ and $[k_X, k_Y] \circ \text{inr} = k_Y$. Given morphisms $f : X \to X'$ and $g : Y \to Y'$, we denote $f + g := [\text{inl}^{X'+Y'} \circ f, \text{inr}^{X'+Y'} \circ g]$. In the rest of the paper, we will often use the following easily derivable identities.

$$ h \circ [k_X, k_Y] = [h \circ k_X, h \circ k_Y] \quad (11) $$

$$ (f+g) \circ \text{inl}^{X+Y} = \text{inl}^{X'+Y'} \circ f \quad (13) $$

$$ [k_{X'}, k_{Y'}] \circ (f+g) = [k_{X'}, \circ f, k_{Y'} \circ g] \quad (12) $$

$$ (f+g) \circ \text{inr}^{X+Y} = \text{inr}^{X'+Y'} \circ g \quad (14) $$

When $\mathbf{C}$ has all coproducts, the category of endofunctors on $\mathbf{C}$ also does and coproducts are taken pointwise. Namely, given functors $F, G : \mathbf{C} \to \mathbf{C}$, $F + G$ sends an object $X$ to $FX + GX$ and a morphism $f$ to $Ff + Gf$. Moreover, we have

$$ \text{inl}_X^{F+G} = \text{inl}^{FX+GX} \quad \text{and} \quad \text{inr}_X^{F+G} = \text{inr}^{FX+GX}. $$

## 2.3 Universal Algebra

Here, we introduce just enough universal algebra to make use of the link between algebraic theories and monads in Section 5 — [2] is a longer gentle introduction to these notions.

**Definition 2.10** An algebraic signature is a set $\Sigma$ of operation symbols along with arities in $\mathbb{N}$, we denote $f : n \in \Sigma$ for an $n$-ary operation symbol $f$ in $\Sigma$. Given a set $X$, one constructs the set of $\Sigma$-terms with variables in $X$, denoted $T_{\Sigma}(X)$ by iterating operations symbols:

$$ \begin{gathered} \forall x \in X, x \in T_{\Sigma}(X) \\ \forall t_1, \dots, t_n \in T_{\Sigma}(X), f : n \in \Sigma, f(t_1, \dots, t_n) \in T_{\Sigma}(X). \end{gathered} $$

An equation over $\Sigma$ is a pair of $\Sigma$-terms over a set of indeterminate variables which we usually denote with an equality sign (e.g.: $s = t$ for $s, t \in T_{\Sigma}(X)$ and $X$ is the set of variables). An algebraic theory is a tuple $(\Sigma, \mathcal{E})$ of a signature $\Sigma$ and a set $\mathcal{E}$ of equations over $\Sigma$.
**Proof.** Let us first expand both sides.

$$
\begin{align*}
\text{L.H.S.} &= \mu^s \circ \mu^s M^s \\
&= \mu^s \circ [\text{id}_{M^s+MM^s}, \text{inr}^{M^s+MM^s} \circ \mu M^s \circ M[\eta M^s, \text{id}_{MM^s}]] && \text{by def. } \mu^s \\
&= [\mu^s, \mu^s \circ \text{inr}^{M^s+MM^s} \circ \mu M^s \circ M[\eta M^s, \text{id}_{MM^s}]] && \text{by (11)} \\
&= [\mu^s, \text{inr}^{id+M} \circ \mu \circ M[\eta, \text{id}_M] \circ \mu M^s \circ M[\eta M^s, \text{id}_{MM^s}]] && \text{by def. } \mu^s \text{ and } [k_X, k_Y] \circ \text{inr} = k_Y
\end{align*}
$$

$$
\begin{align*}
\text{R.H.S.} &= \mu^s \circ M^s \mu^s \\
&= [\text{id}_{id+M}, \text{inr}^{id+M} \circ \mu \circ M[\eta, \text{id}_M]] \circ (\mu^s + M\mu^s) && \text{by def. } \mu^s \\
&= [\mu^s, \text{inr}^{id+M} \circ \mu \circ M[\eta, \text{id}_M] \circ M\mu^s] && \text{by (12)} \\
&= [\mu^s, \text{inr}^{id+M} \circ \mu \circ M([\eta, \text{id}_M] \circ \mu^s)] \\
&= [\mu^s, \text{inr}^{id+M} \circ \mu \circ M[[\eta, \text{id}_M] \circ \text{id}_{id+M}, [\eta, \text{id}_M] \circ \text{inr}^{id+M} \circ \mu \circ M[\eta, \text{id}_M]]] && \text{by (11)} \\
&= [\mu^s, \text{inr}^{id+M} \circ \mu \circ M[[\eta, \text{id}_M], \mu \circ M[\eta, \text{id}_M]]] && \text{by } [\eta, \text{id}_M] \circ \text{inr}^{id+M} = \text{id}_M
\end{align*}
$$

Since the left component is the same, it is enough to prove the right component is also the same, i.e. that

$$
\mathrm{inr}^{id+M} \circ \mu \circ M[\eta, \mathrm{id}_M] \circ \mu M^s \circ M[\eta M^s, \mathrm{id}_{MM^s}] = \mathrm{inr}^{id+M} \circ \mu \circ M[[\eta, \mathrm{id}_M], \mu \circ M[\eta, \mathrm{id}_M]].
$$

We pave the following diagram.

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

We show (a) below, (b) commutes by naturality of $\mu$ and (c) commutes by associativity of $\mu$. To prove (a)
commutes, we can remove one application on $M$ on every morphism and starting with the bottom path, we
have the following derivation.

$$
\begin{align*}
\mu \circ M[\eta, \mathrm{id}_M] \circ [\eta M^s, \mathrm{id}_{MM^s}] &= [\mu \circ M[\eta, \mathrm{id}_M] \circ \eta M^s, \mu \circ M[\eta, \mathrm{id}_M]] && \text{by (11)} \\
&= [\mu \circ \eta M \circ [\eta, \mathrm{id}_M], \mu \circ M[\eta, \mathrm{id}_M]] && \text{by nat. } \eta \\
&= [[\eta, \mathrm{id}_M], \mu \circ M[\eta, \mathrm{id}_M]] && \text{by (1)}
\end{align*}
$$

□

Combining Lemmas 3.1 and 3.2, we obtain the following result.

**Theorem 3.3** *The triple* $(M^s, \eta^s, \mu^s)$ *is a monad.*

Next, we show that this is the semifree monad on $M$.

**Theorem 3.4** There is an isomorphism $\mathrm{EM}(M^s) \cong \mathrm{EM}_s(M)$.

**Proof.** First, note that any $M^s$-algebra $\alpha : X + MX \to X$ must be of the form $\alpha = [\mathrm{id}_X, a]$ since $\mathrm{id}_X = \alpha \circ \eta_X^s = \alpha \circ \mathrm{inl}^{X+MX}$. Next, we claim the commutativity of the two following diagrams is equivalent, i.e., $[\mathrm{id}_X, a]$ is an $M^s$-algebra if and only if $a$ is an $M$-semialgebra.

$$
\begin{tikzcd}[column sep=2.8em, row sep=2.8em]
X + MX + M(X + MX) \arrow[r, "\mu_X"] & X + MX \arrow[l, "\mu_X"] \arrow[d, "[\mathrm{id}_X, a] + M[\mathrm{id}_X, a]"'] & X + MX \arrow[d, "[\mathrm{id}_X, a]"'] \\
[\mathrm{id}_X, a] + M[\mathrm{id}_X, a] \arrow[r, "a"] & [\mathrm{id}_X, a] \arrow[d, "[\mathrm{id}_X, a]"'] & [\mathrm{id}_X, a] \arrow[d, "a"]
\end{tikzcd}
\qquad
\begin{tikzcd}[column sep=2.8em, row sep=2.8em]
MMX \arrow[r, "\mu_X"] \arrow[d, "Ma"] & MX \arrow[d, "a"] \\
MX \arrow[r, "a"] & X
\end{tikzcd}
\qquad (18)
$$
Since the bottom path of (17) simplifies to [[id<sub>X</sub>, a], a ◦ M[id<sub>X</sub>, a]] and the top path simplifies to [[id<sub>X</sub>, a], a ◦ μ<sub>X</sub> ◦ M[η<sub>X</sub>, id<sub>MX</sub>]], we infer that the left square commutes if and only if

$$a \circ M[\mathrm{id}_X, a] = a \circ \mu_X \circ M[\eta_X, \mathrm{id}_{MX}]. \qquad (19)$$

Next, if (19) holds, we precompose by $\mathrm{Minr}^{X+MX}$ and find that

$$a \circ Ma = a \circ M[\mathrm{id}_X, a] \circ \mathrm{Minr}^{X+MX} = a \circ \mu_X \circ M[\eta_X, \mathrm{id}_{MX}] \circ \mathrm{Minr}^{X+MX} = a \circ \mu_X.$$

Conversely, if (18) commutes ($a \circ Ma = a \circ \mu_X$), we can derive the following two equalities.

$$\begin{align*} a \circ Ma \circ M\eta_X &= a \circ \mu_X \circ M\eta_X = a \\ a \circ \eta_X \circ a &= a \circ Ma \circ \eta_{MX} = a \circ \mu_X \circ \eta_{MX} = a, \end{align*}$$

which lead to the following derivation showing (19) holds.

$$\begin{align*} a \circ M[\mathrm{id}_X, a] &= a \circ Ma \circ M\eta_X \circ M[\mathrm{id}_X, a] && \text{by 1st eqn. above} \\ &= a \circ M[a \circ \eta_X, a \circ \eta_X \circ a] && \text{by (11)} \\ &= a \circ M[a \circ \eta_X, a] && \text{by 2nd eqn. above} \\ &= a \circ Ma \circ M[\eta_X, \mathrm{id}_{MX}] && \text{by (11)} \\ &= a \circ \mu_X \circ M[\eta_X, \mathrm{id}_{MX}] && \text{by (4)} \end{align*}$$

We have shown that the assignments $[\mathrm{id}_X, a] \mapsto a$ and $a \mapsto [\mathrm{id}_X, a]$ are well-typed, and they are clearly inverses. It is left to show they are functorial. It is enough to show that a homomorphism between $[\mathrm{id}_X, a]$ and $[\mathrm{id}_X, b]$ is a homomorphism between $a$ and $b$ and vice versa.

Suppose, $f \circ [\mathrm{id}_X, a] = [\mathrm{id}_X, b] \circ (f + Mf)$, then pre-composing with $\mathrm{inr}^{X+MX}$ yields $f \circ a = b \circ Mf$. Conversely, if $f \circ a = b \circ Mf$, we have

$$f \circ [\mathrm{id}_X, a] = [f, f \circ a] = [f, b \circ Mf] = [\mathrm{id}_X, b] \circ (f + Mf).$$

We conclude the desired isomorphism. □

**Remark 3.5** From the proof of the above theorem, we can also infer the following fact, which plays an important role in [8] and in the concrete presentations by operations and equations provided in Section 5. Given a semialgebra $a: MX \to X$ in $\mathrm{EM}_s(M)$, we have that $a \circ \eta_X: X \to X$ is idempotent, i.e., $(a \circ \eta_X) \circ (a \circ \eta_X) = a \circ \eta_X$.

# 4 Weak Distributive Laws are Strong

In this section, we will give an analogue to Proposition 2.7 in the case of weak distributive laws. Then, we will use the isomorphism $\mathrm{EM}_s(M) \cong \mathrm{EM}(M^s)$ to obtain a correspondence between weak distributive laws $MT \Rightarrow TM$ and (strong) distributive laws $M^s T \Rightarrow TM^s$ satisfying an additional constraint.

Let $(M, \eta^M, \mu^M)$ and $(T, \eta^T, \mu^T)$ be monads on a category $\mathcal{C}$ with all coproducts.

If we try to apply the same construction from Proposition 2.7 to a weak distributive law $\lambda: MT \Rightarrow TM$, we quickly encounter a problem when proving that for any $M$-algebra $x: MX \to X$, $\tilde{T}x := Tx \circ \lambda_X$ is an $M$-algebra. Indeed, showing that (3) commutes relies on the derivation

$$Tx \circ \lambda_X \circ \eta_{TX}^M = Tx \circ T\eta_X^M = Tid,$$

which needs (6) to commute, hence $\lambda$ to be strong. We will see in Theorem 4.1 that this is the only obstacle to construct a lifting, namely that the lifting $\tilde{T}$ is now on $\mathrm{EM}_s(M)$. Notice that the construction of the lifting $\tilde{T}$ to semialgebras obtained from a weak distributive law also appears in the proof of [8, Proposition 13]. However, Theorem 4.1 takes this further and characterizes the liftings $\tilde{T}$ on $\mathrm{EM}_s(M)$ that correspond to weak distributive laws.

Indeed, in the other direction, there is another issue when showing that the transformation obtained from a lifting on $\mathrm{EM}_s(M)$ makes (9) commute. In the setting of Proposition 2.7, we can use the fact that $\tilde{T}\mu_X^M$
satisfies the unit axiom of an M-algebra, but this is not necessarily the case here. Therefore, we must add the restriction (20) to the liftings on EM<sub>s</sub>(M) to obtain the correspondence in Theorem 4.1.

Let us try to provide some intuition behind the condition (20) featured in this theorem. Recall from Remark 3.5 that, whenever $\alpha: MA \to A$ is a semialgebra for $M$, then $\alpha \circ \eta_A$ is an idempotent, that we will denote here by $a: A \to A$. Also recall that $\tilde{T}\alpha: MTA \to TA$ is the semialgebra obtained by applying $\tilde{T}$ to $\alpha$. Then condition (20) roughly means that, given any term $t(x_1, \dots, x_n)$ in MTA, we have that $\tilde{T}\alpha(t(x_1, \dots, x_n)) = \tilde{T}\alpha(t(ax_1, \dots, ax_n))$, that is, applying the idempotent $a$ to the leaves of any term in MTA does not change the evaluation of that term under the semialgebra $\tilde{T}\alpha$.

**Theorem 4.1** *Weak distributive laws $\lambda: MT \Rightarrow TM$ are in correspondence with liftings $(\tilde{T}, \tilde{\eta}, \tilde{\mu})$ of $T$ to EM<sub>s</sub>(M) such that for any M-semialgebra $\alpha: MA \to A$,*

$$ \tilde{T}\alpha = \tilde{T}\alpha \circ MT\alpha \circ MT\eta_A^M. \qquad (20) $$

*Proof.* A full proof is given in the appendix. The correspondence is given by the same assignments as in Proposition 2.7 and in fact, the proof will closely follow the one in [20, Chapter 3] except for some minor steps mentioned above which rely on the distributive law being strong and the objects of EM(M) satisfying the unit axiom. $\square$

Next, we combine the characterization of liftings to semialgebras coming from weak distributive laws and the characterization of semialgebras as algebras for the semifree monad to obtain Theorem 4.3. For that, we need to describe how the isomorphism EM<sub>s</sub>(M) ≅ EM(M<sup>s</sup>) leads to a correspondence between liftings of T to these categories.

**Lemma 4.2** *Liftings of T to EM<sub>s</sub>(M) are in correspondence with liftings of T to EM(M<sup>s</sup>).*

*Proof.* Note that the isomorphism $S: EM_s(M) \cong EM(M^s): S^{-1}$ described in Theorem 3.4 commutes with the forgetful functors $U_s^M$ and $U^{M^s}$, namely, the following diagram commutes.

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

Therefore, it is straightforward to check that if $\tilde{T}$ is a lifting of $T$ on EM<sub>s</sub>(M), then $\tilde{T}^s := S\tilde{T}S^{-1}$ is a lifting of $T$ on EM(M<sup>s</sup>) and conversely if $\tilde{T}^s$ is a lifting of $T$ on EM(M<sup>s</sup>), then $S^{-1}\tilde{T}^s S$ is a lifting of $T$ on EM<sub>s</sub>(M). $\square$

**Theorem 4.3** *Weak distributive laws $\lambda: MT \Rightarrow TM$ are in correspondence with distributive laws $\delta: M^s T \Rightarrow TM^s$ satisfying*

$$ \delta \circ \mathrm{inr}^{T+MT} = T[\mathrm{inr}^{id+M} \circ \eta^M, \mathrm{inr}^{id+M}] \circ \delta \circ \mathrm{inr}^{T+MT}. \qquad (22) $$

*Proof.* First, note that a distributive law $\delta: M^s T \Rightarrow TM^s$ satisfies an instance of (6) saying $\delta \circ \eta^s T = T\eta^s$. Thus, we obtain that $\delta = [\mathrm{Tinl}^{id+M}, \delta^r]$ for some natural transformation $\delta^r: MT \Rightarrow TM^s$. Then, (22) can be simplified to

$$ \delta^r = T[\mathrm{inr}^{id+M} \circ \eta^M, \mathrm{inr}^{id+M}] \circ \delta^r. \qquad (23) $$

To further lighten notation, we let $\mu^{s,r} := \mathrm{inr}^{id+M} \circ \mu^M \circ M[\eta^M, \mathrm{id}_M]$ so that $\mu^s = [\mathrm{id}_{id+M}, \mu^{s,r}]$.

In the forward direction, we start with a weak distributive law $\lambda: MT \Rightarrow TM$ and let $\tilde{T}$ be the lifting obtained from Theorem 4.1. Through the isomorphism EM<sub>s</sub>(M) ≅ EM(M<sup>s</sup>), we obtain a lifting $\tilde{T}^s$ of T to EM(M<sup>s</sup>), it sends an M<sup>s</sup>-algebra $[\mathrm{id}_X, x]$ to $[\mathrm{id}_{TX}, \tilde{T}x]$. Next, by the correspondence in Proposition 2.7, we get a distributive law $\delta: M^s T \Rightarrow TM^s$ whose components are

$$ \delta_X = M^s TX \xrightarrow{M^s \mathrm{Tinl}^{X+M^X}} M^s TM^s X \xrightarrow{\tilde{T}^s \mu_X^s} TM^s X. $$

Since we know the first component is $\mathrm{Tinl}^{id+M}$, we are more interested in the second component which we find
to be

$$
\begin{align*}
\delta_X^r &= \tilde{T}^s \mu_X^s \circ M^s \mathrm{Tinl}^{X+MX} \circ \mathrm{inr}^{TX+MTX} \\
&= [\mathrm{id}_{T(X+MX)}, \tilde{T}\mu_X^{s,r}] \circ (\mathrm{Tinl}^{X+MX} + \mathrm{MTinl}^{X+MX}) \circ \mathrm{inr}^{TX+MTX} \\
&= [\mathrm{id}_{T(X+MX)}, \tilde{T}\mu_X^{s,r}] \circ \mathrm{inr}^{TM^s X+MTM^s X} \circ \mathrm{MTinl}^{X+MX} \\
&= \tilde{T}\mu_X^{s,r} \circ \mathrm{MTinl}^{X+MX}.
\end{align*}
$$

Now, using the fact that $\tilde{T}\mu_X^{s,r} = T\mu_X^{s,r} \circ \lambda_X$ and the definition of $\mu^{s,r}$, we find that

$$
\begin{align*}
T[\mathrm{inr}^{X+MX} \circ \eta_X^M, \mathrm{inr}^{X+MX}] \circ \delta_X^r &= T[\mathrm{inr}^{X+MX} \circ \eta_X^M, \mathrm{inr}^{X+MX}] \circ \tilde{T}\mu_X^{s,r} \circ \mathrm{MTinl}^{X+MX} \\
&= T[\mathrm{inr}^{X+MX} \circ \eta_X^M, \mathrm{inr}^{X+MX}] \circ T\mu_X^{s,r} \circ \lambda_X \circ \mathrm{MTinl}^{X+MX} \\
&= T[\mathrm{inr}^{X+MX} \circ \eta_X^M, \mathrm{inr}^{X+MX}] \circ \mathrm{Tinr}^{X+MX} \circ T\mu_X^M \circ \mathrm{TM}[\eta_X^M, \mathrm{id}_{MX}] \circ \lambda_X \circ \mathrm{MTinl}^{X+MX} \\
&= \mathrm{Tinr}^{X+MX} \circ T\mu_X^M \circ \mathrm{TM}[\eta_X^M, \mathrm{id}_{MX}] \circ \lambda_X \circ \mathrm{MTinl}^{X+MX} \\
&= \tilde{T}\mu_X^{s,r} \circ \mathrm{MTinl}^{X+MX} \\
&= \delta_X^r.
\end{align*}
$$

In the opposite direction, we start with a distributive law $\delta = [\mathrm{Tinl}^{id+M}, \delta^r] : M^s T \Rightarrow TM^s$ which is sent (using Proposition 2.7) to a lifting $\tilde{T}^s$ of $T$ on $\mathrm{EM}(M^s)$ that sends an $M^s$-algebra $[\mathrm{id}_X, x] : M^s X \to X$ to

$$
T[\mathrm{id}_X, x] \circ [\mathrm{Tinl}^{X+MX}, \delta_X^r] = [\mathrm{id}_{TX}, T[\mathrm{id}_X, x] \circ \delta_X^r].
$$

Using Lemma 4.2, we obtain a lifting $\tilde{T}$ on $\mathrm{EM}_s(M)$ sending an $M$-semialgebra $x : MX \to X$ to $T[\mathrm{id}_X, x] \circ \delta_X^r$.
After showing this lifting satisfies (20) below, we can use Theorem 4.1 to obtain the weak distributive law $\lambda$.

$$
\begin{align*}
\tilde{T}x \circ MTx \circ MT\eta_X^M &= T[\mathrm{id}_X, x] \circ \delta_X^r \circ MTx \circ MT\eta_X^M \\
&= T[\mathrm{id}_X, x] \circ T(x+Mx) \circ T(\eta_X^M + M\eta_X^M) \circ \delta_X^r && \text{by nat. of } \delta^r \\
&= T[x \circ \eta_X^M, x \circ Mx \circ M\eta_X^M] \circ \delta_X^r \\
&= T[x \circ \eta_X^M, x \circ \mu_X^M \circ M\eta_X^M] \circ \delta_X^r && \text{by assoc. of } x \\
&= T[x \circ \eta_X^M, x] \circ \delta_X^r && \text{by (2)} \\
&= T[\mathrm{id}_X, x] \circ T[\mathrm{inr}^{X+MX} \circ \eta_X^M, \mathrm{inr}^{X+MX}] \circ \delta_X^r && \text{by (23)} \\
&= T[\mathrm{id}_X, x] \circ \delta_X^r && \text{by (23)} \\
&= \tilde{T}x.
\end{align*}
$$

□

The results of Section 4 can be summarized as follows.

$$
\begin{array}{l@{\hspace{2em}}c@{\hspace{2em}}l}
\{\lambda : MT \stackrel{\text{w.d.l.}}{\Longrightarrow} TM\} & \stackrel{\text{Thm 4.1}}{\longleftarrow} & \{\tilde{T} : \text{EM}_s(M) \stackrel{\text{lifts } T}{\Longrightarrow} \text{EM}_s(M) \text{ satisfying (20)}\} \\
& \stackrel{\text{Lem 4.2}}{\longleftarrow} & \{\tilde{T}^s : \text{EM}(M^s) \stackrel{\text{lifts } T}{\Longrightarrow} \text{EM}(M^s) \text{ such that } S^{-1}\tilde{T}^s S \text{ satisfies (20)}\} \\
& \stackrel{\text{Thm 4.3}}{\longleftarrow} & \{\delta : M^s T \stackrel{\text{d.l.}}{\Longrightarrow} TM^s \text{ satisfying (23)}\}
\end{array}
$$

# 5 Examples

In this section, we give algebraic presentations of three semifree monads.

## 5.1 Maybe `Monad`

The maybe monad is defined on the functor $- + 1 : \mathbf{Set} \to \mathbf{Set}$ where $1 = \{\star\}$. The unit and multiplication have components given by

$$
\eta_X = \mathrm{inl}^{X+1} : X \to X + 1 \quad \text{and} \quad \mu_X = [\mathrm{id}_{X+1}, \mathrm{inr}^{X+1}] : X + 1 + 1 \to X + 1.
$$
By Theorems 3.3 and 3.4, we know that the semifree monad for $- + 1$ is a monad on the functor $X \mapsto X + X+1$ with unit $\eta_X^s = \text{inl}^{X+(X+1)}$ and multiplication $\mu_X^s = [\text{id}_X, \text{inr}^{X+(X+1)}] \circ [\text{id}_{X+1}, \text{inr}^{X+1}] \circ ([\text{inl}^{X+1}, \text{id}_{X+1}] + \text{id}_1)]$. This is very opaque and it does not help us understand the semialgebras for $- + 1$.

An alternative way to see these semialgebras is through the point of view of universal algebra. The theory of pointed sets containing a single constant $\bullet$: 0 with no equations is an algebraic presentation of the maybe monad. Briefly, this is because a $(-+1)$-algebra $a: X+1 \to X$ satisfies $\text{id}_X = a \circ \eta_X = a \circ \text{inl}$, thus $a = [\text{id}_X, \bullet]$ where $\bullet: 1 \to X$ is the constant. However, in a semialgebra, $a \circ \eta_X$ is only required to satisfy $a \circ \eta_X \circ a = a$ (see proof of Theorem 3.4). Therefore, denoting $a = [a, \bullet]$, we find (by pre-composing $a \circ \eta_X \circ a = a$ with $\text{inl}$ and $\text{inr}$) that $a$ is idempotent and $a(\bullet) = \bullet$. We infer that a $(-+1)$-semialgebra can be presented with an idempotent unary operation and a constant preserved by the idempotent.

**Theorem 5.1** Let $\Sigma_{+1}^s = \{a: 1, \bullet: 0\}$ and $E_{+1}^s = \{aa = ax, a\bullet = \bullet\}$, then $A(\Sigma_{+1}^s, E_{+1}^s) \cong \text{EM}_s(M)$.

**Proof.** A semialgebra for the maybe monad is a function $a: X+1 \to X$ satisfying $a \circ (a + \text{id}_1) = a \circ [\text{id}_{X+1}, \text{inr}^{X+1}]$. Pre-composing by $\text{inl}^{X+1}$ and $\text{inr}^{X+1}$, we find that, equivalently, $a$ satisfies $a \circ \text{inl} \circ a = a$.

Now, given a $(-+1)$-semialgebra $a: X+1 \to X$, we define $a := a \circ \text{inl}: X \to X$ and $\bullet := a \circ \text{inr}: 1 \to X$. These operations satisfy the equations in $E_{+1}^s$ by the following derivations.

$$a \circ a = a \circ \text{inl} \circ a \circ \text{inl} = a \circ \text{inl} = a$$

$$a \circ \bullet = a \circ \text{inl} \circ a \circ \text{inr} = a \circ \text{inr} = \bullet$$

Conversely, given $a: X \to X$ and $\bullet: 1 \to X$ satisfying $a \circ a = a$ and $a \circ \bullet = \bullet$, we define $a := [a, \bullet]: X+1 \to X$. To verify $[a, \bullet]$ is a $(-+1)$-semialgebra, it is enough to check that $[a, \bullet] \circ \text{inl} \circ [a, \bullet] = [a, \bullet]$. This follows like so:

$$[a, \bullet] \circ \text{inl} \circ [a, \bullet] = a \circ [a, \bullet] = [a \circ a, a \circ \bullet] = [a, \bullet].$$

These operations are clearly inverses, and we are left to show that they are functorial. Suppose $f: X \to Y$ is a homomorphism from $a$ to $b$ (i.e. $f \circ a = b \circ (f + \text{id}_1)$), then

$$f \circ a = f \circ a \circ \text{inl} = b \circ (f + \text{id}_1) \circ \text{inl} = b \circ \text{inl} \circ f = b \circ f$$

$$f \circ \bullet^a = f \circ a \circ \text{inr} = b \circ (f + \text{id}_1) \circ \text{inr} = b \circ \text{inr} = \bullet^b.$$

Conversely, suppose $f \circ a = b \circ f$ and $f \circ \bullet^a = \bullet^b$, then

$$f \circ [a, \bullet^a] = [f \circ a, f \circ \bullet^a] = [b \circ f, \bullet^b] = [b, \bullet^b] \circ (f + \text{id}_1).$$

□

## 5.2 Semigroup Monad

The semigroup (or non-empty lists) monad $(-)^+ : \text{Set} \to \text{Set}$ sends $X$ to $X^+$ the set of non-empty finite words over $X$ (we denote them with lists e.g.: $[x_1, x_2, x_3]$). The unit and multiplication are given by $\eta_X: X \to X^+ = x \mapsto [x]$ and

$$\mu_X : (X^+)^+ \to X^+ = [[x_{1,1}, \dots, x_{n_1,1}], \dots, [x_{k_1}, \dots, x_{n_k,k}]] \mapsto [x_{1,1}, \dots, x_{n_1,1}, x_{2,1}, \dots, x_{n_{k-1},k-1}, x_{k_1}, \dots, x_{n_k,k}].$$

This monad is presented by the theory of semigroups which contains a binary operation with an associativity equation. We will not bother working out what the semifree monad for $(-)^+$ is, and we give its algebraic presentation at once.

**Theorem 5.2** Let $\Sigma_{+}^s = \{a: 1, \bullet: 2\}$ and $E_{+}^s$ contain

$$aa = ax$$

$$a(x \cdot y) = x \cdot y$$

$$ax \cdot ay = x \cdot y$$

$$(x \cdot y) \cdot z = x \cdot (y \cdot z),$$

then $A(\Sigma_{+}^s, E_{+}^s) \cong \text{EM}_s((-)^+)$.
**Proof.** The structure of the proof is exactly the same as for Theorem 5.1 (all details are in the appendix). A $(-)^{+}$-semialgebra $a: X^+ \to X$ is sent to $(X, a: 0, \cdot: 2)$ where $a := a[-]$ and $\cdot := a[-, -]$. A $((\Sigma_+^s, E_+^s))$-algebra $(X, a, \cdot)$ is sent to $a: X^+ \to X = [x_1, \dots, x_n] \mapsto ax_1 \cdots ax_n$ which is well-defined by associativity of $\cdot$. There is a technical difficulty which requires us to prove (by induction) that the equations in $E_+^s$ imply

$$ \forall n \geq 2, \quad ax_1 \cdots ax_n = x_1 \cdots x_n = a(x_1 \cdots x_n). $$

□

## 5.3 Distribution Monad

The distribution monad $\mathcal{D}: \mathbf{Set} \to \mathbf{Set}$ sends $X$ to $\mathcal{D}X$ the set of finitely supported distributions on $X$, i.e.,

$$ \mathcal{D}(X) := \{ \varphi \in [0, 1]^X \mid \sum_{x \in X} \varphi(x) = 1 \text{ and } \varphi(x) \neq 0 \text{ for finitely many } xs \}. $$

Its unit and multiplication are given by $\eta_X = x \mapsto 1x$, where $1x$ is the Dirac distribution at $x$, and

$$ \mu_X = \Phi \mapsto \left( x \mapsto \sum_{\phi \in \mathrm{supp}(\Phi)} \Phi(\phi) \cdot \phi(x) \right). $$

It is presented by the theory of convex algebras which contains a binary operation $+_p$ for every $p \in (0, 1)$ satisfying idempotence $(x+_p x = x)$, skew commutativity $(x+_p y = y+_1 p x)$ and skew associativity $((x+_q y) +_p z = x+_p(y+_{\frac{p(1-q)}{1-pq}} z))$. Here is the algebraic presentation of $\mathcal{D}^s$.

**Theorem 5.3** Let $\Sigma_D^s = \{a: 1,+_p: 2 \mid p \in (0,1)\}$ and $E_D^s$ contain

$$ \begin{aligned} aax &= ax \\ a(x+_p y) &= x+_p y \\ ax+_p ay &= x+_p y \\ x+_p x &= ax \\ x+_p y &= y+_1 p x \\ (x+_q y) +_p z &= x+_p(y+_{\frac{p(1-q)}{1-pq}} z), \end{aligned} $$

then $\mathbf{A}(\Sigma_D^s, E_D^s) \cong \mathrm{EM}_s(\mathcal{D})$

**Proof.** In this proof, we will have to distinguish probability distributions seen in $\mathcal{D}(X)$ and those seen in a $(\Sigma_D^s, E_D^s)$-algebra. In the former, we will write $px+\bar{p}y$ ($\bar{p} := 1-p$) in the binary case and $\sum_{i=1}^n p_i x_i$ in general. In the latter, we will write $x+_p y$ in the binary case and $+_1 p_i x_i$ in general. Note that $+_p$ is well-defined by skew associativity of $+_p$ (assuming all $x_i$s are distinct).

The proof follows the sketch of the last two (all details are in the appendix). A $\mathcal{D}$-semialgebra $a: \mathcal{D}X \to X$ is sent to $(X, a: 0,+_p: 2)$ where $a := a(1-)$ and $+_p := a(p - \bar{p}-)$. A $(\Sigma_D^s, E_D^s)$-algebra $(X, a: 0,+_p: 2)$ is sent to $a: \mathcal{D}X \to X = \sum_{i=1}^n p_i x_i \mapsto+_1 p_i ax_i$. Analogously to the proof for the semigroup monad, a step in the proof uses the fact that the equations in $E_D^s$ imply

$$ \forall n \geq 2, \quad a \left( \mathbf{1}_{i=1}^n p_i x_i \right) = \mathbf{1}_{i=1}^n p_i x_i = \mathbf{1}_{i=1}^n p_i ax_i. $$

□

These three examples show a clear link between the presentation of a monad on **Set** and of its semifree monad. They all fit in the following conjecture.
**Conjecture 5.4** Let $(M, \eta, \mu)$ be a monad on Set with an algebraic presentation $(\Sigma_M, E_M)$, then $(M^s, \eta^s, \mu^s)$ is presented by the signature $\Sigma_M \cup \{a : 1\}$ with the equations

$$ \begin{array}{l} aax = ax \\ \forall \mathrm{op} : n \in \Sigma_M, \mathrm{a}(\mathrm{op}(x_1, \dots, x_n)) = \mathrm{op}(x_1, \dots, x_n) = \mathrm{op}(ax_1, \dots, ax_n) \\ \forall t(x_1, \dots, x_n) = s(x_1, \dots, x_n) \in E_M, t(ax_1, \dots, ax_n) = s(ax_1, \dots, ax_n). \end{array} $$

# 6 Directions for Future Work

In this paper we proved that semialgebras for a monad $M$ on a category with coproducts are in fact algebras for the semifree monad $M^s$ with underlying functor $\mathrm{id} + M$. We also showed that weak distributive laws $MT \Rightarrow TM$ correspond to certain strong distributive laws $M^s T \Rightarrow TM^s$.

Starting with a weak distributive law $\lambda : MT \Rightarrow TM$, we now have two ways to obtain a weak composite of $T$ and $M$. If idempotents split in the base category, Garner's method [8] yields a weak lifting $\hat{T}$ of $T$ to $\mathrm{EM}(M)$ and hence a monad structure on the functor $U^M \circ \hat{T} \circ F^M$, where $F^M$ is the free $M$-algebra functor sending $X$ to $(MX, \mu_X^M)$. If all coproducts exist in the base category, our method also yields a lifting $\tilde{T}^s$ of $T$ on $\mathrm{EM}(M^s)$ and hence a monad structure on the functor $U^{M^s} \circ \tilde{T}^s \circ F^{M^s}$.

In general these composite monads are not the same, for example, for the weak distributive law of [9] we obtain on one hand the monad $\mathcal{P}_c\mathcal{D}$ of convex powersets of distributions, and on the other, a monad $\mathcal{P}(\mathrm{id} + \mathcal{D})$. Understanding how these composite monads relate directly and how the second one can be used for the semantics of computational effects is left for future investigations.

The adjunctions between $\mathrm{EM}_s(M)$ and $\mathrm{EM}(M)$ described in [8, Lemma 12] can now be seen as adjunctions between $\mathrm{EM}(M)$ and $\mathrm{EM}(M^s)$ as drawn below.

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

One can show that $I$ is the functor induced by the monad map $[\eta^M, \mathrm{id}_M] : M^s \Rightarrow M$, and hence that $I \circ U^M = U^{M^s}$. Also, while this only implies $K \circ F^{M^s}$ and $F^M$ are isomorphic, since both are left adjoints to $U^M$, one can also prove they are equal. However, the other triangles do not necessarily commute.

Another direction for future research is Conjecture 5.4. If it is resolved positively or if another general algebraic presentation for semialgebras is discovered, we may be able to use Theorem 4.3 in conjunction with the very general results of [23] to obtain no-go theorems for weak distributive laws.

# References

[1] Steve Awodey. Category Theory. Oxford University Press, 2010.

[2] Andrej Bauer. What is algebraic about algebraic effects and handlers?, 2019.

[3] Jon Beck. Distributive laws. In B. Eckmann, editor, Seminar on Triples and Categorical Homology Theory, pages 119–140, Berlin, Heidelberg, 1969. Springer Berlin Heidelberg.

[4] Gabriella Böhm, Stephen Lack, and Ross Street. On the 2-categories of weak distributive laws. Communications in Algebra, 39(12):4567–4583, 2011.

[5] F. Bonchi, A. Sokolova, and V. Vignudelli. The theory of traces for systems with nondeterminism and probability. In 2019 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pages 1–14, 2019.

[6] Filippo Bonchi and Alessio Santamaria. Combining semilattices and semimodules. In FoSSaCS, volume 12650 of Lecture Notes in Computer Science, pages 102–123. Springer, 2021.

[7] Filippo Bonchi, Alexandra Silva, and Ana Sokolova. The Power of Convex Algebras. In Roland Meyer and Uwe Nestmann, editors, 28th International Conference on Concurrency Theory (CONCUR 2017), volume 85 of Leibniz International Proceedings in Informatics (LIPIcs), pages 23:1–23:18, Dagstuhl, Germany, 2017. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.
[8] Richard Garner. The Vietoris monad and weak distributive laws. *Applied Categorical Structures*, 28(2):339–354, 4 2020.

[9] Alexandre Goy and Daniela 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, New York, NY, USA, 2020. Association for Computing Machinery.

[10] Alexandre Goy, Daniela Petrişan, and Marc 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.

[11] Martin Hyland and Christine Tasson. The linear-non-linear substitution 2-monad. In *ACT*, volume 333 of *EPTCS*, pages 215–229, 2020.

[12] Klaus Keimel and Gordon D. Plotkin. Mixed powerdomains for probability and nondeterminism. *Logical Methods in Computer Science*, Volume 13, Issue 1, January 2017.

[13] G.M. Kelly. A unified treatment of transfinite constructions for free algebras, free monoids, colimits, associated sheaves, and so on. *Bulletin of the Australian Mathematical Society*, 22(1):1–83, 1980.

[14] Bartek Klin and Julian Salamanca. Iterated covariant powerset is not a monad. *Electronic Notes in Theoretical Computer Science*, 341:261–276, 2018. Proceedings of the Thirty-Fourth Conference on the Mathematical Foundations of Programming Semantics (MFPS XXXIV).

[15] S. MacLane. *Categories for the working mathematician*. Springer-Verlag, 1971.

[16] Matteo Mio, Ralph Sarkis, and Valeria Vignudelli. Combining nondeterminism, probability, and termination: equational and metric reasoning. In *LICS*, 2021.

[17] Michael Mislove. Nondeterminism and probabilistic choice: Obeying the laws. In *Catuscia Palamidessi*, editor, *CONCUR 2000 — Concurrency Theory*, pages 350–365, Berlin, Heidelberg, 2000. Springer Berlin Heidelberg.

[18] Emily Riehl. *Category Theory in Context*. Dover Publications, 2017.

[19] Ross Street. Weak distributive laws. *Theory and Applications of Categories [electronic only]*, 22:313–320, 2009.

[20] Miki Tanaka. *Pseudo-distributive laws and a unified framework for variable binding*. PhD thesis, Laboratory for the Foundations of Computer Science, School of Informatics, University of Edinburgh, 2004.

[21] Daniele Varacca. *Probability, nondeterminism and concurrency: two denotational models for probabilistic computation*. BRICS, 2003.

[22] Daniele Varacca and Glynn Winskel. Distributing probability over non-determinism. *Mathematical Structures in Computer Science*, 16(1):87–113, 2006.

[23] Maaike Zwart and Dan Marsden. No-go theorems for distributive laws. In *34th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2019, Vancouver, BC, Canada, June 24-27, 2019*, pages 1–13. IEEE, 2019.
First, naturality follows from the following diagram where (a) commutes by naturality of $\eta^M$ and (b) commutes because $TMf$ is the image of $Mf:MX \to MY$ which is a homomorphism between $\mu_X^M$ and $\mu_Y^M$ by naturality of $\mu^M$.

$$ \begin{array}{ccc} MTX & \xrightarrow{MT\eta_X^M} & MTMX \xrightarrow{\tilde{T}\mu_X^M} TMX \\ \multicolumn{1}{c}{MTf} & \Big|_{(a)} & \multicolumn{1}{c}{MT^T Mf} \Big|_{(b)} \xrightarrow{\Big|_{TMf}} \\ MTY & \xrightarrow{MT\eta_Y^M} & MTMY \xrightarrow{\tilde{T}\mu_Y^M} TMY \end{array} \qquad (27) $$

Next, we show that the instances of (7), (8) and (9) for $\lambda$ commute by paving the following diagrams.

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

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

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

(a) Naturality of $\eta^M$ and $\eta^T$.

(b) By left of (1).

(c) By hypothesis, $\tilde{\eta}_{(MX,\mu_X^M)} = \eta_{MX}^T$ is a homomorphism.

(d) Apply $MT$ to right of (1).

(e) Apply $\tilde{T}$ to $\mu_X^M$ as a homomorphism $(MMX, \mu_{MX}^M) \to (MX, \mu_X^M)$ in $EM_s(M)$.

(f) Naturality of $\mu^M$ and $\eta^M$.

(g) Associativity of $\tilde{T}\mu_X^M$.

(h) Naturality of $\eta^M$.

(i) Apply $\tilde{T}$ to $MT\eta_X^M$ as a homomorphism $(MTX, \mu_{TX}^M) \to (MTMX, \mu_{TMX}^M)$ in $EM_s(M)$.

(j) Apply $\tilde{T}$ to $\tilde{T}\mu_X^M$ as a homomorphism $(MTMX, \mu_{TMX}^M) \to (TMX, \tilde{T}\mu_X^M)$ in $EM_s(M)$.

(k) Naturality of $\mu^T$ and $\eta^M$.

(l) By (20).

(m) By hypothesis, $\tilde{\mu}_{(MX,\mu_X^M)} = \mu_{MX}^T$ is a homomorphism.

We conclude that $\lambda$ is a weak distributive law.

Finally, we are left to show that the operations we described are inverses. Starting with $\lambda$, we obtain a
lifting $\tilde{T}$ sending $\mu_X^M$ to $T\mu_X^M \circ \lambda_{MX}$ which is sent to $\lambda'$ whose component at $X$ is

$$ \lambda'_{X} = T\mu_{X}^{M} \circ \lambda_{MX} \circ MT\eta_{X}^{M} = T\mu_{X}^{M} \circ TM\eta_{X}^{M} \circ \lambda_{X} = \lambda_{X}. $$

Starting with $\tilde{T}$, we obtain a weak distributive law $\lambda$ whose component at $X$ is $\tilde{T}\mu_X^M \circ MT\eta_X^M$ which is sent to $\tilde{T}'$ which sends an $M$-semialgebra $x : MX \to X$ to

$$ \begin{aligned} \tilde{T}'x &= Tx \circ \lambda_X \\ &= Tx \circ \tilde{T}\mu_X^M \circ MT\eta_X^M \\ &= \tilde{T}x \circ MTx \circ MT\eta_X^M \quad \text{Apply } \tilde{T} \text{ to } x \text{ as a homomorphism } (MX, \mu_X^M) \to (X, x). \\ &= \tilde{T}x. \quad \tilde{T} \text{ satisfies (20)} \end{aligned} $$

The theorem follows.

□

## 7.2 Proofs for Section 5

**Proof of Theorem 5.2** Given a $(-)^{+}$-semialgebra $a : X^{+} \to X$, we define $a := a[-] : X \to X$ and $- \cdot - := a[-, -] : X \times X \to X$. Let us verify each of the equations in $E_+^s$ hold.

$$ \begin{align*} a(x \cdot y) &= a[a[x, y]] & (x \cdot y) \cdot z &= a[a[x, y], z] \\ &= (a \circ a^+)[[x, y]] & &= a[a[a[x, y]], a[z]] \\ &= (a \circ \mu_X)[[x, y]] & &= a[a[x, y], a[z]] \\ &= a[x, y] &= x \cdot y & &= (a \circ a^+)[[x, y], [z]] \\ &= (a \circ \mu_X)[[x, y], [z]] & &= \therefore \text{ symmetric argument} \\ aax &= a[ax] & &= a[x, y, z] \\ &= a[a[x]] & &= a \circ a^+)[[x]] & &= a[x, a[y, z]] = x \cdot (y \cdot z). \\ &= (a \circ a^+)[[x]] & &= (a \circ a^+)[[x], [y]] \\ &= (a \circ \mu_X)[[x]] & &= (a \circ \mu_X)[[x], [y]] \\ &= a[x] & &= a[x, y] = x \cdot y \\ &= ax & &= \end{align*} $$

Conversely, given $a : X \to X$ and $\cdot : X \times X \to X$ satisfying the equations in $E_+^s$, we define $a : X^{+} \to X$ by $[x_1, \dots, x_n] \mapsto ax_1 \cdots ax_n$ which is well-defined by associativity. We need to generalize the equation $ax \cdot ay = x \cdot y = a(x \cdot y)$ to longer strings of $\cdot$, namely, we claim that $ax_1 \cdots ax_n = x_1 \cdots x_n = a(x_1 \cdots x_n)$. We proceed by induction starting with $n=2$ which is true by hypothesis. If it holds for $n-1$, then

$$ \begin{align*} ax_1 \cdots ax_n &= (ax_1 \cdots ax_{n-1}) \cdot ax_n \\ &= (x_1 \cdots x_{n-1}) \cdot ax_n \\ &= a(x_1 \cdots x_{n-1}) \cdot aax_n \\ &= a(x_1 \cdots x_{n-1}) \cdot ax_n = a(x_1 \cdots x_n) \\ &= (x_1 \cdots x_{n-1}) \cdot x_n \\ &= x_1 \cdots x_n. \end{align*} $$

In the following derivation which shows $a$ is a $(-)^{+}$-semialgebra, we need a slightly weaker version that holds even for $n=1$: $a(ax_1 \cdots ax_n) = ax_1 \cdots ax_n$. For any $L = [[x_{1,1}, \dots, x_{n_1,1}], \dots, [x_{k,1}, \dots, x_{n_k,1}]] \in (X^+)^+$,

$$ \begin{align*} a(a^+(L)) &= a[ax_{1,1} \cdots ax_{n_1,1}, \dots, ax_{k,1} \cdots ax_{n_k,1}] \\ &= a(ax_{1,1} \cdots ax_{n_1,1}) \cdots a(ax_{k,1} \cdots ax_{n_k,1}) \\ &= ax_{1,1} \cdots ax_{n_1,1} \cdots ax_{k,1} \cdots ax_{n_k,1} \\ &= a[x_{1,1}, \dots, x_{n_1,1}, x_{2,1}, \dots, x_{n_{k-1},k-1}, x_{k,1}, \dots, x_{n_k,1}] \\ &= a(\mu_X(L)). \end{align*} $$

Let us show these operations are inverses. If $a$ and $\cdot$ are obtained from $a : X^{+} \to X$, then we proceed by induction to show that $a[x_1, \dots, x_n] = ax_1 \cdots ax_n$. For $n=1$, it is clear. For $n=2$, we have $a[x_1, x_2] =$
$a[a[x_1], a[x_2]] = ax_1 \cdot ax_2$. Suppose it holds for $n-1$, then

$$
\begin{align*}
a[x_1, \dots, x_n] &= (a \circ \mu_X)[[x_1, \dots, x_{n-1}], [x_n]] \\
&= a[a[x_1, \dots, x_{n-1}], a[x_n]] \\
&= a[ax_1 \cdots ax_{n-1}, ax_n] \\
&= a(ax_1 \cdots ax_{n-1}) \cdot aax_n \\
&= ax_1 \cdots ax_n.
\end{align*}
$$

We conclude that the semialgebra obtained from **a** and $\cdot$ is **a**. In the other direction, let **a** be obtained from **a** and $\cdot$. We have $a[x, y] = \mathbf{a}x \cdot \mathbf{a}y = x \cdot y$ and $a[x] = \mathbf{a}x$ showing that the operations obtained from **a** are **a** and $\cdot$.

Finally, we check that these operations are functorial. Suppose $f: X \to Y$ is a homomorphism between $a$ and $b$, then

$$
\begin{align*}
f(\mathbf{a}(x)) &= f(a[x]) = b[f(x)] = \mathbf{b}f(x) \\
f(x \cdot^a y) &= f(a[x, y]) = b[f(x), f(y)] = f(x) \cdot^b f(y).
\end{align*}
$$

Conversely, if $f \circ a = b \circ f$ and $f \circ a^b = f \circ (f \times f)$, then

$$
f(a[x_1, \dots, x_n]) = f(ax_1 \cdot^a a \cdot^a a x_n) = \mathbf{b}f(x_1) \cdot^b \mathbf{b} \cdot^b \mathbf{b}f(x_n) = b[f(x_1), \dots, f(x_n)].
$$

□

**Proof of Theorem 5.3** Given a $\mathcal{D}$-semialgebra $a : \mathcal{D}X \to X$, we define $x +_p y := a(px + \bar{p}y)$ and $\mathbf{a}x = a(1x)$. Let us verify each equation in $E_{\mathcal{D}}^s$ holds.

$$
\begin{align*}
\mathbf{a}(x +_p y) &= a(1a(px + \bar{p}y)) & (x +_q y) +_p z &= a(p(x +_q y) + \bar{p}z) \\
&= (a \circ \mathcal{D}a)(1(px + \bar{p}y)) & &= a(pa(qx + \bar{q}y)) + \bar{p}z) \\
&= (a \circ \mu_X)(1(px + \bar{p}y)) & &= a(pa(1a(qx + \bar{q}y)) + \bar{p}a(1z)) \\
&= a(px + \bar{p}y) & &= a(pa(qx + \bar{q}y) + \bar{p}a(1z)) \\
&= x +_p y & &= (a \circ \mathcal{D}a)(p(qx + \bar{q}y) + \bar{p}(1z)) \\
&= (a \circ \mu_X)(p(qx + \bar{q}y) + \bar{p}(1z)) \\
&= a(pqx + \bar{p}qy + \bar{p}z) \\
&= \therefore \text{ symmetric argument} \\
x +_p x &= a(px + \bar{p}x) & \mathbf{a}x +_p \mathbf{a}y &= a(pax + \bar{p}ay) \\
&= a(1x) = \mathbf{a}x & &= a(pa(1x) + \bar{p}a(1y)) \\
&= (a \circ \mathcal{D}a)(p(1x) + \bar{p}(1y)) & &= (a \circ \mu_X)(p(1x) + \bar{p}(1y)) \\
x +_p y &= a(px + \bar{p}y) & &= (a \circ \mu_X)(p(1x) + \bar{p}(1y)) \\
&= a(\bar{p}y + px) & &= a(px + \bar{p}y) \\
&= y +_{1-p} x & &= x +_p y
\end{align*}
$$

Conversely, given $+_p$ and **a** satisfying $E_D^s$, we define $a : \mathcal{D}X \to X$ by $a(\sum_{i=1}^n p_i x_i) = +_{i=1}^n p_i \mathbf{a}x_i$. We need to generalize the equation $\mathbf{a}(x+_p y) = x+_p y = \mathbf{a}x+_p \mathbf{a}y$ to distributions with larger support, namely, we claim that $\mathbf{a}(+_i^n p_i x_i) =+_i^n p_i x_i =+_i^n p_i \mathbf{a}x_i$. We proceed by induction starting with $n=2$ which is true by hypothesis. Suppose it holds for $n-1$, and let $p'_i$ for $1 \le i \le n$ be such that $+_i^n p_i x_i =+_i^{n-1} p'_i x_i + p'_n x_n$,
then

$$
\begin{align*}
\sum_{i=1}^{n} p_i a x_i &= \sum_{i=1}^{n-1} p'_i a x_i + p'_n a x_n \\
&= \sum_{i=1}^{n-1} p'_i x_i + p'_n a x_n \\
&= a \left( \sum_{i=1}^{n-1} p'_i x_i \right) + p'_n a a x_n \\
&= a \left( \sum_{i=1}^{n-1} p'_i x_i \right) + p'_n a x_n = a \left( \sum_{i=1}^{n-1} p'_i x_i + p'_n x_n \right) = a \left( \sum_{i=1}^{n} p_i x_i \right) \\
&= \left( \sum_{i=1}^{n-1} p'_i x_i \right) + p'_n x_n \\
&= \sum_{i=1}^{n} p_i x_i.
\end{align*}
$$

In the following derivation which shows that $a$ is a $\mathcal{D}$-semialgebra, we need a slightly weaker version that holds even for $n = 1$: $a(+_{i=1}^n p_i a x_i) = +_{i=1}^n p_i a x_i$. For any $\Phi = \sum_{i=1}^n p_i (\sum_{j=1}^{m_i} q_{i,j} x_{i,j})$, $^6$

$$
\begin{align*}
a(Da(\Phi)) &= a \left( \sum_{i=1}^{n} p_i \binom{m_i}{j=1} q_{i,j} a x_{i,j} \right) \\
&= \sum_{i=1}^{n} p_i a \binom{m_i}{j=1} q_{i,j} a x_{i,j} \\
&= \sum_{i=1}^{n} p_i \binom{m_i}{j=1} q_{i,j} a x_{i,j} \\
&= \sum_{i=1}^{n} \sum_{j=1}^{m_i} p_i q_{i,j} x_{i,j} \\
&= a \left( \sum_{i=1}^{n} \sum_{j=1}^{m_i} p_i q_{i,j} x_{i,j} \right) \\
&= a(\mu_X(\Phi)).
\end{align*}
$$

Let us show that these operations are inverses. If $\mathbf{a}$ and $+_{\mathbf{p}}$ are obtained from $\mathbf{a} : \mathcal{D}\mathbf{X} \to \mathbf{X}$, then we proceed by induction to show that $\mathbf{a}(\sum_{i=1}^n p_i x_i) = +_{i=1}^n p_i \mathbf{a} x_i$. For $n=1$ it is clear. For $n=2$, we have

<footnote>$^6$ In this derivation, we cannot assume that all the $x_{i,j}$s are distinct, so skew associativity is not enough to say that $+_{i=1}^n$ is well-defined. However, we may use skew commutativity and idempotence as well because $\mathbf{a}$ is applied to every term of the sum and idempotence holds when this is the case.</footnote>
$a(px + \bar{p}y) = a(pa(1x) + \bar{p}a(1y)) = ax +_p ay$. Suppose it holds for $n-1$, then

$$
\begin{align*}
a \left( \sum_{i=1}^{n} p_i x_i \right) &= (a \circ \mu_X) \left( p'_n \left( \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} x_i \right) + \bar{p}'_n (1x_n) \right) \\
&= (a \circ \mathcal{D}a) \left( p'_n \left( \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} x_i \right) + \bar{p}'_n (1x_n) \right) \\
&= a \left( p'_n a \left( \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} x_i \right) + \bar{p}'_n a (1x_n) \right) \\
&= a \left( p'_n \left( \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_i \right) + \bar{p}'_n ax_n \right) \\
&= a \left( \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_i \right) + p'_n ax_n \\
&= \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_i + p'_n ax_n \\
&= \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_i + p'_n ax_n \\
&= \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_i + \sum_{i=1}^{n-1} \frac{p'_i}{p'_n} ax_n
\end{align*}
$$

We conclude that the semialgebra obtained from **a** and $+_p$ is **a**.

In the other direction, let $a$ be obtained from **a** and $+_p$. We have $a(px + \bar{p}y) = ax +_p ay = x +_p y$ and $a(1x) = ax$ showing that the operations obtained from $a$ are **a** and $+_p$.

Finally, we check that these operations are functorial. Suppose $f: X \to Y$ is a homomorphism between $a$ and $b$, then

$$
\begin{align*}
f(\mathbf{a}x) &= f(a(1x)) = b(1f(x)) = \mathbf{b}f(x) \\
f(x +_p^a y) &= f(a(px + \bar{p}y)) = b Hab(x) + \bar{p}f(y) = f(x) +_p^b f(y).
\end{align*}
$$

Conversely, if $f \circ a = b \circ f$ and $f \circ +_p^a = +_p^b \circ (f \times f)$, then

$$
f(a(\sum_{i=1}^{n} p_i x_i)) = f\left(\binom{n}{1} p_i a x_i\right) = \binom{n}{1} p_i f(a x_i) = \binom{n}{1} p_i \mathbf{b} f(x_i) = b(\sum_{i=1}^{n} p_i f(x_i)).
$$

□