Monoid in the Category of Endofunctors

Published in

SoftwareMill Tech Blog

8 min readDec 3, 2019

Today we are going to deep dive into the Category theory again to find out what the famous sentence, being the title of this blog posts, means.

The sentence originally appeared in the book “Categories for the Working Mathematician” by Sounders Mac Lane and it looks like this:

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

To understand the quote fully we would need to touch on Monoids, Monoidal Categories, Applicatives, Endofunctors and more. Hopefully, at the end of this post this sentence will no longer be a bunch of magical words glued up together.

Monoid

Let’s start with the Monoid. To make things simple I’ll try to use Scala as the language for the snippets wherever possible.

trait Monoid[A] { 
  // an identity element 
  def id: A 
  // an associative operation 
  def op(x: A, y: A): A 
}

A Monoid is any type that has two functions: an operation taking two arguments of a type and returning a value of that type, and that also has a function which given a value returns the value of the same type without changing anything — the identity operation.

In Cats, you may be familiar with Semigroup which has a method combine:

trait Semigroup[A] { 
  def combine(x: A, y: A): A 
}

and Monoid is basically a Semigroup with additional method empty — our identity function.

trait Monoid[A] extends Semigroup[A] {   
  def empty: A 
}

Please note that we need to follow the Category Theory rules here so the combine operation has to be associative and empty value should be an identity for our combine operation:

combine(x, empty) = combine(empty, x) = x

Basically if something is a Monoid we know we can combine it together to form bigger Monoids or write more generalized functions which will take something which can be composable instead of some concrete types.

Ok, so we know what a Monoid is and, simplifying things a bit, we can say that a Monoid is a set of objects and a method of combining them. The simplest examples would be:

a String where the identity function return an empty String (“”) and our combine function would concat the two instances into one
an Int where the combine function would be + and identity would be 0
a List where the identity function would be List.empty or Nil and the combine function would concat two lists together (++)

and so on.

For examples on this, I encourage you to see the Cats Monoid documentation and great Monoid discussion on Reddit.

From Category Theory point of view, Monoid is the simplest Category of one object with a structure. In other words it’s a Category with one object and an (endo-)functor going from that single object back to itself.

From Wikipedia:

In category theory, a monoid (or monoid object) (M, μ, η) in a monoidal category (C, ⊗, I) is an object M together with two morphisms
μ: M ⊗ M → M called multiplication,
η: I → M called unit

So, this is actually our def combine(x: A, y: A): A with def empty: A from the previous examples.

Monoidal Category

To explain what a Monad is, it’s usefull to know what a Monoidal Category is. If you look into Wikipedia definition for Monoid, you will see a strange (⊗) symbol called ‘multiplication’. The Monoidal Category is a Category in which you can “multiply” objects using some kind of a tensor product (⊗) and which also has a special object Ithat is the unit of multiplication.

In Monoidal Category, for any objects a and b there is a mapping a ⊗ b and this mapping is functorial in both arguments, which means that you can also “multiply” morphisms.

In other words, Monoidal Category is like our Monoid but applied to a Category itself.

Example of a Monoidal Category is a Category of Sets, Set is Monoidal Category with cartesian product x serving as a tensor product, and the singleton set 1 as the unit.

In a Set Category, the objects are Sets, morphisms are functions and where any particular one-element set serves as the unit.

So, similary to Monoid, Monoidal Category can be defined with:

•: S × S → S
e : 1 → S

where:

(a • b) • c = a • (b • c), for all a, b and c in S
e • a = a • e = a, for all a in S

Functors in Monoidal Category

If you follow along with me on a journey to better understand the Functional Programming concepts you may be already familiar with the idea of a Functor (if not you can read about it here). Once again, Functor is a mapping of objects and morphisms from one Category to another, that preserves composition and identity.

With our Monoidal Category example, we can imagine that we have a bunch of Functors mapping objects from Category C to Category of Sets. Our Functors would also form a Category, this category will consist of Functors as objects and morphisms between any two functors as natural transformations.

With our [C, Set] Functors Category our Functor should map the tensor product in C to the cartesian product in Set and also the unit I from C to the singleton set 1.

If we take Functors which preserve monoidal structure when mapping C to Set and we care only about one way transformation (from C to Set and not the opposite) we will end up with something called Lax Monoidal Functor — known as Applicative Functor.

https://bartoszmilewski.com/2018/05/16/free-monoidal-functors-categorically/

In Cats, our Lax Monoidal Functor looks like the following (example formulation via product)

trait Applicative[F[_]] extends Functor[F] { 
  def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] 
  def pure[A](a: A): F[A] 
}

As you can see, the above definition is like 1 to 1 equivalent of what we get with Category Theory natural transformation definitions for Lax Monoidal Functor.

Note on Endofunctors

We have talked about Category of Functors and we know what is Monoidal Category. Now, you may ask what an Endofunctor is? Endofunctor is a mapping of objects and morphisms from one Category back to the same Category. Actually, all the Functors we are dealing with in functional programming are Endofunctors, this is because we are dealing with only one Category — Category of types.

Monad

If you have used Cats a bit, you may be aware at this point that Monad in Cats extends Applicative — in other words we are really close :) but we will get back to it later.

From Category Theory point of view Monad is an Endofunctor equipped with two natural transformations.

Functor T : X → X and:

natural transformation: μ : T × T → T
natural transformation: η : I → T

where × means functor composition andI is the identity endofunctor on X.

Our μ and η are equivalent to flatMap and unit in Scala Cats.

Monad is an Applicative so its also a Functor. The distinctive feature of a Monad over the simple Functor concept is that we can build new structures from the pieces of original structure without nesting. With simple Functor with a map (fmap) we would simply nest each Functor (F[F[A]]) whereas with Monad we can flatten the resulting structure so we won’t end up with a structure reflecting the whole flow used to build it.

Similarly to Functor, we can think of a Monad as a container but a container for “side effects”, this means that with a Monad the side effects can be grouped into one structure where the order of effects is maintained. We will also have a “do nothing” side effect where when grouped with another side effect will be the same as the single side effect. Our flatMap (or Haskell join) is a grouping operation, where two side effects are grouped into one. And that’s basically all there is to a Monad.

To get the feeling for the sentence/blog title we are trying to decipher let’s move back a bit to our Monoid example, a Monoid is an object eg. M with two morphisms (as described earlier):

μ: M ⊗ M → M (multiplication, product)
I → M (unit)

If we apply these laws to a Category of Endofunctors we will have product ⊗ replaced by composition of Endofunctors and unit being an identity Endofunctor.

Any Monad is by definition an Endofunctor, which also means it’s an object in the category of Endofunctors, where the monadic μ(flatMap) and η(unit) operators satisfy the definition of a Monoid in that particular Monoidal Category.

From the programming perspective Monoids are very good at combining things together. If you look into the examples with Ints, Strings, Lists etc. this becomes very clear. So with Monoid you can always compose two integers to get an integer but this does not always apply to functions, you cannot always compose two functions and get a function of the same type at the end (especially functions with higher kinded types). This is where Monad comes to the rescue.

In Cats, the Monad documentation states:

Monad extends the Applicative type class with a new function flatten. Flatten takes a value in a nested context (eg. F[F[A]] where F is the context) and “joins” the contexts together so that we have a single context (ie. F[A]).

So our definition of Monad in programming world would be:

def unit: A → F[A]
def map: F[A] → (A → B) → F[B]
def flatten: F[F[A]] → F[A]

In Scala the Monad definition could look like the following:

trait Monad[M[_]] {
  def unit[A](a: A): M[A]
  def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
}

So, like all Applicatives, we have a unit/pure function which takes a value and wraps it, as well as the map, which takes a function and applies it to an element returning a wrapped object. Now, in case of Monads, our special Functors, we have one additional method — flatten — which prevents us from nesting the side effects.

Summary

Simplifying the things greatly, we know that Functor is something that we can map with, we also know that in Functional Programming world we deal only with one Category, which is Category of Types and therefore we basically only deal with Endofunctors. Having a Category of Endofunctors we need to find a fixed Endofunctor which has some additional properties like the μ(flatMap) and η(unit) morphisms.

Monad will be an Endofunctor which is able to turn two Endofunctors into one with μ: F ⊗ F→ F eg: F[F[T]] into F[T] and wrap itself up into an Endofunctor context with I → M (unit). In other words we have a Monoid in a Category of Endofunctors.