A personal blog about computer science topics.

A Monoid in the Category of Endofunctors
Posted on Jul 25 2023 ~ 6 min read
#category theory  #abstract algebra  #monads 

Functor Functor Applicative Applicative Functor->Applicative Traversable Traversable Functor->Traversable Applicative->Traversable Alternative Alternative Applicative->Alternative Monad Monad Applicative->Monad Apply Apply Apply->Applicative Semigroup Semigroup Semigroup->Apply Monoid Monoid Semigroup->Monoid MonadPlus MonadPlus Monad->MonadPlus MonadFix MonadFix Monad->MonadFix ArrowApply ArrowApply Monad->ArrowApply Monoid->Applicative Monoid->Alternative Monoid->Monad Monoid->MonadPlus Category Category Monoid->Category ArrowPlus ArrowPlus Monoid->ArrowPlus Foldable Foldable Monoid->Foldable Arrow Arrow Category->Arrow Foldable->Traversable Arrow->ArrowApply ArrowChoice ArrowChoice Arrow->ArrowChoice ArrowZero ArrowZero Arrow->ArrowZero ArrowZero->ArrowPlus

A Monad is a triple ( T , η , μ ) (T, \eta, \mu) where:

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

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

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

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

  • μ A T ( μ A ) = μ A μ T ( A ) \mu_A \circ T(\mu_A) = \mu_A \circ \mu_{T(A)} (associativity)
  • μ A T ( η A ) = μ A η T ( A ) = i d T ( A ) \mu_A \circ T(\eta_A) = \mu_A \circ \eta_{T(A)} = id_{T(A)} (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 A A of C \mathcal{C} , the unit is a morphism η A : A T A \eta_{A} : A \rightarrow T A , and the multiplication is a morphism μ A : T ( T A ) T A \mu_{A} : T(T A) \rightarrow T A , such that the following diagrams commute:

\begin{xy} \xymatrix{ T(T(TA)) \ar[d]_{\mu TA} \ar[r]^{T\mu{(A)}} & T(TA) \ar[d]^{\mu{A}} \\ T(TA) \ar[r]_{\mu{A}} & TA } \end{xy}
\begin{xy} \xymatrix{ TA \ar[d]_{\eta TA} \ar[r]^{T\eta{(A)}} \ar@{=}[dr] & T(TA) \ar[d]^{\mu{A}} \\ T(TA) \ar[r]_{\mu{A}} & TA } \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 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).


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.

Haskell Definition of Monad (Interface)

class Monad m where
  --   ηx : A -> T A (unit)
  return :: a -> m a

  --   μx : T (T A) -> T A (multiplication)
  join   :: m (m a) -> m a

These have to obey the Monad laws:

join . join == join . fmap join           -- associativity
join . return == id == join . fmap return -- left and right identiy

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.

class Monad m where
  return :: a -> m a
   (>>=) :: m a -> (-> m b) -> m b

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

>>= f = join (fmap f a)

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:

join a = a >>= 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).

An Instance of Monad, the List Monad

instance Monad [] where
  return :: a -> [a]
  return x = [x]

  (>>=) :: [a] -> (-> [b]) -> [b]
  xs >>= f = concat (map f xs)

Another Instance, the Maybe Monad

instance Monad Maybe where
  return :: a -> Maybe a
  return x  = Just x

  (>>=) :: Maybe a -> (-> Maybe b) -> Maybe b
  (>>=) m g = case m of
                 Nothing -> Nothing
                 Just x  -> g x

All of the above is already implemented in the standard Haskell library, so you can simply open an interactive Haskell interpreter (ghci) and test the following examples.

ghci> [1,2,3] >>= \-> [x, x*2]

ghci> Just 3 >>= \-> Just (x*2)
Just 6

-- And heres how to use IO
ghci> getLine >>= \line -> putStrLn ("You said: " ++ line ++ "!")
You said: Hi!


  1. 0.The diagram displayed at the top of this post is a modified version of Brent Yorgey's Typeclassopedia diagram
  2. 1.Monad in ncatlab
  3. 2.Notes on Category Theory by Paolo Perrone
  4. 3.Category theory/Monads