A monad is a structure that describes generalized objects and morphisms.

The category $$[\cC, \cC]$$ of endofunctors is a strict monoidal category with the functor composition as the monoidal product and the identity functor $$\id_\cC$$ as the monoidal unit.

A monad in a category $$\cC$$ is an endofunctor $$T: \cC \to \cC$$ equipped with two natural transformations:

• composition $$\mu: TT \nat T$$
• unit $$\eta: \id_\cC \nat T$$

subject to

• associativity: $$\mu (T \mu) = \mu (\mu T)$$
• identity: $$\mu (\eta T) = \id_T = \mu (T \eta)$$

In other words, a monad is a monoid in the category of endofunctors.

-- bind
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(=<<) :: Monad m => (a -> m b) -> m a -> m b
(>>)  :: Monad m => m a -> m b -> m b
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

# 2 Algebra

## 2.1 F-algebra

For an endofunctor $$F: \cC \to \cC$$, an algebra over an endofunctor (F-algebra) $$(A, \act_A)$$ consists of an object $$A$$ (carrier) and a morphism $$\act_A: FA \to A$$.

An F-algebra homomorphism from $$(A, \act_A)$$ to $$(B, \act_B)$$ is a morphism $$f: A \to B$$ such that $$\act_B \compL Ff = f \compL \act_A$$.

For an endofunctor $$F: \cC \to \cC$$, a coalgebra over an endofunctor (F-coalgebra) $$(A, \act_A)$$ consists of an object $$A$$ (carrier) and a morphism $$\act_A: A \to FA$$.

An F-coalgebra homomorphism from $$(A, \act_A)$$ to $$(B, \act_B)$$ is a morphism $$f: A \to B$$ such that $$\act_B \compL f = Ff \compL \act_A$$.

### 2.1.1 Initial F-algebra

An initial F-algebra of an endofunctor $$F$$ is an initial object in the category of F-algebras.

If an endofunctor $$F$$ has an initial F-algebra $$(\mu F, i)$$, then $$F \mu F \iso \mu F$$.

1. $$(F \mu F, Fi)$$ is an F-algebra, so there exists a unique F-algebra homomorphism $$u: \mu F \to F \mu F$$.
2. $$i \compL u: \mu F \to \mu F$$ is an F-algebra homomorphism from the initial F-algebra and thus is unique, $$i \compL u = \id_{\mu F}$$.
3. $$u \compL i = Fi \compL Fu = F(i \compL u) = F \id_{\mu F} = \id_{F \mu F}$$.

In a category $$\cC$$ with a terminal object $$1$$, a natural numbers object (NNO) $$\N$$ is an initial F-algebra of the endofunctor $$X \mapsto 1 + X$$.

\begin{aligned} \begin{array}{rccccc} & 1 &+& \N &\to& \N \\ \zero: & * && &\mapsto& 0 \\ \successor: && & n &\mapsto& n+1 \end{array} \end{aligned}

In a category $$\cC$$ with a terminal object $$1$$ and binary products, an $$A$$-valued list object $$[A]$$ is an initial F-algebra of the endofunctor $$X \mapsto 1 + A \times X$$.

\begin{aligned} \begin{array}{rccccc} & 1 &+& A \times [A] &\to& [A] \\ \nil: & * && &\mapsto& [] \\ \cons: & && (x, xs) &\mapsto& x:xs \end{array} \end{aligned}

## 2.2 M-algebra

For a monoid object $$(M, \mu, \eta)$$ in a monoidal category $$(\cC, \otimes, I, \alpha, \lambda, \rho)$$, a (left) algebra over a monoid object (M-algebra) is an F-algebra $$(A, \act_A: M \otimes A \to A)$$ for the endofunctor

\begin{aligned} (M \otimes -): \cC &\to \cC \\ A &\mapsto M \otimes A \\ f &\mapsto \id_M \otimes f \end{aligned}

that is compatible with

• monoid product: $$\act \compL (\mu \otimes \id) = \act \compL (\id \otimes \act) \compL \alpha$$
• monoid unit: $$\act \compL (\eta \otimes \id) = \lambda$$

An M-algebra homomorphism is an F-algebra homomorphism.

## 2.3 T-algebra

For a monad $$(T, \mu, \eta)$$, a (left) algebra over a monad (T-algebra) is an M-algebra $$(A, \act_A: TA \to A)$$ in the category of endofunctors over the constant functor $$\Delta A$$.

Thus, a T-algebra is compatible with

• monad composition: $$\act_A \compL T \act_A = \act_A \compL \mu_A$$
• monad unit: $$\act_A \compL \eta_A = \id_A$$

A T-algebra homomorphism is an F-algebra homomorphism.

For a monad $$(T, \mu, \eta)$$ in a category $$\cC$$, the Eilenbergâ€“Moore category $$\cC^T$$ is a category of T-algebras and T-algebra homomorphisms.

# 3 Kleisli category

For a monad $$(T, \mu, \eta)$$ in a category $$\cC$$, the Kleisli category $$\cC_T$$ is a category whose

• objects are $$\cC$$-objects $$\Obj_{\cC_T} := \Obj_\cC$$
• morphisms are Kleisli morphisms $$\Hom_{\cC_T}(A, B) := \Hom_\cC(A, TB)$$
• composition is the Kleisli composition $$g_\Kl \compL_T f_\Kl := \mu_C \compL Tg_\Kl \compL f_\Kl$$
• identity morphism is the monad unit $$\id_A := \eta_A: A \to TA$$

$(F: \cC \toot \cD: G, \epsilon: FG \nat \id_\cD, \eta: \id_\cC \nat GF)$

$(GF: \cC \to \cC, G \epsilon F: GFGF \nat GF, \eta: \id_\cC \nat GF)$

$(FG: \cD \to \cD, F \eta G: FG \nat FGFG, \epsilon: FG \nat \id_\cD)$

# 5 Examples

## 5.1 Maybe

• $$MA = 1 + A$$ nothing or values
• $$Mf = 1 + f$$ computation with failure
• $$\mu: MM \nat M$$ failure propagation
• $$\eta: \id \nat M$$ just
• $$A \to MB$$ partial function
• $$MA \to A$$ pointed object

## 5.2 List

free monoid

• $$[]: 1 \to LA$$ empty list
• $$\concat: LA \times LA \to LA$$ concatenation

• $$LA$$ list
• $$Lf$$ list map
• $$\mu: LL \nat L$$ concatenation
• $$\eta: \id \nat L$$ singleton
• $$A \to LB$$ list function
• $$LA \to A$$ monoid $$(A, \fold [e: 1 \to A, \cdot: A \times A \to A])$$
• right identity $$[a]$$
• left identity $$[[], [a]]$$
• associativity $$[[a, b], [c]]$$

## 5.3 Powerset

• $$PA = 2^A$$ powerset
• $$Pf$$ set map
• $$\mu: PP \nat P$$ union
• $$\eta: \id \nat P$$ singleton
• $$A \to PB$$ set function
• $$PA \to A$$ suplattice

## 5.4 Multiset

• $$NA = \N^A$$ multiset
• $$Nf$$ sum map
• $$\mu: NN \nat N$$ multiplication
• $$\eta: \id \nat N$$ singleton
• $$A \to NB$$ multiset function
• $$NA \to A$$ commutative monoid

## 5.5 Probability

Giry monad $$\text{measurable space } (A, \Sigma_A) \mapsto (\set{\text{probability measure } \mu: \Sigma_A \to [0, 1]}, \set{\epsilon_U: \mu \mapsto \mu(U) \mid U \in \Sigma_A})$$

• $$PA$$ probability measures
• $$Pf$$ pushforward measure
• $$\mu: PP \nat P$$ marginalization
• $$\eta: \id \nat P$$ Dirac measure
• $$A \to PB$$ conditional probability
• $$PA \to A$$ expectation

## 5.6 State

• $$[S, S \times A]$$

## 5.7 Continuation

• $$[[A, R], R]$$

A monoidal monad is a monad in the 2-category of monoidal categories, lax monoidal functors, and monoidal natural transformations.

# 7 Monoidal Kleisli category

For a monoidal monad $$(T, \mu_T, \eta_T, \mu, \eta)$$ in $$(\cC, \otimes, I)$$, the Kleisli category $$\cC_T$$ inherits the monoidal structure from $$\cC$$, whose

• monoidal product $$\otimes_\Kl$$ on objects is the monoidal product $$\otimes$$ on $$\cC$$

• monoidal product $$\otimes_\Kl$$ on morphisms is obtained by $$f_\Kl \otimes_\Kl g_\Kl := \mu (f_\Kl \otimes g_\Kl)$$

$(A \xto{f_\Kl} TB) \otimes_\Kl (C \xto{g_\Kl} TD) = A \otimes C \xto{f_\Kl \otimes_\Kl g_\Kl} T(B\otimes D) = A \otimes C \xto{f_\Kl \otimes g_\Kl} TB \otimes TD \xto{\mu_{B, D}} T(B \otimes D)$

• monoidal unit, associator, and left/right unitors are those of $$\cC$$