Monoids in the Category of...

The unfortunate meme phrase “a monad is just a monoid in the category of endofunctors, what’s the problem?” comes from two sources:

• The fact and most of the phrasing comes from Mac Lane’s Categories for the Working Mathematician, but
• “What’s the problem?” is a cheeky addition from a funny 2009 blog post: A Brief, Incomplete, and Mostly Wrong History of Programming Languages

The meme words have become an annoying blot on the fringes of the Haskell universe. Learning resources don’t mention it, the core Haskell community doesn’t like it because it adds little and spooks newcomers, and it’s completely unnecessary to understand it if you just want to write Haskell code. But it is interesting, and it pops up in enough cross-language programming communities that there’s still a lot of curiosity about the meme words. I wrote an explanation on reddit recently, it became my highest-voted comment overnight, and someone said that it deserved its own blog post. This is that post.

This is not a monad tutorial. You do not need to read this, especially if you’re new to Haskell. Do something more useful with your time. But if you will not be satisfied until you understand the meme words, let’s proceed. I’ll assume knowledge of categories, functors, and natural transformations.

Deriving Simple Recursive Functions

I used to teach Haskell to first-year university students, and many of them struggled to write their first recursive functions. It really isn’t obvious why you can solve a problem using the function you’re in the process of defining, and many students have difficulty making that leap. There is no shame in this. I remember taking a long time to grok proof-by-induction, which has a similar conceptual hurdle: how can you use a statement to prove itself?

Writing recursive functions requires a lot of tacit knowledge in selecting the recursion pattern to use, which variables to recurse over, etc. Recursion was not immediately obvious to industry professionals, either: I remember an errata card that came with TI Extended Basic for the Texas Instruments TI 99/4A which mentioned that later versions of the cartridge removed the ability for subprograms to call themselves, because they thought it was not useful and mostly done by accident.

I want to share a recipe that helped my students write their first recursive functions. There are three steps in this recipe:

1. Write out several related examples
2. Rewrite the examples in terms of each other
3. Introduce variables to generalise across all the examples.

Worked examples and some teaching advice after the jump.