We all know that programming is based on math, what is perhaps not so clear is that knowing more math is going to help us become better developers. And although in all types of programming, math is fundamental, it is even more so in functional programming.
A very widespread concept which I’m sure you have heard lately is the monad. It is a mathematical concept of the category theory applied later in functional programming.
I first heard the term when I started programming in Scala. After much searching on the Internet, I only found articles explained by and for mathematicians or articles that talked about programming and not math. On the other hand, some abuse of language is done to refer to things that are not monads as such. So we will try to talk here, without losing the mathematical rigor, about what the monads are, and then how and why they will help us become better developers. Although they are very abstract and complex terms we will try to do it all in a simple way.
In order to understand the monads, we must first learn about two concepts, categories and functors.
Categories
Let’s start with an example:
Imagine that we have obtained the following map of the Middle Earth of the Lord of the Rings. Elves have made it.
What do we see on this map?
The first thing we see is a few towns. In addition, we have roads that connect each of the towns, as well as themselves (identity). These are one way or one way back. Also, as seen on the map, you cannot reach every town (Who would want to go to Mordor? Oh, that’s right… hobbits…). On the other hand, it seems clear that if Frodo wants to go from The Shire to Erebor, he can go first through Rivendell or he can go directly to Erebor.
This is a category. Mathematically speaking, it has two components:
The first, a set of sets (the set of towns on Middle Earth)
The second, a type of functions/arrows that are called morphisms (the roads that connect the towns). In addition, we can compose the morphisms (as in the previous Frodo example) and this composition is such that any morphism composed with the identity is equal to morphism¹ and such that the composition is associative².
Functor:
Imagine now that we find another map, this time the map of the Seven Kingdoms of Game of Thrones.
Again, we have towns and roads linking these towns. That is, we have another category.
Look at the roads that link each town. Can you find some similarity? For example, is there any town that no one wants to go to? Of course, who would want to go to Meereen? Nobody!
Another example is that there is a town that can be reached from all other towns. Look, at the Middle Earth one too!
In fact, it has so many similarities we could say that if we change names and distances, it is the same map (in mathematics it is said to have the same structure and, in the real world, we say George R.R. Martin was “strongly inspired” by the Tolkien’s work)³.
Seeing this, it is clear that we should be able to transform, the map of the Middle Earth in the Seven Kingdoms, but … how?
The first thing we have to think about is a transformation the towns, in this case:
The last thing we have to do is transforming the roads:
A very important thing about this transformation is that it preserves the structure, including the composition: Frodo going from the Shire to Erebor (optionally going through Rivendell) would be similar to a trip made by John Snow from The Wall to King’s Landing (also optionally passing by The Eyrie).
We can say that this transformation… It’s a Functor! In this way, we have been able to transform “completely different” worlds, exactly what the category theory in mathematics was created for: to build bridges between very different fields.
Monad:
Now we have found another map of the Middle Earth, but this time, drawn by a Dwarf.
Of course, the Middle Earth is the same, so it must have (and has) the same populations, and the same roads. Of course with so many maps, it would be difficult It to get lost …
As it is essentially the same map, it is clear that we can also construct a functor or a transformation of the Middle Earth itself, which is the same. This special type of functors is known as endofunctors.
But there is more. If an endofunctor also fulfills that it has two natural transformations such as the identity function and another function that is associative, we can say that we have a monad (this we call monadic laws)⁴.
Monads in functional programming
History:
Philip Wadler, who is the greatest contributor to the theory behind functional programming and the use of monads, was inspired by the use of Eugenio Moggi’s monads to give semantics to programming languages. The monads introduced the idea of sequence into the functional paradigm, but without contradicting it, thanks to the composition of functions.⁵
Many common programming concepts can be described in terms of monad structures, including side effects, I/O, exception handling…
This allows such concepts to be defined in purely functional ways without the need to add new terms to language semantics and without resorting to imperative programming. There are languages like Haskell that provide monads in the standard kernel and, although Scala does not provide it in the kernel, you are familiar with Cats and Scalaz libraries that help us develop with monads (although we can always implement our own).
Functors and monads in FP:
It has been nice explaining how the category theory in mathematics works but, as developers, we already want to see an example applied to functional programming:
This drawing⁶ represents a functor, in this case, composed of List and map. Surely you have already linked this example with the one of the Lord of the Rings and Game of Thrones´s functor.
You may have read online that List is a functor per se, just like the Scala Option class is a monad. Both are type constructors (that would be equivalent to the transformer of towns) but… where is the transformer of roads/arrows? This is a very frequent abuse of language that you will no longer see with the same eyes.
If in the previous drawing we had used flatMap instead of map (flatMap’s output is in the same category), we would have drawn a monad (although we need to check the monadic laws) instead of a functor.
There are many reasons to use monads in our programs, but I will list the top 3 main reasons (in my humble opinion) to use them:
At the end of the day, we only want to use functions (remember: functional programming).
-
Imagine that you have a program that performs these two functions:
f(x) = x+3
g(x,y) = List(x, y)
We want these two functions to be executed in order, sequentially, and we want to do it using only functions. So, how could we do it? Using composition of functions. If we first want to execute g and then f on the result, we compose the functions in the next way: f ∘ g (x, y).
If instead of the previous g, we use g(x, y) = x / y, we have two problems:
If the type that accepts f is different from the one that returns g (g could return a float since it is a division, and f accepts an Int) we would clearly have a problem.
What would happen if the function g passed the values 2 and 0? Indeed, there would be a failure since it can not be divided by 0. We do not want exceptions in functional programming since an exception is not a function.
What I mean is that the composition of functions needs one more ingredient to be 100% functional (this ingredient will also solve the two problems above). This ingredient, obviously (judging by the title of the post ;)), is the use of monads.
The idea is to allow functions to return two types of results, so g would no longer be: g: Int, Int → Float, but we would do that g: Int, Int → Some | None and f(x): Some | None → Some | None.
For example, we are going to undo the functions with the previous example:
def g(x: Int, y: Int): Option[Float] = {
y match {
case 0 => return None
case y => return Some(x.toFloat/y)
}
}
And the same with f(x):
def f(x: Option[Float]): Option[Int] = {
x match {
case None => None
case Some(x) => Some(x.asInstanceOf[Int]+3)
}
}
So our code would be g(x, y).flatMap (x => f (Option (x))). In this way, we have composed the two functions and avoided the exceptions, since if y is equal to 0 the result will be None.
Summary and conclusions
In short, we can say that a monad is an endofunctor which holds monadic laws. We can also say that thanks to the monads, we can compose functions, solving type problems and exceptions.
Now that we know the category theory a little better and how some of these concepts are used in functional programming, we can use the tools provided in our programs to make a better code.
Go, you can already tell your friends “I’ve seen things you people wouldn’t believe”.
Notes
1. That is, if Frodo goes from The Shire to Erebor (f) and then stays in Erebor (identity) is the same as if he goes directly to Erebor.
2. That is, if we take five paths, for example that one which goes from The Shire to Erebor (f), that one which goes from Rivendell to the Shire (g), that one which goes from Mordor to Rivendell (h), that one which goes from Rivendell to Erebor (j) and that one which goes from Mordor to The Shire (k). Then (f ∘ g) ∘ h = f ∘ (g ∘ h) since f ∘ g = j and g ∘ h = k.
3. Obviously, the paths of these maps are carefully invented so that everything fits perfectly.
4. Monadic laws with composition operation:
F ∘ id = F (Left identity)
Id ∘ F = F (Right identity)
(F ∘ G) ∘ H = F ∘ (G ∘ H) (Associativity)
5. De Euclides a Java — Ricardo Peña Mari
6. Based on Nikolay Grozev’s one
Resources and links
The Juan Pedro Villa-Isaza’s work around applications of category theory in functional programming
Wikipedia’s articles on category theory and monads
A work about programming history: De Euclides a Java — Ricardo Peña Mari
*This post originally appeared on Datio’s Blog on June 26, 2017.
Top comments (0)