# beuke.org

## A personal blog about computer science topics.

A Monoid in the Category of Endofunctors
Posted on Jul 25 2023 ~ 6 min read A Monad is a triple $(T, \eta, \mu)$ where:

• $T: \mathcal{C} \rightarrow \mathcal{C}$ is an endofunctor
• $\eta: 1_\mathcal{C} \rightarrow T$ is a natural transformation (the unit)
• $\mu: TT \rightarrow T$ is another natural transformation (the multiplication)

These must satisfy the following coherence conditions, known as the Monad laws:

• $\mu \circ T\mu = \mu \circ \mu T$ (associativity)
• $\mu \circ T\eta = \mu \circ \eta T = 1_T$ (left and right identity)

This means that for any object $X$ in $\mathcal{C}$, we have:

• $\mu_X \circ T(\mu_X) = \mu_X \circ \mu_{T(X)}$ (associativity)
• $\mu_X \circ T(\eta_X) = \mu_X \circ \eta_{T(X)} = id_{T(X)}$ (left and right unit laws)

We can rephrase these conditions using the subsequent commutative diagrams:

\begin{xy} \xymatrix{ TTT \ar[d]_{\mu T} \ar[r]^{T\mu} & TT \ar[d]^{\mu} \\ TT \ar[r]_{\mu} & T } \end{xy}
\begin{xy} \xymatrix{ T \ar[d]_{\eta T} \ar[r]^{T\eta} \ar@{=}[dr] & TT \ar[d]^{\mu} \\ TT \ar[r]_{\mu} & T } \end{xy}

We can also write down the natural transformations in terms of their components. For each object $X$ of $\mathcal{C}$, the unit is a morphism $\eta_{X} : X \rightarrow T X$, and the multiplication is a morphism $\mu_{X} : T(T X) \rightarrow T X$, such that the following diagrams commute:

\begin{xy} \xymatrix{ T(T(TX)) \ar[d]_{\mu TX} \ar[r]^{T\mu{(X)}} & T(TX) \ar[d]^{\mu{X}} \\ T(TX) \ar[r]_{\mu{X}} & TX } \end{xy}
\begin{xy} \xymatrix{ TX \ar[d]_{\eta TX} \ar[r]^{T\eta{(X)}} \ar@{=}[dr] & T(TX) \ar[d]^{\mu{X}} \\ T(TX) \ar[r]_{\mu{X}} & TX } \end{xy}

An application of this concept is that monads provide a way to express computations (in terms of morphisms) that include additional structure or side-effects (captured by the endofunctor $T$) in such a way that these computations can be chained together (via the $\mu$ natural transformation) and lifted over the monadic structure (via the $\eta$ natural transformation), and they do so in a way that is consistent (respecting the associativity and unit laws).

# Example

The Monad, by definition, requires us to implement two functions: the unit, which is called return in Haskell, where we just have to lift a value into the Monad (e.g., put a value into a list), and the multiplication join.

These have to obey the Monad laws:

We can now draw the commutative diagram for the Haskell definition of Monad:

\begin{xy} \xymatrix{ \text{m(m(m a))} \ar[d]_{\text{fmap join}} \ar[r]^{\text{join}} & \text{m(m a)} \ar[d]^{\text{join}} \\ \text{m(m a)} \ar[r]_{\text{join}} & \text{m a} } \end{xy}
\begin{xy} \xymatrix{ \text{m a} \ar[d]_{\text{fmap return}} \ar[r]^{\text{return}} \ar@{=}[dr] & \text{m(m a)} \ar[d]^{\text{join}} \\ \text{m(m a)} \ar[r]_{\text{join}} & \text{m a} } \end{xy}

The definition of a monad given here is equivalent to the one we typically use in Haskell.

We can easily define >>= with join and fmap.

This operation is called bind (or is sometimes refered to as flatMap). The bind function can be used if you need to operate on the lifted value before collapsing. We can also translate the other way around and define join in terms of >>= and id:

Hence join is bind applied to the identity function. These two constructions are reverse to each other and they translate the monad laws correctly. Now we lets have a look at some concrete examples (instances of Monad).