Three Popular FP Myths – 2

This is the second part of Three Popular FP Myths. I would not call it “debunking”, just a clarification. There’s a lot of confusion in functional programming circles about all this.

A Monad is not a Monoid in the Category of Endofunctors

But they say it is

Well, everybody knows that it is. StackOverflow says that it is (“With a bit of squinting”).  James Iry says that it is (with a wink), ascribing the phrase to Wadler. Barbie, quoting James, says that it is:

Even Saunders MacLane in his “Categories for the Working Mathematician” seems to be saying this:

So What, Still It Is Not

First, what is a monoid? It is usually defined in Sets, but we can be more generic, and define it in an arbitrary category with cartesian product × and terminal object 1.

First, a classical Monoid is a set A, a binary operation Op: A×A → A, and an element e:A such that Op is associative, and e is a neutral element for Op.

A Monoid in a category C constitutes of an object A, a binary operation Op: A×A → A, and an “element” e:1 → A such that Op is associative, and e is a neutral element for Op.

A Monad is an endofunctor M in a category C with a natural transformation μ:M∘M → M and a natural transformation η:Id → M, such that μ is associative, and η is neutral regarding μ. The last one means that μX∘M(ηX) = μXηMX = identityMX.

We can start with the category of endofunctors on C, assume has products and a terminal object, Endo(C) , and try to figure out what’s a monoid there. No, what’s a terminal object there? It’s (obviously) a functor that maps every object to1. Nothing even close to Id, the identity functor. Also, cartesian product of a couple of endofunctors is defined object-wise, so F×G(X) = F(X)×G(X). Functor composition is not involved. Monoids are not defined via functor composition, they are defined via Cartesian product.

So, that’s it. Not that these two don’t look similar, they do – but they are very different.

Now, what’s that similarity? Aha, see next.

Monoidal Category

A Monoidal Category generalizes Cartesian category in the following way:

Instead of Cartesian product, we introduce tensor product – a binary operation on the categories objects that is similar in behavior to Cartesian product.

For a couple of objects A and B, A⊗B is just another object of the same category. This operation has to be functorial by each argument: for a:A → A' we will have a⊗B:A⊗B → A'⊗B, and for b:B → B' we will have A⊗b:A⊗B → A⊗B').

The operation ⊗ has to be associative, up to a natural isomorphism, that is, for each A,B,C an associator is defined, αA,B,C:(A⊗B)⊗C → A⊗(B⊗C).

In addition to this, a unit object I is introduced, that serves like a neutral element for ⊗: two natural transformations provide isomorphisms between A, A⊗I, and I⊗A.

All these natural transformations should satisfy certain compatibility rules (see wiki.)

A natural example of a monoidal category is a Cartesian category, where terminal object 1 serves as a unit I, and Cartesian product × serves as a tensor product ⊗.

Another example is the following:

Monoidal Category of Endofunctors

Given a category C, the category of its endofunctors (as objects) and natural transformations (as morphisms) can be viewed as a monoidal category with ⊗ defined as functor composition ∘, and Identity Functor Id as the unit object I. Feel free to check associativity, functoriality, neutrality and the pentagram property.

Monoid Object in Monoidal Category

ncatlab explains it with precision. We expand the notion of monoid to the case where operation is defined not on a Cartesian product, but on a tensor product. μ:M⊗M →M Instead of neutral element, we need a unit morphism, η:I → M, and a bunch of properties, like associativity and neutrality, making this construct look like a regular monoid.

Monad as a Monoid (Object in Monoidal Category)

If we take as a base category the monoidal category of endofunctors defined above, a (generalized) monoid in such a monoidal category is an endofunctor M with μ:M∘M → M and η:Id → M. The monoidal properties of these μ and η are exactly the properties of a monad. So we have a monad.

Conclusion

I hope this clarifies the confusion. Any time you encounter a monad, it makes no sense to try to find an operation that maps “two elements of a monad” to the third element.

Dan Piponi had express all this in 2008 in plain Haskell:
http://blog.sigfpe.com/2008/11/from-monoids-to-monads.html?m=1