More on Monoids and Monads

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. Endo[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 As 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 Ms 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.

14 thoughts on “More on Monoids and Monads

  1. This is the first discussion of monads I’ve seen that gives any hints about the etymology of the name. I assume that all these mathematical names were chosen for very good reasons, but I never see them explained.

    • I actually don’t know for a fact that this is the proper etymology, but it’s the only one I’ve encountered that makes sense.

      • The term ‘monad’ actually originates with Pythagorean mystics. I think modern usage is a nod to Leibniz, whose metaphysical theories were based on a single element, the monad.

      • Scott, the term monad is just Greek for something with an adicity of one. I think that the term came into category theory as a pun like what I described. I’ll dig up a link to a source on that. Stand by.

      • From “Categories For The Working Mathematician” by Saunders Mac Lane, page 138:

        Terminology: These objects \langle X, T, \eta, \mu \rangle have been variously called “dual standard construction”, “triple”, “monoid”, and “triad”. The frequent but unfortunate use of the word “triple” in this sense has achieved a maximum of needless confusion, what with the conflict with ordered triple, plus the use of associated terms such as “triple derived functors” for functors which are not three times derived from anything in the world. Hence the term monad.

      • As far as I can glean, the term “monad” was suggested by Jean Benabou in 1966. Somebody should email him and ask what prompted it.

  2. Excellent post, as usual. I like this approach of talking about monads in terms of the algebraic theories they describe.

    It’s kind of mind-bending how monads and monoids are intertwined on several different levels. Monoids are algebras for lists, which are a kind of monad, which is a monoid in the category of endofunctors…

  3. What’s an algebra for a Future? In Scala speak, an algebra for a monad M requires a distinguished type A, along with a function M[A] => A such that everything commutes. But a Future requires no particular type A; a function Future[A] => A is available for all A, which simply blocks on the computation and returns it when it’s done. So the algebras for future seem “obvious” and are generated for all A. In fact Future looks a lot like the Identity monad, just with different semantics–from a categorical perspective (at least the usual categorical encoding of types and functions) it seems like they’re no different.

  4. Tom, the answer to that question is the same as “what’s the algebra for IO?”. Future depends on a particular parallel strategy, just as IO depends on an execution environment.

    • But it doesn’t depend on the type of the thing you’re computing (unlike the List theory, which only has an algebra for each type in the Monoid class.)

  5. The 5th line in the 3rd code snippet should be:

    case x :: xs => m.compose(f(x), foldRight(xs, f))

    instead of:

    case x :: xs => m.compose(f(x), foldRight(as, f))

    Right?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s