A Monad is just a Monoid in the Category of Endofunctors — Let’s actually unravel this.

Or: from Category Theory to Functional Programming (and back).

This infamous sentence is used a lot in articles about Monads and category theory. However most of them either end with “well it is a similar concept so it probably aligns, if you don’t look too closely” or they do not actually explain it at all apart from the catchphrase. And if they do actually attempt to, the perspective is either surely mathematical or completely from a programmers perspective. Let me (at least try to) finally link the two and give a hopefully understandable explanation that links and satisfies both math and programming. Code examples will be given in Scala (sorry Haskell lovers ❤️)

This article will try to lay the basics on category theory and functional programming. Explaining the underlying theoretical concepts and especially linking them to practical functional programming. I will try to put the emphasis on aligning math theory and programming, as I see this barely done in any article covering this topic. Usually the concepts are discussed surely from either perspective, making them seem to only roughly align. But before we jump into the topic, let me fist explain

Why you should care

Category theory is a rather abstract mathematical concept and admittingly you can be a pretty decent programmer without ever having heard of it. However, understanding this topic and it’s associated concepts, helps you to reason about your code in a better (more mathematical) manner and ultimately enables you write complex programs in a more structured way. In the end, good code is usually code with a good meta concept behind it. And in my humble opinion the infamous sentence in the title of this article is actually a pretty good mnemonic to connect the dots.

Ok, let’s get started! We will start with the basic concepts of category theory and applying them to functional programming. Then we will be making our way to Functors and Monads, giving the theoretical backgrounds as well as actual implementations in Scala, ending on the concepts of Monoids and Monoids in a monoidal category before then finally explaining the title of this article. If you are already an expert on the topic and just want the conclusion, there is a tl;dr at the end.
Here is the structure of this article as a category 🙃

Disclamer: I will of course greatly simplify things along the way, as this is an extremely complex field of research. (If you have never heard this sentence, let me translate it for you: I will not actually simplify anything, but if I am unprecise about something, I can justify it as a “simplification” 😇)

Category Theory

Let us start with the obvious: what is category theory?
Category theory deals with mathematical structures and their relation to each other. If that sounds abstract and not like anything at all, well its because it is. Basically category theory is meant to give a way of formally describing other mathematical concepts as some kind of top level framework.

A Category is an abstract collection containing the following entities:

• a class of objects that make the elements of the category.
• so called morphisms (sometimes referred to as arrows), that form relations from a source object to a target object (single sided). There are different properties associated to morphisms, that are not relevant for us here. If you care, just take a look at Wikipedia.
• a binary operation that is the composition of morphisms.

In mathematical terms this means we have a Category C with the object class ob(C), morphisms mor(C) with the form f : A → B with A, B ∈ ob(C) and f ∈ mor(C) and the composition operation ∘ : mor(A, B) × mor(B, C) → mor(A, C) (written f∘ g : A → C for f : A → B and g: B→ C) that obeys the associativity law and has a neutral element, which simply is the identity morphism id: X→ X for every X∈ ob(C) (yep, just points back to the same object)

All math aside, my favorite example for a category is a flight map: Cities are objects and morphisms are the plane routes from a city to another. You can also compose flight routes to get from a city A to a City C via a stopover in City B, hence composition. It sometimes helps to think of categories and morphisms as just “graphs”.

Totally not exhaustive example of a category of cities with plane routes between them as morphisms.

For the Programmer

Ok, so far so abstract. Let’s now take a look into the “real word” of functional programming. In functional programming, we can use category theory to describe some of the most basic concepts of programming. It is important to keep in mind, that whenever we talk about category theory in programming, we deal with only one category: the category of types.
Ok, so all of our types like String, Int, SomeCoolClassYouWrote, etc. form one Category, that we will refer to as T. Another pretty basic concept of programming are functions. A function takes parameters of some type and returns another type, e.g.:

def getLengthOfString(s: String): Int

Yay, we just went from String to Int! These functions in our category of types are — you guessed it — morphisms from one type to another.
And of course we can compose functions with a compatible type signature:

def getLengthOfString(s: String): Int
def isZero(i: Int): Boolean
def isWordEmpty(s: String): Boolean = isZero(getLengthOfString(s))

Nice! we have a category!

Functional programmers like to call these morphisms “pure functions”. A pure functions is a function like this, that works surely with the given types and has no side effects (This is very important, but more on that later).

Enter: Functors

Another important concept in Category Theory are so called Functors.
Functors in Category Theory describe a mapping from one category to another, that preserves the categories structure (This is really important). This basically means, that functors map objects of one category to objects of another category and they do the same with morphisms while keeping composition intact. Functors are basically morphisms in the big category of all categories, if you will.
Well you might argue (and rightfully so) that I just said that we only deal with one category in programming, that is the category of types. So why would we care about structure-preserving mappings between categories? Well, a special kind of Functors are Functors, that map a category to itself. The so called Endofunctors. As we only deal with one category in programming, you can just keep in mind, that every Functor in the context of programming is an Endofunctor and they are often used as synonyms.

But still, why would we care to map our category to itself? Does not sound too interesting, right? Well basically the idea here is, that we can utilize the concept of an Endofunctur to Encapsulate a Type with some semantic, while preserving its structure.
Lets make this more clearly by looking at an example:

class Box[T](content: T) {
    def map[B](f: T => B): Box[B] = 
      new Box[B](f(content))
}

Ok what do we have here? We basically have a wrapper type — a Box — that contains some content of a Type T. Why is this a functor? Again, a Functor does basically three things: It maps objects to objects, morphisms to morphisms and preserves the structure. In our Box example we have the Functor “Box”, that maps the type T to — well — the type T and it maps every morphism from T to any type B via the map function. You can basically pass any function (morphism) that goes from T to B into map. Also, it does not matter wether you apply a morphism before or after wrapping the type into the Box and obviously composition also still works the same, therefore the structure is preserved.
In this example this is rather obvious, since within the box we are basically just working on the content directly (applying mapped functions on it), but you get the Idea.

Admittingly, the benefit of this this Box type wrapper is rather limited, as we only wrap types into it and pass functions through “map”, effectively making our code more verbose. However, a few paragraphs back I mentioned that we can add a semantic side effect to functors. So let me get back to this, as this is where the actual real world programming benefit of Functors lies:
We give our Box Functor a meaningful name and associate a semantic with it. Let us assume our Box is a Box where the content is optional and call it “Option[T]”, meaning that there is either a content of type T in the box or noting at all. Kind of a Schrödingers Cat kind of box where you do not really know about the content, as long as you do not open it. The rule for our Option Functor is now, that it can contain something or nothing. If we pass a morphism through map, we only apply it if there is a content in the box or return a special empty type if there isn’t. Let’s implement this:

trait OptionT[+A] {
  val isEmpty: Boolean
  def get: A
  def map[B](f: A => B): OptionT[B] =
    if (isEmpty) NoneT else SomeT(f(this.get))
}
class SomeT[A](content: A) extends OptionT[A] {
  val isEmpty: Boolean = false
  def get: A = content
}
case object NoneT extends OptionT[Nothing] {
  val isEmpty: Boolean = true
  def get: Nothing = throw new NoSuchElementException("None.get")
}

Side node: I used the name OptionT in the code example, since Scala does not like classes from its standard library to be overwritten.

Easy! so now we can have an Option of something, that is either a Some(value) or a None, if there is no content.
You might be familiar with this concept if you have used Scala or other languages before that utilize this concept to deal with potential absence of a value while avoiding the null pointer issue. This by the way, is actually how Option is implemented in the Scala standard library (shortened of course).

In practice, there are many of these Functors, that have a semantic (or side effect) associated to it. A few Examples are: Either, where a there can be either a value or an error object (quite similar to Option but with errors instead of just None) or IO for side effects that include io operations, such as reading from a database, writing to a log, etc.

Okay quick recap on what to remember so far: Functors map the category of types to itself in a structure-preserving way, while also holding some semantic, usually referred to as a “side effect”.

Finally Monads

Okay we now know what functors are. It is actually pretty easy to get from the concept of a functor to the concept of a Monad. It helps to view Monads as a higher order concept around functors. Every Monad is also a functor (just with some added operations and rules). For programmers, a Monad basically only adds the flatMap method to the functor.
Of course there is a bit more to it, so let us get started by looking at the math again:
In Category Theory a Monad on a Category C is the tripel M = (F, unit, flatMap)
where

• F is some Endofunctor F : C → C
• unit is a natural transformation (I will explain this term in a bit) from the identity functor Id : C → C to our functor F, defined as unit : Id→ F.
  The identity functor is just a perfect 1 to 1 mapping from our category to itself, therefore giving us its identity.
• flatMap is a natural transformation defined as flatMap : T² → T (The notation T² means T ∘ T, where ∘ is the composition operator of our category)
  T² represents a composed (therefore nested) structure here, that flatMap turns into an un-nested structure, hence the name flatMap

(Short side note: in the correct mathematical definition unit and flatMap are denoted by the greek letters μ “Eta” and η “My”. I choose to give them a name here, as I find these letters extremely annoying to work with as they look so similar that I never can tell them apart or remember which one is which)

Okay, firs of all let me introduce the concept of a natural transformation: These transformations provide a mapping between functors, similar to how morphisms map objects and functors map categories. If you haven’t noticed by now, category theory likes repeating patterns.
unit and flatMap are natural transformations, as they map functors (the Id functor or T² which is also just a composed functor) to the Monads functor F. You might know natural transformations already if you have worked with Lists in Scala. On Scala’s List type there is a method “headOption”, that gives you the top most value in the list as an Option (since it might not be present in an empty list). This really is just a natural transformation from List to Option (vice versa Option has a toList method). If you start looking for natural transformations you will actually find them all over the place.

Okay, back to the Monad: Let’s explain its components one by one:

unit
We have basically already defined unit (sometimes also referred to as pure) in my examples of the Box and Option functors. You can see unit as a way of wrapping the underlying type into the Monad. Because that is really what it is: unit defines, how we get from our plain type to the Monad Type. In the example of our Option Functor we can define unit as
def unit(value: T): Option[T]
or in mathematical(ish) notation unit : T → Option[T]

flatMap
flatMap (often called bind — in different definitions replaced by “join”) is a method that allows us to “chain” Monads. Imagine we have a function that divides by a number and returns an Option as its result, as the function might not be defined for certain input values, such as 0 (also called a “partial function”, as it is only partially defined). If we call this method multiple times, we might end up with a structure that looks looks like Option[Option[Int]]. Here is an example:

def divide_x_by_y(x: Int, y: Int): Option[Int]
val res = divide_x_by_y(4, 2).map(x => divide_x_by_y(x, 1))
// res: Option[Option[Int]] = Some(Some(2))

So in order to “chain” these Monads without nesting, we can use flatMap like so:

> val res = divide_x_by_y(4, 2).flatMap(x => divide_x_by_y(x, 1))
// res: Option[Int] = Some(2)

Nice! This concept is extremely important to Monads.

Let’s quickly implement flatMap to our Option to make it a Monad:

trait OptionT[+A] {
  val isEmpty: Boolean
  def get: A
  def map[B](f: A => B): OptionT[B] =
    if (isEmpty) NoneT else SomeT(f(this.get))
  def flatMap[B](f: A => OptionT[B]): OptionT[B] =
    if (isEmpty) NoneT else f(this.get)
}

Option is now a Monad! Lets quickly draft a rough generic Monad type, that we can use to wrap around functors:

trait Monad[F[_]] {
  def unit(): Monad[F]
  def map[A, B](f: A => B): Monad[F]
  def flatMap[A, B](f: A => Monad[F]): Monad[F]
}

As you can see, we can define the functor’s map function based on flatMap and unit (abstract here, as the way to “flatten” the Monad depends on the actual implementation, like in Option).

Side node: F[_] is a so called “tagless final”, a higher kinded type. Basically F[_] just means “any type F, that itself has one type parameter”. In other words, F[_] means a functor. Option[T] would satisfy F[_] for example.

So using the new Monad wrapper type, we can get an Option Monad like this:

trait OptionTMonad[+A] extends Monad[Option] {
  val isEmpty: Boolean
  def get: A
  def unit(x: A): OptionTMonad[A] = SomeTMonad(x)
  def flatMap[B](f: A => OptionTMonad[B]): OptionTMonad[B] =
    if (isEmpty) NoneTMonad else f(get)
}
class SomeTMonad[A](content: A) extends OptionTMonad[A] {
  val isEmpty: Boolean = false
  def get: A = content
}
case object NoneTMonad extends OptionTMonad[Nothing] {
  val isEmpty: Boolean = true
  def get: Nothing = throw new NoSuchElementException("None.get")
}

So in summery, we can build a Monad around a Functor by providing the flatMap and unit functions, thus enriching our Functor with some important rules and functionalities. The idea is always the same. The Functor provides the semantic and the Monad gives us natural transformations as operations to work with => SomeMonad extends Monad[SomeFunctor]

A Monad is just a Monoid in the Category of Endofunctors

So far so good. Now we now what category theory is and what Functors and Monads are. We just ned one more concept to finally unravel this infamous sentence:

The Monoid

If it sounds like a Monad and looks like a Monad, it is probably sometimes a Monad. Maybe? A Monoid in its general sense is an algebraic structure. This means, that Monoids give us an algebra to work with. Algebras usually consist of a set of “things” (in math usually numbers for obvious reasons) and some rules and operations on this set.
In the case of a Monoid we have a triple (M, *, e) consisting of a set M, a binary operation * : M × M → M that is associative and an element e, that is neutral towards this operation (meaning: something * e = something).

Let me give you an example of a simple Monoid: The natural numbers with the multiplication operation and the neutral element 1 towards the multiplication form the Monoid (N, *, 1). Multiplication is associative and any natural number times 1 is itself.

Here is were it gets a bit tricky: Category theorists hate sets and “actual things”. They like it waaay more abstract. So in category theory there is an alternative definition: A monoid in a monoidal category.

First things first: a monodial category is a category C with a bifunctor
⊗ : C × C → C and a neutral object I ∈ ob(C) (And some more criteria, that are irrelevant for us here).
In this category the objects are categorial Monoids with the form (M, μ, η) where

• M is some object,
• μ is a “multiplication” morphism defined as μ: M ⊗ M → M
• and η: I → M is an isomorphism called unit, that maps the neutral object to an element in M and vice versa (since it is an isomorphism and they go both ways. I will use η1: M → I to denote the inverse).

Well, this definition of a Monoid in a monoidal category looks an awful lot like our Monad, doesn’t it?

Before we continue, let me quickly show that this category theoretical definition of a Monoid can actually be used to describe a Monoid in the sense of an algebraic structure:
In fact this definition is really just a more abstract and generalised way to describe Monoids. Let us make the same example as above with the multiplication on natural numbers:
If we define our bifunctor as the actual numerical multiplication it gives us the neutral element I = 1. One Monoid in this category of “multiplicational monoids” is the very Monoid with the natural numbers, that we used as an example above: Simply take the natural numbers N as the Monoids object, then following the bifunctor definition, μ becomes a morphism for numerical multiplication: μ((2, 3)) = 2 * 3 = 6 and η1 is the neutral element towards μ, since μ((x, η1(x))) = x * 1 = x.

Now we finally have everything we need in order to understand the infamous sentence:

Take all the Endofunctors on a Category and put them into their own category. You now have a new category, whose objects are Endofunctors and whose morphisms are natural transformations between these Endofunctors. This category has a neutral element, which is the Identity Functor Id, that we discussed earlier. We also have a bifunctor “∘” that is the composition of Functors. Now take the Endofunctors in this category and make them Monads: We add unit “η” and flatMap “μ” (flatMap is actually defined using the composition bifunctor “∘”, if you scroll back up to the Monad section of this article), that are both natural transformations.

So to recap:

• we now have a category whose objects are Monads
• we have the neutral Element Id, that is the identity Endofunctor
• and we have the functor composition as an associative bifunctor

If we fill that into our definition above, we can see that we have a lawful monodial category with Monads as objects. These Monads fit the exact definition of a Monoid in monoidal category.

Therefore our Monad is a Monoid in the monoidal category of Endofunctors.

tl;dr

In category theory Monoids are defined in a more abstract way than their algebraic counterparts. This definition aligns with the definition of a Monad if you put it into a monoidal category. A category of Endofunctors with the binary operation of the Functor composition and the monadic natural transformations added to each Endofunctor in it, forms such a monoidal category, thus making a Monad a Monoid in the category of Endofunctors.

Here is what the DALL-E AI generated for “A Monad is a Monoid in the category of Endofunctors”.