In a previous post on monoids, we established that Monoids are List-Algebras. In other words, a monoid `A`

essentially models a function of type `List[A] => A`

. We saw how the unit and associativity laws for monoids model the fact that we can fold left and right, and that the empty list doesn’t count.

**Monoids for Free**

We defined a monoid as a category with one object. Now, let’s generalize this notion. Before, we represented Monoid as having a binary function and an identity element for that function. But by our categorical definition, we could just restrict the Scala category (where types are the objects and functions are the arrows) and define Monoid in terms of that:

class Endo[M] {
def compose(m1: M => M, m2: M => M): M => M = m1 compose m2
def identity: M => M = m => m
}

A function from some type to itself is called an *endomorphism*. E`ndo[M]`

for *any* type M, is a monoid, by our previous definition. It is a category with one object M whose only arrows are endomorphisms on M.

We know already that lists and monoids are intimately connected. Now notice that `M => M`

is exactly the form of the right-hand side of foldRight. Let’s remind ourselves of the type of foldRight:

def foldRight[A,B]: (List[A], A => (B => B)) => (B => B)

Read this with an eye to endomorphisms and the fact that they form monoids. FoldRight, then, is saying that a `List[A]`

together with a function from a value of `A`

to an endomorphism on `B`

, allows us to collapse all those `A`

s into a single endomorphism on `B`

. Here’s a possible implementation:

def foldRight[A,B] = (as: List[A], f: A => B => B) => {
val m = new Endo[B]
as match {
case Nil => m.identity
case x :: xs => m.compose(f(x), foldRight(as, f))
}

That’s slightly different from what you might be used to seeing, but equivalent.

**A Theory of Monoids**

This gives rise to a further theory. If we had a `List[List[A]]`

such that `A`

is a monoid, so we know we can go from `List[A]`

to `A`

, then it’s safe to say that we could fold all the inner lists and end up with `List[A]`

which we can then fold. Another way of saying the same thing is that we can pass the list constructor `::`

to `foldRight`

. It has the correct type for the `f`

argument, which is not a coincidence (namely `A => List[A] => List[A]`

). That in turn gives us another function (`List[A] => List[A] => List[A]`

) which, as it turns out, appends one list to another. If we pass *that* to foldRight, we get `List[List[A]] => List[A] => List[A]`

. That *again* has the proper type for `foldRight`

, and so on. The pattern here is that we can keep doing this to turn an arbitrarily nested list of lists into an endofunction on lists, and we can always pass an empty list to one of those endofunctions to get an identity.

So the types of arbitrarily nested lists are monoids. Our composition for such a monoid appends one list to another, and the identity for that function is the empty list.

Let’s call this our “theory of monoids”, so we can refer to it by name later on.

**Monoids of a Higher Kind**

But there’s something more general going on here. For a moment, let’s denote `List[A]`

as `A*`

, meaning “zero or more values of type `A`

“. If `A`

is a monoid, then this gives us the function `A* => A`

(since monoids are list-algebras). Now note what happened with arbitrary nesting of `List`

. Let’s notate this as `List*[A]`

meaning “lists of `A`

nested to zero or more levels”. It seems that we can go from `List*[A] => List[A]`

. So the `List`

type constructor itself seems to be a sort of monoid of a higher kind.

And this turns out to be true. Let’s look at our monoid trait again:

trait Monoid[M] {
val identity: M
def append(a: M, b: M): M
}

With an eye towards `M* => M`

, we can see that the Monoid provides a way of turning a list-of-M of arbitrary length (M*) into a list-of-M of length 1 (M¹). The `identity`

takes care of the case where we have an empty list (M⁰), and the `append`

reduces M² to M¹. By induction, we know that this is enough to collapse any number of Ms into a single M.

For our higher-kinded monoid, which we’ll call M as well, we need the same thing–a way of going from M⁰ to M¹, and from M² to M¹. “Higher-kinded monoid” is a bit long-winded. Since it’s a *triad* (a type constructor with identity and append), and also a sort of monoid, we’ll contract this to “Monad”:

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

**The Obvious Axioms**

Now recall the monoid laws from before. We can infer the *monad laws* from those. Monad’s `unit`

is the `identity`

of our higher-order monoid, and should be an identity for the `join`

method, which is Monad’s equivalent of Monoid’s `append`

. So `join(unit(m)) == m`

(left identity) and `join(map(unit)(m)) == m`

(right identity).

The `join`

method should be associative, meaning that if you have `M[M[M[A]]]`

, it doesn’t matter whether you join the inner or outer `M`

s first. That is, `join(map(join)(m))`

should equal `join(join(m))`

.

This is pretty much a straight translation from the monoid laws, except that we needed `map`

to apply a function “on the right” (or on the inside) of an `M`

.

**The Monad for Monoids**

OK, so remember our theory of monoids from above? We can encode that theory in Scala, using a monad:

val listMonad = new Monad[List] {
def map[A,B](f: A => B) = (xs: List[A]) => xs.map(f)
def unit[A](a: A) = a :: Nil
def join[A](xs: List[List[A]]) = xs.flatten
}

So `List`

is a monad that represents a theory about monoids. What is this thing saying about monoids? The `map`

method says that if we can fold a `List[A]`

with a monoid, and we can turn every `A`

into a monoid `B`

, then we can fold a `List[B]`

. The `unit`

and `join`

methods, together with the *monad laws* above, are saying the following:

If we have an expression of some monoid-type `A`

, like `(a1 + a2 + a3)`

, where `a1`

, `a2`

, and `a3`

are values of type `A`

and `+`

is the `append`

function of the monoid, then we can insert the `identity`

into that expression wherever we want, and we can add and remove parentheses at will, and the order in which we add and remove them doesn’t matter.

**Monads Are Not Just About Monoids**

Alright, so the `List`

monad is all about monoids, but this is just one use case for the `Monad`

trait. I.e. `List`

is *the* monad for monoids.

We could write a `Monad`

instance that means something totally different. For example we might write `Monad[Future]`

, to encode a theory of concurrent processes. What would that theory be saying? Well, `map`

would say that we can extend a running process by giving its continuation. And the `unit`

and `join`

functions with the monad laws would say that we can arbitrarily fork subexpressions of a program, and arbitrarily join with forked processes, and that the order in which we fork and join doesn’t matter to the result of the program.

We can perfectly well write an implementation of `Monad[Option]`

, or `Monad[Reader[A]#->]`

where `trait Reader[A] { type ->[B] = A => B }`

. I’ll leave these implementations as an exercise for the reader. See if you can come up with an explanation for the monad laws in each case.

I hope you’ve enjoyed this deep dive into monoids, monads, and their relationship.