I was temporarily (for six days) a GitHub outlaw with my repos hidden from public view, and this abstract blog article was part of my "coding hunger strike". For example, if you were to go to the pandemic package on PyPI, you were able to download files for an open source epidemic simulation I wrote a while back (article here) but if you then clicked through to GitHub to view the code, you'll have gotten a 404 error.

If you work at GitHub, I would humbly suggest that some other measures be taken in the event of whatever (in my case some issues I raised were tagged as spam) because, to reduce my argument to two words, Knight Capital. Dead code coming back to life can be catastrophic. End of editorial.

The question du jour. Have you ever wondered if a monad in functional programming is actually a monad in mathematics? Is that the kind of thing you absolutely must know the answer to, once you notice the question? No? Then write to Nat Friedman and let him know I need to be pushing code because otherwise you'll be left with this kind of navel gazing.

Hmmm, are monads monads?

What could be a more important question? Well, maybe choosing an optimizer for your drug discovery simulation or using microprediction to reduce spoilage is actually more important but back to monads. I personally made rather slow progress on this front (still don't understand why arrows are strong monads, for example) but perhaps something of the connection between the monad pattern in programming and the monad definition in mathematics can be cleared up here. (I'm going to pause now to allow 95% of you to suddenly realize you have something pressing to do. I get it if this particular itch isn't one you need to scratch, just at the moment.)

We must find out! Let's not be turned off by the fact that most articles about monads leave newbies like your author thinking that a monad is an endofuntorial elephant. I nearly went mad after reading twenty random monad blogs without finding a single one that states which category or categories we are in. That's like finding descriptions of "Germany" that include the Autobahn, white sausages and beerhouses, but not one that mentions Germany is a country.

This lack of precision hardly helps us when we turn to details, like that fact that monad is Haskell isn't actually a functor in the Haskell hierarchy. Indeed as Heunen and Jacobs point out, both monads and arrows are actually monoids, in mathematical parlance. So let me state this first: a monad (programming speak) is a monad (math speak) *in the category of types*. If neither of us get anything more from this exercise, so be it.

Let's start from the programming side. One use of a monad pattern emerges from an everyday programming need: the desire to extend the number system (or some other type) to include an exception, or 'missing' value. This is achieved by creating a new type. In Scala (you'll forgive the bias, I really don't know Haskel) this is constructed as Option[something]. When you alter a Double so that it is an Option[Double] you are creating an obvious mapping from one type to another, you might even say "the" obvious mapping. But you are not merely mapping objects to Option[objects] - at least not if you wish to get any work done. You are also dragging along all the nice things you'd like to do to the objects, namely hit them with functions. The "dragging" is a functor.

A functor is not just a map from one space to another, we recall, but also a map of all the stuff-you-can-do-to-things in that space to stuff-you-can-do-to-things in the other space. To be more precise, I should say we are dragging over not just functions but maybe some other stuff like relations, but that is a fine point for now. In the case of Double => Option[Double] you drag f(x) = x*x+3, say, into a function we might call Some(f) which should act on elements of Option[Double] and take Some(x) to Some(x*x+3).

Or take Double and shove it in Mathematica, metaphorically. It is no longer a Double, but merely an expression, like x*x+3 which is yet to be bound to a specific Double. Thing is, you'd like to do to the expressions what you do to real numbers, so evidently we are dragging morphisms like the one taking 3 into 9 and 5 into 15 over to morphisms on expressions (like the one taking x into 3*x). They ain't the same thing but there is clearly some conservation of structure as we go from real, tangible Double into ephemeral 'x'.

For more examples of "obvious" mappings, take a bunch of program fragments and shove them together in a combinator pattern. Or play with state machines, whose composition can be simplified to a single state machine. The notion of an incomplete calculation, an unconsummated something, an unsimplified something, or an extension of a domain are all examples where there is an obvious, rich mapping from one type to another. So rich, in fact, that if we are thinking sloppily we often fail to distinguish between the domain and range of the obvious mapping.

Now let's back up and dot a few t's because while a monad is a fairly simple pattern in programming we aren't close to recognizing its mathematical definition (well, I'm not). To be a little formal, we need categories, functors and natural transformations. Remember that a category is supposed to be a space together with some morphisms obeying laws? It was a long time ago for me too, but the morphisms in two of the examples I mentioned are merely the set of all functions with the signature Double => Double. Again, a morphism is a more general concept than a function, basically obeying associativity, and for that reason is often called an arrow (in mathematics). But let's not worry about the possible deficiency in our morphism collection right now because the set of all Double => Double functions is interesting enough.

Two quick checks. First, it is obvious that composition of functions in the mathematical sense - no side effects - is associative. Second, we'll need not concern ourselves overly with the existence of an identity morphism - the other category requirement - because constructing the function that takes x and returns x presents little challenge to most programmers! Safe to assume the identity exists.

So jolly good, DOUBLE is a category and, returning to our first example, Some( ) sure looks like it might help make a functor from DOUBLE into something we imaginatively call SOME-DOUBLE. (In general we could call the first category THING and the new category SOME-THING, I suppose). Likewise Symbolic( ), which I just made up, looks like it might help create a functor from DOUBLE into SYMBOLIC-DOUBLE, as we might name it, a category representing a computation but not its answer. Are the images of these maps themselves categories? It seems pretty obvious that they are, because of the triviality of function application associativity and, to be pedantic, the obvious fact that the identity morphism maps to the identity morphisms in both SOME-DOUBLE and SYMBOLIC-DOUBLE.

We focus on the first functor momentarily, whose implementation in Scala comprises the constructor x=>Some(x) and the lifting f => (x => x map f) which uses the 'built-in' map method. I personally think of this built-in functor as a 2-tuple where MAP._1 acts on objects and MAP._2 acts on functions. I'll just use MAP going forward for either though, slightly abusing notation.

MAP = ( x=>Some(x), f => (x => x map f) )

As an aside, if I had my way Function1 would come with a map method so the morphism mapper f => (x => x map f) would look simpler, but it doesn't matter so long as we remember that morally speaking, the morphism-mapping part of the functor is just 'map'. When I say that map is 'built in' I really mean built in to the collections libraries, incidentally, because map is provided in the scala.collection.Traversible and scala.collection.Iterable traits and all collections are of one of these two types. Thus for all intents and purposes the combination (constructor, map) is an "off the shelf" functor although yes, for the third time, there are indeed plenty of morphisms other than functions - partial orders, paths on graphs et cetera - I'll let it go if you will.

What is the domain of MAP? My guess is that we should extend it to include not just DOUBLE but SOME-DOUBLE. Also SOME-SOME-DOUBLE, SOME-SOME-SOME-DOUBLE and so on ad infinitum. Call that big union the category Omega so that MAP is, in math speak, an endofunctor because it maps the category Omega into itself. We are getting a little closer to the mathematical definition now, I do hope, and here comes the last little jog. It is a natural (and obvious) transformation between the built-in functor MAP applied once and the built-in functor MAP applied twice.

To humor me, apply MAP twice to get MAPMAP = MAP compose MAP, a functor that maps points x => Some(Some(x)) and of course messes with morphisms as well. For example, consider the function f(x) = x*x+3. MAP takes this morphism into another morphism which in turn happens to map Some(x) into Some(Some(x*x+3)). On the other hand MAPMAP would take f into a different morphism taking Some(x) into Some(Some(Some(x*x+3))). This just emphasizes the fact that MAP and MAPMAP are not the same thing, but they are dreadfully close.

The built-in functor MAP takes points to points and functions to functions. |

In category theory, there is a notion of a natural transformation between two functors that respects composition of morphisms. If we were category theorists, we'd probably say, "Oh I suppose there must be a natural transformation from MAPMAP to MAP." I did not, come to think of it, have that exact experience myself, admittedly. The moral of the story: I think we should talk more about natural transformations to make us better people.

Actually we'll only talk about the one natural transformation mentioned: MAPMAP to MAP. As the definition on wikipedia explains (with F=MAPMAP and G=MAP, and C=D=Omega), this amounts to finding what is known as a component function (math speak) that lifts h=MAP(MAP(f)) onto g=MAP(f). That is straighforward because, translating back to Scala speak,

h andThen flatten = flatten andThen g

You couldn't hope for a more "obvious" commutative diagram than this - which is a good sign because in category theory many things are supposed to look obvious after untangling of definitions or chasing of diagrams. We only need the top half of the diagram here, incidentally, and I don't think I need to define flatten. Even Scala newbies could implement the bit of it we need via pattern matching: x => x match {Some(y) => y}.

Flatten is the component realizing the natural transformation from MAPMAP to MAP (top half) whereas Some is the component realizing the natural transformation from Id to MAP (bottom half) |

f andThen Some = Some andThen g

so the bottom half commutes.

We're done. If you skip down the wikipedia monad page to the formal definition, ignoring the stuff at the start about adjoint functors which is just confusing, you'll see that a monad comprises a functor F and two natural transformations, one taking the identity functor Id to F and the other taking F compose F to F. The natural transformations are defined by their components which are, respectively, the constructor Some and the squishing operation flatten. To summarize, here is how we would relate the definition of a mathematical monad on Wikipedia to the day-to-day notion of a monad in programming Scala:

Mathematical monad ingredients | Example of a common monad |

Two categories C,D | One category comprising an infinite union of similar types C=D=Omega=Union(DOUBLE,SOME-DOUBLE,SOME-SOME-DOUBLE,...) |

A functor between the categories F: C->D | The "built-in" functor MAP taking points x=>Some(x) and functions f => (x => x map f) |

A natural transformation taking the identify functor Id to F | A natural transformation taking the identify functor Id to MAP |

A "component" realizing said natural transformation | A constructor x => Some(x) that "wraps" up x |

A second natural transformation taking F F -> F | A natural transformation from MAPMAP to MAP |

A second "component" realizing the second natural transformation | A flatten operation x => x match {Some(y)=>y} that unwraps y |

As the mathematicians remind us, there are some things to check, known as coherence conditions, but I leave that to the reader.

Now here we are transforming functors when what we are looking for is as elementary as unwrapping a burrito . One might argue that understanding the abstraction is no harder than noticing the essential similarity between any two cases where this pattern arises and any good programmer should be on the lookout for that sort of thing. They should also be looking to communicate it to those maintaining code long after they have written it, and make that maintenance as simple as possible. Abstraction is next to cleanliness, as they don't really say.

Maybe...if one is going to talk loosely about "conserving structure" one might as well talk rigorously about it...if it isn't all that much harder. And when you do, there are probably some nontrivial things that fall out of category theory. No wonder the seemingly arcane area, once considered so obscure and abstract as to be useless, has made a charge up the Google n-gram leaderboard in recent times.

Still, I think most people would prefer to keep it a little wooly and merely recognize that we have an obvious identification between a doubly constructed type like List(List(3,4)) and one level down List(3,4), and that this identification needs to be carried over to morphisms - sorry functions. That is why you would probably write flatmap yourself as the need arose, but might not necessarily appreciate the similarity to ComputeThis(ComputeThis( blah )) or ParseMe(ParseMe( blah )) or AbstractMe(AbstractMe( blah )) and so on. Actually Option is kind of like a partial computation too. You can think of Some(x) and Some(Some(x)) as calculations in stasis, if you will, although the only thing that "remains" to be calculated is whether x exists or not. My goodness, it always does!

One might wax mathematical in the hope of achieving a higher state of monadicness. Perhaps, for example, we "understand" what MAP is doing because we root our intuition to pattern matching, kind of. If I tell you that g = (Some(x)=>Some(x*x+3)) you say, "Oh I get it, that is like x=>x*x+3 lifted up into Option[Double]." And if I tell you that h = (Some(Some(x))=>Some(Some(x*x+3)) you say, "Oh I get it, that is like x=>x*x+3 lifted all the way to Option[Option[Double]]." And you won't complain if I point out that g and h are the same, at least on some domain, because they are rooted in the same thing, the naked function x=>x*x+3. Perhaps the obviousness prevents us from seeing the top half of the second diagram independently of the bottom, however. It may seem odd that we have discussed monads in both programming and mathematics and I made only passing reference to flatMap, the built-in "bind" for Scala collections (defined here and here for Traversable and Iterable traits respectively). For another time, I guess.

Now ... can I have my repos back please?

## Comments