Monads are Monoids in the Category of Endofunctors

monads-are-monoids-in-the-category-of-endofunctors.txt

"Monads are Monoids in the Category of Endofunctors"

If you are a functional programmer, you've probably heard this statement before.

To understand it, first we need to understand its component parts:
. Category
. Monoid
. Endofunctor

After this, we will glue those parts together piece by piece to grasp the whole.

-----------------------------------------------------------------------------

/*** CATEGORY ***/

A Category is made of "objects" linked by "arrows" (aka morphisms). That's it!

Objects: A, B, C, D, ...
Arrows: A => B, A => C, C => D, B => B, C => A, D => B, ...

Categories also have the following properties:

--- Arrow composition ---
Given the arrows:
f: A => B
g: B => C
h: C => D

then there must exist an arrow:
i: A => D == h . g . f //"." means composition

Also, arrow composition is associative:
(h . g) . f == h . (g . f)

--- There is an identity arrow for each object ---
idA: A => A 
idB: B => B 
idC: C => C

In the context of programming, the objects are Types and the arrows are Functions. Keep this in mind...
Any similarity between arrow composition and function composition is not a coincidence!

-----------------------------------------------------------------------------

/*** MONOID ***/

A Monoid is defined by 3 parts:

--- A set of elements ---
In Category Theory, is just a collection of objects.
In programming, the "set" is some type (Int, String, List, etc) and the "elements" are the values of this type.

--- A binary associative operation between the elements of the set ---
Considering the "set" as the type "S", then the operation (tipically called "append") is:
>>> def append(e1: S, e2: S): S

Or, in an OOP approach, "append" could be a method of S:
>>> def append(other: S): S

--- An element that combined with any other in the set results in the other --- 
The "neutral element", also known as "zero" or "identity". It's behavior is:
>>> s.append(zero) == s
>>> zero.append(s) == s

Some examples of Monoids, in the form (set, binary-associative-operation, zero):
(Int, +, 0)
(Int, *, 1)
(String, +, "")
(List, ++, Nil)

-----------------------------------------------------------------------------

/*** ENDOFUNCTOR ***/

Endofunctors are a special case of Functor, therefore we need to define Functor first!

A Functor is a mapping between objects of Categories, preserving the arrows connecting them.
The Endofunctor is a Functor that maps objects of the same Category!

Did you remember that "In the context of programming, the objects are Types and the arrows are Functions"?
This has an interesting consequence... ALL FUNCTORS WE USE IN PROGRAMMING ARE ENDOFUNCTORS!
We are always inside a single Category: the Category of our programming language's types!
So, why don't we call them Endofunctors? I think it's just more simple and cool to use Functor...

Back to software, a Functor - F - can be defined as:

--- A Type Constructor F[_] ---
In OO languages it can be a class with a type parameter
>>> F[_]

--- A function of type: "F[A] => (A => B) => F[B]" ---
In OOP, it can be a method of F[A] with the type "(A => B) => F[B]"
This function is typically called "map"
>>> def map[B](f: A => B): F[B]

--- Adherence to the Functor laws ---
Let "fa" be a Functor of type F[A] and "f" and "g" be functions of type "f: A => B" and "g: B => C"
1. Identity: fa.map(a => a) == fa
2. Composition: fa.map(f).map(g) == fa.map(g compose f)

-----------------------------------------------------------------------------

/*** CATEGORY OF ENDOFUNCTORS ***/

Now that we know what Categories and Endofunctors are, a Category of Endofunctors is
a Category where the objects are Endofunctors and the arrows are Natural Transformations.

That's new! What is a Natural Transformation?

A Natural Transformation is a transformation between Functors.

They are for Functors what Functions are for normal Types.
When the objects are Types, arrows are Functions. 
When the objects are Functors, arrows are Natural Transformations

Given the types A and B, we can have a function:
f: A => B

Given the Functors A[T] and B[T], we can have a Natural Transformation:
F[T]: A[T] ~> B[T] //~> represents the Natural Transformation. We'll use this notation again soon!

-----------------------------------------------------------------------------

/*** MONOID IN THE CATEGORY OF ENDOFUNCTORS ***/

Finally, time to put everything together!

A "Monoid in the Category of Endofunctors", as we saw above, would be:
- a set of elements: the Endofunctors F //which are the objects
- a binary associative operation: F[F[A]] ~> F[A] //remember: in this Category arrows are Natural Transformations!
- the zero element: Id[A] ~> F[A] //another Natural Transformation

Id[A] is the Identity Functor, which is a Functor that does nothing! It doesn't encode any effect!
In fact, Id[A] == A. The definition of Identity Functor in Cats is exactly this - type Id[A] = A
Given the Id Functor "ida: Id[A]" and a function "f: A => B", then:
>>> ida.map(f) == f(a) //It is the same as just applying the function directly

"F[F[A]] ~> F[A]" is associative in the sense that, if you want to turn F[F[F[F[A]]]] into F[A], 
it doen't matter what two Fs you will merge first.

Knowing that Id[A] == A, it became easier to see the behavior of the zero:
>>> Id[F[A]] == F[A]; F[Id[A]] == F[A]

Is this "Monoid in the Category of Endofunctors" we've just defined really a Monad?

Commonly, we see Monads defined as:
- a type constructor: M[_]
- a function of type: A => M[A] //unit
- a function of type: M[A] => (A => B) => M[B] //map
- a function of type: M[A] => (A => M[B]) => M[B] //flatMap, bind, >>=

We've used this definition before to explain why Monads are useful here:
https://gist.github.com/programaker/07d117b239566879c088eb4e13037469

But there is another way to define Monad which is more helful to our goals here:
- a type constructor: M[_]
- a function of type: A => M[A] //unit
- a function of type: M[A] => (A => B) => M[B] //map
- a function of type: M[M[A]] => M[A] //flatten, join

But what about flatMap? It is very important! Without it, there is no for-comprehension nor do-notation!
In this definition, it is a derived function, expressed in terms of map and flatten:
>>> def flatMap[B](f: A => M[B]): M[B] = map(f).flatten //OOP version, where M[A] is the object, not a function argument

Notice that both versions contain a "map" function. But, isn't map part of the definition of Functor?
YES! And this solves part of the mystery: Monads ARE Functors! (actually Endofunctors, but in programming it doesn't matter)

Comparing the "Monoid in the Category of Endofunctors" with the second Monad definition, we have:
"Id[A] ~> F[A]" corresponds to "A => M[A]" //unit (remember that Id[A] == A!) 
"F[F[A]] ~> F[A]" corresponds to "M[M[A]] => M[A]" //flatten

And that's it! Thanks to the alternative Monad definition, we were able to match its structure and 
the structure of the "Monoid in the Category of Endofunctors" and see that the legend is true!