"What's a Monad?"

[jducoeur]

This one is mainly aimed at programmers, but I'm trying to teach a bit of programming, so it's not just for the FP geeks. (This is basically a bit of Functional Programming 101.)

In a comment on my earlier post, cellio asks what a Monad is. It's one of the most fraught questions in modern programming, but let's give it a stab. Bear with me -- this takes some explaining, and I am trying to avoid The Curse of Lady Monadgreen. This will be a practical description, rather than a precise formal one.

First, Functors

Let's consider several data types that we find in Scala. (And many other languages as well, often under other names, but I'm going to use Scala for my examples since it's what I know best. The concepts here are very general, but some languages express them better than others.)

On the one hand, take val o: Option[T]. This means that o is a box that may or may not hold a value of type T: o is either Some(t) or None. It's kind of like the idea of being able to be null, but much more principled. (Many languages use this either instead of null or provide it as an alternative.)

Next, let's look at val l: List[T]. This means that l is a box containing as many Ts as you want (possibly zero) with a specific order. (As opposed to Set[T], which has no intrinsic order.)

Finally, let's take val f: Future[T]. This one doesn't exist in as many languages: it basically says that f is a box that will eventually contain a T, assuming all goes well. (If all does not go well, it will eventually contain an error.) It's a good way to deal with asynchrony in programs, and can replace locks and callbacks and other such hell in many cases.

These types are all Functors. This means that they have a method called map(), which means "do the following transformation with every element in me". So for example:

• o.map(x => x * 2) -- if o is, say, Some(5), this will return Some(10). OTOH, if o is None, the result will still be None.
• l.map(x => x * 2) -- if l is List(1, 2, 3), this will return List(2, 4, 6).
• f.map(x => x * 2) -- this returns another Future; if f eventually contains a 6, the resulting Future will eventually contain 12. And if f eventually returns an error, this resulting Future will contain that same error.

So the concept of a Functor[T] is that it is a box that contains "T-ness" in some fashion. You can transform the T's inside of it, getting another of the same kind of Functor with the transformed values.

Functors to Monads

All Monads are Functors, but with an additional kick: there is a sensible way to nest them. All of the above types are also Monads, and their Monad-ness can be expressed in for comprehensions, like the following.

val maybeUser: Option[User] = ...
val maybePhone: Option[PhoneNumber] = for {
  user <- maybeUser              // Option[User]
  profile <- user.maybeProfile   // Option[Profile]
  phone <- profile.maybePhone    // Option[PhoneNumber]
}
  yield phone

(I generally find it helpful to pronounce the <- arrow as from "in". So the first line of that for comprehension reads roughly "for each user in maybeUser".)

What the above is saying is:

• I may have a User.
• If so, put that User in a value named user.
• If that user has a value in maybeProfile, put that in profile.
• If that profile has a value in maybePhone, put that in phone.
• If all that worked, return the phone number.

We are able to nest values or functions of type Option, and get another Option out at the end. If any of those steps returned None, then we get None out the end.

Next, let's do the same with List:

val regions: List[Region] = ...
val allCustomers: List[Customer] = for {
  region <- regions              // List[Region]
  dealer <- region.dealers       // List[Dealer]
  customer <- dealer.customers   // List[Customer]
}
  yield customer

This is saying:

• Start with a List of Region.
• For each of those Regions, get all the Dealers.
• For each of those Dealers, get all the Customers.
• Return all of those Customers.

It's the same concept: there is a logical concept of nesting. More importantly, there is a specific way in which you nest: in the case of nesting Lists like this, the results will all be concatenated together: the Customers for each Dealer in order in the resulting List, and all of the ones from Dealers in the same Region together.

Finally, let's try Future:

val userId: String = ...
val profileFut: Future[Profile] = for {
  user <- userDb.loginUser(userId)              // Future[User]
  prefs <- preferenceService.getPrefsFor(user)  // Future[Prefs]
  avatar <- photoService.getAvatarFor(user)     // Future[Photo]
}
  yield new Profile(user, prefs, avatar)

Each step in this case is a function that returns a Future. Putting it together:

• First, try logging in with the given userId, and get back a box that should eventually contain a User.
• Once we have that User, get a box that will eventually contain their Prefs.
• After we have fetched the Prefs, get a box that will eventually contain the user's Photo.
• When we've obtained all of that, assemble a Profile out of it.

Again, we are nesting these operations, and again, Future imposes some details: these steps will be conducted in order, each one starting after the previous one has finished, and if any step returns an error, everything after that will fall through and return that error instead of trying to continue.

Note that each kind of Monad knows how to combine with itself. That doesn't mean that they can easily combine with each other -- there are sometimes ways to combine different Monads in sensible ways, but it's a bit ad-hoc: not all combinations make sense.

Conclusion

So those are the high concepts. A Functor is a sort of box that contains "T-ness", where you can transform the Ts inside of it. A Monad is a Functor that has specific rules for how it can be nested within itself.

And yes, the names are weird. They come from Category Theory, a branch of abstract mathematics that turns out to be really useful for serious programming. The video linked from my previous post includes the legendary line, "a monad is a monoid in the category of endofunctors": literally true and correct in Category Theory terms while being utterly useless for actually understanding anything.

Anyone who wants to dig into this a little should pick up the delightful book How to Bake Pi, a fairly slim, Kindle-friendly book that teaches Category Theory in terms of baking: each chapter starts with a recipe, and then shows how that recipe relates to a mathematical concept. It doesn't teach programming per se (and requires no background in either math or programming), but it provides the underpinnings that this stuff all grew out of. I found it invaluable for getting comfortable with this stuff.

For the actual programming concepts, including Functors, Monads and other such fun types, I currently recommend the documentation for the Cats library -- the Cats community has taken documentation really seriously, and the documentation of each type does a delightful job of exploring why that type works the way it does. It is aimed at programmers, though -- I wouldn't recommend coming into it completely cold.

Hopefully folks will find this at least a little helpful. Questions welcomed...

Comments

[fredrikegerman]

Congratulations, you have written the obligatory monad tutorial, which seems to be a rite of passage for everyone who ventures into Monadery. I was no exception...

[jducoeur]

Heh. It's actually something like the fifth time I've done so -- I've been a semi-professional Scala trainer for the past couple of years, so I explain this one fairly often. (Albeit usually with a lot more editing time than the above...)

[metahacker]

I keep wanting article #2 in this series: "WHY are monads?"

If you need fodder for future articles. Like, since most things we write are monads, why is it important that we know they're monads? What do we commonly write that *isn't* a monad? what about that isn't a functor? When would you write those instead? What other useful categories are there, and what is their use?

[jducoeur]

Actually, that one's fairly easy: you want a Monad when it makes sense to nest things like this. Indeed, my traditional handwave explanation is that, if you find yourself wanting a for comprehension like the above, and can describe exactly how it would work, you're about 3/4 of the way to being able to write the Monad in question. (That's how I learned it in the first place.)

More precisely, Monads are a formalism for a *sequential* type, where you need to deal with the first value, which gives you enough to compute the second, which gives you enough to compute the third. That's as opposed to Applicatives, which describe a *parallel* type, where you can compute two values separately and then combine their results together.

But I don't really plan on talking about that a lot here: mostly, that sort of stuff goes into my professional blog instead, and that's mostly focused on Dotty at the moment. I only did the Monad tutorial here because Monica asked, and I'm pretty practiced at teaching the subject by now. (This is actually a *highly* compressed version of a training module that I wrote for corporate use...)

[cellio]

Thank you. The "sequential type" idea is new and I see the utility of that. (The goofy names are obfuscating factors for me. I should not need a graduate degree in math to understand programming concepts.) Functors, though, seem quite obvious; as I was reading I was thinking "yeah, so, this is just map()... what's the big deal?". Does that mean I missed something, or is that just background? (Though I grant that Future is a neat and novel concept that would make lots of ugly async code become more comprehensible.)

My first real programming language (as opposed to "used in university for classroom-sized projects") was LISP. That might have warped me. :-) I think of LISP as a functional language (I realize it can be used in other ways), but I don't think I'd ever heard the word "monad" until sometime in the last few years.

[jducoeur]

The goofy names are obfuscating factors for me. I should not need a graduate degree in math to understand programming concepts.

Yeah, that's a common complaint. It's somewhat a historical artifact: these ideas came into programming via category theory enthusiasts, who said "We should be able to use these great concepts in our programs!", and used the terms they were used to. We've sometimes discussed changing the names to something more intuitive, but by now the jargon has largely permeated the community, so we've gotten used to it.

(It's actually worse in some places, though. There are two competing category-theory libraries in Scala -- one of them not only uses the math terms, it favors the math *symbols*, so some programs look like something out of a textbook, which is great if you really grok the math and terrible if you don't. The other library has deliberately avoided getting as symbol-heavy, on the grounds that it's an unnecessary barrier to entry, and in general I think the Scala community has gotten more leery about Extreme Unicode in programs.)

as I was reading I was thinking "yeah, so, this is just map()... what's the big deal?". Does that mean I missed something

Nope, Functor really is that simple. It's just that the *abstraction* of map() turns out to be surprisingly useful -- there are many higher-order functions that you can then write for *any* Functor, so it's very useful to have the common concept.

Similarly, Monads are (as is alluded to in the original video) largely a fancy term for "types that have flatMap()", which is what is actually going on under the hood in those for comprehensions above. flatMap() is similar to map(), but means "map() over all the elements *and* flatten the resulting nested data structure". That notion of "flattening" makes sense in some data types, but not in others -- if it does make sense, you probably have a Monad.

And again, there are tons of things you can then do with *any* Monad, which turns out to be *hugely* useful. For example, there's a common pattern in modern Scala called "Tagless Final" (again, sorry for the jargon), which is where you write code that can run with any Monad -- the type of Monad gets set by the code calling it. So at runtime you can use something complex and asynchronous like Future (more or less -- Future is actually a little badly-behaved, but that's a different topic), but for unit testing you instead use a synchronous Monad that is easier to work with.

Though I grant that Future is a neat and novel concept that would make lots of ugly async code become more comprehensible.

Yeah -- it's one of the many reasons why writing browser code is actually easier in Scala.js than in native JavaScript. Composing complex AJAX operations is *vastly* easier with Futures than with callbacks. (Enough so that JS has now picked up a similar concept, which they call Promises.)

I think of LISP as a functional language (I realize it can be used in other ways)

No, that's entirely fair -- LISP was the first reasonably popular functional language (maybe the first functional language, period), long predating most of the rest. It's less fancy than something like Haskell, but the central concepts are there.

I don't think I'd ever heard the word "monad" until sometime in the last few years.

Yeah, I didn't really encounter it myself until I started getting serious about Scala in 2012, and I don't think I really *understood* it until about 2015 or so. The concept and term have existed for decades in the math world, and it's been around in the hardcore FP community (that is, Haskell) for a while, but it's only really started to permeate the wider programming community recently.

Although, that said, it shows up in unexpected ways. C#'s LINQ system, although syntactically based on SQL, is roughly a general framework for creating and using Monads, with a very different look-and-feel. This general notion is useful enough that folks are finding ways to leverage it...

[mindstalk]

> LISP was the first reasonably popular functional language (maybe the first functional language, period), long predating most of the rest.

Hell, it was the second high-level language, period, after Fortran but before COBOL.

Depends on how you define functional language, but I think from the beginning it let you pass around and manipulate functions -- "first class data type" -- which is pretty core. And had recursion and recursive data types, though it wasn't until the Scheme dialect that someone insisted tail calls be efficient.

[cellio]

On further thought... as you've described it, isn't a monad ("sequential type") basically syntactic sugar around &&? That is, if you write A && B && C and A is false, you stop, or if A is true but B is false, you stop. I said "basically" because it's not strictly boolean with the None stuff and Futures are their own oddity, but from 20,000 feet, is this a fair comparison or have I missed something fundamental?

[jducoeur]

There's a fundamental difference, but it's a little subtle.

The key notion of Monads is this nesting thing. It's sequential, but what it is really expressing is *dependency*. That is, you have to compute a value of A first; once you have that, you can compute B. Once you have a value of B, you can compute C.

In that respect, it's actually quite different from A && B && C, because those values are *independent* -- the value of A doesn't affect the value of B. Intuitively, I think && is an applicative operator, but I'm not sure whether it follows all of the relevant rules. Roughly speaking, Applicative means "compute the elements independently, then combine their values into this type".

Yes, you're combining values in &&, but the value of B itself doesn't depend on the value of A. If you look at the Monad examples above, in each of them we're computing the "inner" values based on the "outer" ones. (Well, mostly -- the Future example actually shows one where you *could* do the operations in parallel; it's arguably a bug, or at least an inefficiency, that we're doing them strictly in order. Scala just happens to make it easier syntactically to do it this way.)

Really, I should have described this as dependent vs. independent in the first place (I often do), but that didn't occur to me when I was writing this up...

[cellio]

Oh, *dependency*. Yes, that makes sense. And also, I don't know that compilers *aren't* allowed to evaluate operands in whatever order they want; maybe A && B doesn't get evaluated in that order. (I guess one could find out by using expressions that have side effects, but... *shudder*.) I think you're right that "dependent" is a better description than "sequential", at least based on the vast understanding (cough) I've gained from reading this. :-)

[jducoeur]

I don't know that compilers *aren't* allowed to evaluate operands in whatever order they want; maybe A && B doesn't get evaluated in that order.

Excellent guess! Yes, in fact modern compilers are prone to rewriting code routinely if they have reason to believe that doesn't affect the semantics. And then the JVM does the same thing based on its runtime data. Moreover, modern *chips* are prone to doing the same thing with the compiled code, rewriting the assembly to squeeze out a few microseconds here and there.

This is part of what makes multi-threaded code fiendishly difficult and fraught: there are things you can do that *look* completely sound, but allow the microcode to perform rewrites that make perfectly good sense from a single-threaded perspective, but totally break the semantics when multiple threads are interacting. Worse, these bugs are *incredibly* difficult to find and debug, because they will often arise only once in a million runs. So building multi-threaded code correctly is *weirdly* complicated, involving more contortions than you would expect at first glance.

And this, in turn, is one of the beauties of the Futures approach -- it isn't nearly as susceptible to those bugs as traditional lock-based approaches.

[cellio]

And this, in turn, is one of the beauties of the Futures approach -- it isn't nearly as susceptible to those bugs as traditional lock-based approaches.

But the complexity still has to go *somewhere*, right? It moves away from the programmer, it looks like, but that presumably increases the burden on the compiler or execution engine or whatever to get it right. *Somebody* has to unravel all the multi-threaded async crud, right? I mean, it's great that it's not me, but it's not free either, right?

Granted, concentrating the bug exposure in the compiler instead of distributing it among all programmers means that when a bug is found it's more likely to get fixed and benefit everyone. I'm not sure I'd want to be on the team that has to make that work, though. :-)

[jducoeur]

I mean, it's great that it's not me, but it's not free either, right?

Also absolutely correct.

This shows up best in the Scala world in the form of "lazy val" -- basically, a value that will be computed the first time somebody tries to access it, and is then a constant from then on. Seems easy, right? Folks (including me) litter their code with these things -- it's a core piece of the language.

But in fact, doing this *correctly* -- such that it works in a multi-threaded environment, with confident guarantees that it will only run once, without deadlocks, as efficiently as possible -- is *crazy* difficult, so much so that this language construct has been re-implemented several times over the past fifteen years, and we still don't have it quite right.

If you'd like a sense of just *how* crazy it is, see this proposal to get it entirely right. It's daunting.

Granted, concentrating the bug exposure in the compiler instead of distributing it among all programmers means that when a bug is found it's more likely to get fixed and benefit everyone. I'm not sure I'd want to be on the team that has to make that work, though.

Yep. This is why many of us are deeply grateful to the folks who make the compilers hum along, hiding many of these nasty details under the hood so that we can peacefully get along with our application programming.

[mindstalk]

> maybe A && B doesn't get evaluated in that order.

Depends on the language, but part of the point of C && is that it is order-dependent, as you said in your earlier post. If A is false, B isn't evaluated. Short-circuit evaluation.

[drwex]

This explanation raises a lot of questions that are likely nitpicky and would certainly make it longer. But I come out of this with effectively no more knowledge of "what is a monad" than I went in with.

I can't tell from this what's "mondad"-ness and what is "Scala"-ness. Like, it appears all your constructs have, effectively, error and null handling built in. Is that a property of Scala things or of monad things?

You have some capital "S" that make me want to ask whether that's a typo, a feature of the fonts you used or some attempt to call my attention to some notion of plurality.

You use "..." and I can't tell if that's a legal thing in your language or something you're using to avoid having to write out code that isn't relevant to the point you want to make.

You use "functor" which I see is linguistically similar to "function" but I'd have to look up what the difference is. Since all functors are monads (you say) I want to know that relationship, particularly since you use "function" once, in the very middle of everything.

I have a sneaking suspicion you could drop all the words about Futures which appear to be a neat thing you like and are using but aren't actually important to explaining what mondads are. If they have some importance in particular I failed to grasp it, sorry.

You talk about order in a somewhat incomplete way. I mean, all lists are "ordered" by definition but you seem to mean something else and maybe something more specific. And again I can't tell if this ordering behavior is a monad-think or a Scala-thing or just a neat thing you want to tell us about.

[jducoeur]

Lessee --

Null handling: broadly speaking, not a thing in Scala. Idiomatic Scala shuns nulls pretty religiously: indeed, the whole point of Option is that it replaces the concept of null with something better-typed. While nulls can't be entirely ignored (they show up when you interoperate with Java/JavaScript, and occasionally at other times), the policy is to scrub them out on contact, so the rest of the code doesn't need to deal with them. So yes: that is very intentionally ignored, as a matter of proper design.

Error handling: the Option example *can't* have exceptions -- there's just nowhere in that code for them to crop up. Ditto for the List example. In the case of Future, they get bundled *into* the Future. I didn't take the time to explore that in detail (since it's off-topic), but basically you attach a "recover" handler to your Future, which means "if the following Exceptions arise, do the following". It's basically the same as try/catch (in Scala and many other languages), but asynchronous.

You have some capital "S" that make me want to ask whether that's a typo

I suspect the ones you're looking at are just a font illusion: they're lower-case, but lower-case Helvetica at the end of an otherwise Courier word looks weird.

You use "..." and I can't tell if that's a legal thing in your language or something you're using to avoid having to write out code that isn't relevant to the point you want to make.

The latter. (Although ??? *is* actually literal Scala -- it's a function that throws a NotImplementedException, and is delightfully useful.)

You use "functor"

Like I said -- it's math jargon. (Not my fault.) It *is* semantically related to "function", but the relationship is fairly complex, having to do with the way types relate to each other.