Introduction
If you’re like me, one of the first thoughts you had when you started at Rally was something along the lines of “what the hell is a monad?” You then Googled the term and found yourself deep down the rabbit hole of abstract math, wrapped up in functors and monoids and categories to the point that you don’t even remember the original question. This can be quite overwhelming if you’ve never set eyes on a functional programming language before, but fret not! I’ve read through pages of dense math and watched hours of lectures on the topic so you don’t have to, and I will set out to summarize the topic here, and furthermore provide ways to apply it so that you can start thinking (and writing) functionally today.
This post is aimed at any engineers who consider themselves “new” to the functional scene -- whether that be in Scala, Haskell, or otherwise. By the end you should be a bit more comfortable defining the basics of category theory, and identifying those principles in the wild. Also, if you’re ever out drinking with a theoretical mathematician, refrain from quoting any of this directly. More often than not there is more to these concepts than what I mention here, but for programmers like us this is sufficient.
The Basics
So what is a Category and how is it related to programming? Like many things we deal with as programmers, Category is a fancy name for a pretty simple concept: a labeled, directed graph with some extra constraints. In a Category each of the nodes is called an object, and each of the edges is called a morphism.
As alluded to before, not all directed graphs are Categories, there are some extra criteria that must be met. Consider the image to the right, note that each object has a morphism pointing at itself. This is the identity morphism, and each object requires one for a graph to be considered a Category. Next, see that the object A has a morphism f that points to B, and likewise the object B has a morphism g that points to C. Since there is a way from A to B and B to C, there is clearly a way from A to C, right? This is the next requirement of a Category, morphisms must be able to be composed associatively, or for morphism f: A => B and g: B => C there exists a morphism h = g(f): A => C.
This might already be feeling a bit nebulous, so let’s take a look at an example of something that fits this definition in scala.
trait Rock trait Sand trait Glass def crush(rock: Rock): Sand def heat(sand: Sand): Glass
Looking at this I think the relationships become a bit simpler. Crushing the rock into sand is the morphism that transforms the rock object into the sand object, and heating the sand up to make glass is the morphism from sand to glass. The composition of these relationships should clearly then be
val glass: Glass = heat(crush(rock))
The identity functions also exist (defined in Predef in Scala), as for any object you can easily write a function that returns that same object. Therefore, this system is a Category, albeit a rather simple one.
Diving Deeper Into Categories
We’re going to dive a little deeper into some of the terminology now, starting with the category known as Magmas. Whether you know it or not you’re already intimately familiar with the underlying concept -- a magma is nothing more than a binary operation, or an operation that combines two values to create a new value. For the sake of any beginners reading this I will not go into the proof that the set of all binary operations is in fact a category, but for those interested Bartosz Milewski dives into that in his blog here. Any arithmetic from addition to multiplication live in sub-categories under the magmatic category (diagram to the right).
The order of inheritance here is as follows:
- Magma: all binary operations
- Semigroups: all binary operations that are associative
- Associative: order of evaluation does not matter.
- Monoids: all binary operations that are associative and have a neutral element
- Neutral Element: a value that, when combined with another value, returns that value (aka the identity element)
So to our earlier example, both addition and multiplication are monoids as they are associative (a + (b + c) = (a + b) + c) and have an identity element (a x 1 = 1 x a = a). The final bubble in our diagram is for quasigroups, which is not necessarily nested the same way as semigroups or monoids. Quasigroups are binary operations that are invertible, which is not quite as simple to explain so I’m going to refer to Mark Seemann’s series on the matter: a binary operation is invertible when for any values a and b, there exist values x and y that can transform a into b. Sounds complicated, sure. To help understand what this means let’s consider subtraction, as illustrated in that same blog post:
val x = a - b val y = a + b assert(a - x == b) assert(y - a == b)
Note that y is not itself subtraction, this still counts. The objects in a category are abstracted and can be virtually anything, what matters is that for any a and b that could possibly be generated those assertions hold true.
Types In Context
Regardless of specific discipline, the subject of types is something that should be comfortable for anyone familiar with programming in the form of data types. Int, bool, float, so on and so forth -- all types, but if you were to put it into words how would you describe the platonic ideal of a type? In his blog-series-turned-textbook Category Theory for Programmers, Milewski describes them as simply “sets of values.” For example Boolean is the finite set containing the values “true” and “false,” Char is the finite set of all alphanumeric characters, and String is an infinite set of Chars.
Problem is, in category theory we want to step away from sets and instead think of things in terms of objects and morphisms, but the fact that types are ultimately sets simply cannot be escaped. Luckily for us these sets still have a place in category theory, as our objects are abstractions and can represent anything. Therefore there is nothing wrong with saying our objects are sets, and it becomes possible to think about our Scala programs as categories where the types are objects and the functions are morphisms. This may seem painfully obvious to many, after all the notion of an object is something we’re used to in Scala, but it is worth stating explicitly.
If you’ve worked with an OOP language like Java recently you are more than likely familiar with the concept of generic types. Something like LinkedList
For an example of functors, let’s consider the Scala Option[T] type combined with our earlier rock/sand/glass example:
val rockOpt: Option[Rock] = Some(rock)
What we have above is Rock type as we defined it earlier but it’s wrapped in an Option. This is a generic type (and much more, we’ll get into that later) and it tells us that this object is either the specific thing we’re looking for or it is None, which would be comparable to null in other languages.
Without using functors, we could imagine applying our crush() function to the underlying Rock would require using an if statement to handle the possibility of the Option being None.
var sandOpt: Option[Sand] = None
if(rockOpt != None) {
sandOpt = Some(crush(rockOpt.get))
}
This is kind of an aside but please don’t use var, this is bad Scala code for multiple reasons. Anyway, back to the point -- in Java or C# this wouldn’t be an issue, you check if your value is the type you expect and you do what you want with it. However, with the power of functors, we can do this quite a bit more elegantly with the map() function:
val sandOpt: Option[Sand] = rockOpt.map(crush)
Boom, one line and we have it. You might have been able to make the first example one line by using ternary operators or something, but you couldn’t get it this short. It’s really wonderful in its simplicity. So what is happening here is map() is taking a function and mapping (in the mathematical sense) that function onto itself. The structure of the Option is preserved, but now it contains either Sand or None instead of Rock or None. Illustrated, it looks something like this:
Notice how everything lines up, every object and morphism is preserved in both systems, therefore in this case the morphism in the center is the functor that represents the mapping from T to Option[T].
Putting It Together
Now we can get back to the original question “what the hell is a monad?” There is an answer you’ll stumble across eventually trying to blindly Google the answer, and that is a monad is just a monoid in the category of endofunctors usually followed by a not-so-slightly sarcastic what’s the problem? This is mostly a joke answer people throw around to illustrate how complicated things are in this topic, but it’s not really that complicated, we’ve already worked out what these words mean so let’s go through step-by-step and decipher this.
First, we know that monoids are associative, binary operations that contain a neutral (identity) element. Second, we know endofunctors map categories onto themselves in a way that preserves structure. That means, in plain English, that a Monad is simply some wrapper type (like we saw before with generics) that supports some method of taking a function and using it to transform itself. List is a monad, Option (like we looked at before) is a monad, and depending on who you ask Future is a monad as well. Example:
val l: List[Int] = List(1, 2, 3) def f(i: Int) = List(i, i*2, i*3) println(l.flatMap(f)) // output: List(1, 2, 3, 2, 4, 6, 3, 6, 9)
Deceptively simple, right? At the very least it shouldn’t feel quite as hard to pin down, even if the usefulness of such a concept isn’t immediately clear. It’s abstract by nature, which doesn’t make it any easier to explain, and may lend to some of the misconceptions surrounding it. In the next part we’ll get into some real-world examples of these things, which I believe will illustrate further that they are extremely powerful and actually pretty common.
More Material
The entities and logos identified on this page may have trademarks and those trademarks are owned by the respective entity.
