Monads are Dominoes

It’s about time I made my contribution to the zoo of monad tutorials. After explaining the concept of monads to somebody who is not a programmer or a mathematician, I was told that what I had explained sounded exactly like a game of dominoes.

However, instead of explaining monads in terms of a cute metaphor about dominoes, I’m just going to throw you into the deep end. Deep breath!

Definition: A category   is given by objects and arrows between these objects. Each arrow   has a unique source object   and a target object  . For every three objects  ,  , and  , and arrows   and  , there is a composite arrow

such that

Composition is associative: if  ,  , and  , then

There exists a unique identity arrow for each object For every object  , there exists an arrow     such that for every arrow  , we have    

A category for dominoes:

The objects of the category are the natural numbers. An arrow in the category is a domino piece with two numbers on it:  . A composition of arrows   is two domino pieces placed together end-to-end by the following equation:

The identity arrow for each object   is a domino piece   with the same number   on both ends.

Associativity:

Identity:

A monad for dominoes

Definition: A monad is given by a functor   (from a category   to itself, i.e. an endofunctor in  ), equipped with natural transformations:

x

where   is the identity functor and x is functor composition. This must satisfy the axioms that     and   are identity transformations, and     (i.e.   is associative).

The dominoes need not be annotated with numbers, but might be annotated with any set of objects. Therefore, there exists an endofunctor   on the category of sets, such that for all sets  , we can construct the set of dominoes  .

For every object   in  , we can construct a domino  . This is   for our monad. Then, for the set of dominoes  , we can construct   which is the set of dominoes annotated with other dominoes. For any pair of dominoes in  , composed end-to-end, we can see it as a single domino in  . The   operation in our monad is then the fact that for any such pair of dominoes  , it behaves as the domino   with regard to composition with other dominoes in  .

Proof:

Associativity:

Identity:

Exercises left to the reader:

1. What does a monoid in the category of dominoes look like?

2. How would the game of dominoes change if it allowed products and coproducts?

3. Can you come up with a coherent theory describing the behavior of “spinners” in the game of dominoes?

Advertisements

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.

On Monoids

I’m often asked about monoids, monads, and what the difference is between the two. Seeing that there’s not a lot of material that explains these things in terms of Scala, I’m going to try to remedy that presently. Even if you already know what these things are, I hope to provide a little deeper insight. In this post I’m going to talk about monoids in some depth.

First, here is a definition for Monoid, in Scala:

trait Monoid[T] {
  def append(m1: T, m2: T): T
  val identity: T
}

To state that in English, a monoid is given by a type T together with a function append: (T, T) => T, and a value identity: T. The rules for a monoid are that append must be associative (meaning that append(x, append(y, z)) == append(append(x, y), z)), and identity must be an identity for that function (such that append(identity, x) == x, and append(x, identity) == x. For example, String with concatenation and the empty string form a monoid. Boolean with true and &&, or Boolean with false and ||, also are monoids. As are Int with addition and 0, multiplication and 1, etc.

As an example, here is the String monoid:

val stringMonoid = new Monoid[String] {
  def append(s1: String, s2: String) = s1 + s2
  val identity = ""
}

Monoids are List-Algebras

Everyone is familiar with the singly-linked list (a.k.a. cons-list). A List[T] is constructed as either the empty list (Nil), or from an element of type T and another List[T].

Nil is an irreducible unit (it takes no arguments and has no structure), and is in fact totally equivalent to the () value of type Unit. The :: (cons) constructor takes two arguments, and indeed a non-empty List[T] is equivalent to a pair (T, List[T]) (the head and the tail).

Note that a Monoid consists of two functions, one that takes no arguments, and one that takes two arguments, just like the constructors of List. This is not a coincidence. If you have a List[T] and a Monoid[T], you can reduce the list using the Monoid, to a single value of type T.

def reduce[A](ts: List[A], m: Monoid[A]): A =
  ts match {
    case Nil => m.identity
    case x :: xs => m.append(x, reduce(xs))
  }

If you expand out the Monoid argument, you get:

def reduce[A](ts: List[A], identity: A, append: (A, A) => A): A

This looks suspicously similar to foldRight and foldLeft. Again, not a coincidence. Here’s the signature for foldRight:

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

In fact, the implementation of these last two is exactly identical. So, monoids are just an abstraction that represents the arguments you give to folds. The associativity rule simply models the fact that you should get the same answer for a given monoid whether you foldLeft or foldRight. The identity rule (in loose terms) models the fact that the empty list “doesn’t count”.

Monoids are one-object categories

Those readers further along might be wondering where this notion of monoids comes from, and why the concept is even warranted in the first place. Well, it comes from Category Theory. So let me give you a crash course.

A category consists of objects (A, B, C, etc.) and arrows between objects, (A => B, A => C, B => C, etc). You can think of it as a diagram or graph, with objects as the nodes, and arrows as directed edges between the nodes. Given any pair of arrows f: B => C and g: A => B, there exists a composite arrow (f * g): A => C.

Here’s an encoding of the concept in Scala:

trait Category[F[_,_]] {
  def compose[A,B,C](f: F[B,C], g: F[A,B]): F[A,C]
  def identity[A]: F[A,A]
}

For example, there’s a category where the objects are Scala types, the arrows are Scala functions, and the composition of arrows is simply function composition.

val catScala = new Category[Function1] {
  def compose[A,B,C](f: B => C, g: A => B): A => C =
    f compose g
  def identity[A]: A => A =
    (a: A) => a
}

A category must have an identity arrow for each object, which points from the object to itself. In the Scala category, these arrows are represented by the identity function.

Furthermore, a category must satisfy associativity ((f * g) * h == f * (g * h)), and identity (f * identity == f and identity * f == f), for all arrows f, g, and h.

Note that the laws that a category must satisfy are exactly the laws that a monoid must satisfy. You can think of the append function of the monoid as the arrow composition, and the identity value as the identity arrow. For a Monoid[T], the arrows are precisely all the values of type T, and T itself is the only object in the category.

We can give this category in Scala:

// The category for a given monoid.
def monoidCategory[M](m: Monoid[M]) =
  new Category[({type λ[α, β] = M})#λ] {
    def identity[A] = m.identity
    def compose[X, Y, Z](f: M, g: M) = m.append(f, g)
  }