A monad is just a monoid in the category of endofunctors, what's the problem?

Roman A. Taycher picture Roman A. Taycher · Oct 6, 2010 · Viewed 164k times · Source

Who first said the following?

A monad is just a monoid in the category of endofunctors, what's the problem?

And on a less important note, is this true and if so could you give an explanation (hopefully one that can be understood by someone who doesn't have much Haskell experience)?

Answer

Tom Crockett picture Tom Crockett · Oct 6, 2010

That particular phrasing is by James Iry, from his highly entertaining Brief, Incomplete and Mostly Wrong History of Programming Languages, in which he fictionally attributes it to Philip Wadler.

The original quote is from Saunders Mac Lane in Categories for the Working Mathematician, one of the foundational texts of Category Theory. Here it is in context, which is probably the best place to learn exactly what it means.

But, I'll take a stab. The original sentence is this:

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

X here is a category. Endofunctors are functors from a category to itself (which is usually all Functors as far as functional programmers are concerned, since they're mostly dealing with just one category; the category of types - but I digress). But you could imagine another category which is the category of "endofunctors on X". This is a category in which the objects are endofunctors and the morphisms are natural transformations.

And of those endofunctors, some of them might be monads. Which ones are monads? Exactly the ones which are monoidal in a particular sense. Instead of spelling out the exact mapping from monads to monoids (since Mac Lane does that far better than I could hope to), I'll just put their respective definitions side by side and let you compare:

A monoid is...

  • A set, S
  • An operation, • : S × S → S
  • An element of S, e : 1 → S

...satisfying these laws:

  • (a • b) • c = a • (b • c), for all a, b and c in S
  • e • a = a • e = a, for all a in S

A monad is...

  • An endofunctor, T : X → X (in Haskell, a type constructor of kind * -> * with a Functor instance)
  • A natural transformation, μ : T × T → T, where × means functor composition (μ is known as join in Haskell)
  • A natural transformation, η : I → T, where I is the identity endofunctor on X (η is known as return in Haskell)

...satisfying these laws:

  • μ ∘ Tμ = μ ∘ μT
  • μ ∘ Tη = μ ∘ ηT = 1 (the identity natural transformation)

With a bit of squinting you might be able to see that both of these definitions are instances of the same abstract concept.