"Monad" that's a word you hear quite often these days. There is a lot of unjustified FUD whenever this word pops up. People seem to be downright scared about it. You can tell by the amount of rhetorical trick words people use to scare others away from trying to understand monads at all. "Academic", "no use in real world programming" etc etc. I find it quite frustrating to hear something like that even within the Scala community from time to time (even though this is getting rarer and rarer), since these are the "arguments" people bring up when they try to scare others away from Scala.
First of all, I'm not a category theorist. These things just fascinate me, and I enjoy reading about this in my free time. I'm your ordinary "Joe, the programmer" working at a small software company.
Still, I find these things useful in my day job. Why? Because as a programmer I'm building mathematical machines (namely software) all day long and these concepts help me to order my thoughts and make at easier to reason about my software and design stuff.
In this blogpost I want to show how to derive Monads from what you already know and give names to things you maybe never even thought about.
Categories
Since monads come from Category Theory we first have to define what a
category is.
A category
C basically consists of 2 sets
ob(
C) and
hom(
C) where we call
ob(
C) the
objects of
C and
hom(
C) the
morphisms of
C. Morphisms are maps that go between objects.
Never saw a
Category in your every day programming? Sure? There is a
Category called
Hask, its objects are the Haskell types and its morphisms are Haskell functions. So you can think about that in a Scala context:
Let
f be a function of type
Int => String.
Int and
String are both elements of
ob(
C) and
f is an element of
hom(
C).
There's more to a
Category, we need to be able to compose morphisms and there has to be a special element called
identity. Lets looks at composition first.
Let f and g be functions:
f: A => B
g: B => C
We can compose those 2 functions in Scala by using the
compose method to get a new function.
g compose f // yields a function of type A => C
OK, that's half the rent. Now we just need the special element called
identity which basically is a function that does nothing. It just takes a value and returns it unmodified. So when we
compose a function
f with
identity we get back a function that is equivalent to
f and it should not matter if we compose
f with
identity or
identity with
f.
In short: The following 3 functions are equivalent (which means: when fed with the same input values they will yield the exact same result)
f // A => B
f compose id // A => B
id compose f // A => B
Now we know that a
Category is (well, at least we know enough to start, a real category theorist can take you on a breathtaking journey from here :)). Let's move on!
Enter Higher-Kinded-Types
Next "scary word", but again: You use them all the time. First we need to know what a
kind is. We know what types and values are. You can think of them as levels. A value like
1 and
x => x (that's a function value, yes those are values too!) live a the value level while types like
Int and
Int => Int live at the type level. We group values into types.
true and
false are both values of type
Boolean (think of types as sets of values).
OK, if we group values into types, can we group types? Yes, we can! We can group types into… *drumroll* KINDS! Now we have a third level and our world looks something like this:
kinds
---------
types
---------
values
In most languages we only deal with one kind called
* (pronounced
type) that groups all types, but there are languages that allow infinite levels (I might cover one of them in future blog posts).
We now have a basic idea of what kinds are, so what are
higher kinded types? Like High-Order-Functions (functions that take functions as arguments and yield functions e.g. compose)
higher kinded types are
type constructors that take type constructors as arguments and yield types (or maybe even
type constructors).
"Wait a minute… are you talking about generics?"
Think about
List. It's not a type by itself, you need to feed it a type as an argument to get a type. This is called a
Type Constructor.
List takes one type and returns a type, hence
List has the kind
* -> * (this notation is borrowed from Haskell). The Scala notation for a
type constructor like
List is
List[_].
So a
higher kinded type looks something like this:
trait Functor[F[_]] where F could be a
List,
Option or any other
type constructor that takes one argument.
Functors
Now that we have
higher kinded types, let's take a look at our functions
f and
g from the beginning and lets add a
type constructor F[_] to the mix (this is Scala notation and means: takes one type and yields a type). We can now produce a whole new set of types with this higher kind (e.g.
F[Int],
F[String] etc.). We could now create functions that work with these types… hey I know this. This sounds like… a
Category! Yes, it is! It's actually a
Subcategory of our
Hask Category we introduced at the beginning. Let's call this new
Category D (so we don't confuse it with the
type constructor F). So elements of
ob(
D) would be something like F[A] and for
hom(
D) it would be something like F[A] => F[B].
Now wouldn't it be cool if there was a morphism between those two categories, one that preservers composition and the identity rule? Something that could map a function of type
A => B to a function of type
F[A] => F[B]? That's what's we call a
Functor, it's a morphism between categories.
"Why is this useful?" you might ask. Just think about the kind of code reuse you could achieve. Let's look at
Option as a concrete example. It's a
type constructor. So how do we map a function of type
Int => Int to a function of type
Option[Int] => Option[Int]? Can't you tell by now? The answer is the
map method of Option ;).
Let's check it out:
scala> val f = (_: Int) + 1
f: (Int) => Int = <function1>
scala> Some(1) map f
res0: Option[Int] = Some(2)
We could now reuse our function
f with
Option, there was no need to write a special version of
f that works with
Option.
The second ingredient we need to make our
Functor complete is a morphism that maps a value of type
A to a value of type
F[A]. In the case of
Option this is just the factory function:
scala> Some(_: Int)
res0: (Int) => Some[Int] =
scala> Option(_: Int)
res1: (Int) => Option[Int] =
scala> Option(1)
res2: Option[Int] = Some(1)
scala> Some(1)
res3: Some[Int] = Some(1)
Endofunctors
Now, let's assume that we want something like this:
scala> Some(1) map {
| case x if x % 2 == 0 => Some("YES!")
| case _ => None
| }
res1: Option[Option[java.lang.String]] = Some(None)
We want to use a function of type
Int => Option[String] with
Option's
map method. But what's that? We get an
Option[Option[String]]. That's stupid, now I have to unpack one
Option to get the result I actually wanted.
What happened here? Remember how we mapped a function of type
A => B to a function of type
F[A] => F[B] in the previous section about functors? What we did now is: we mapped a function of type
Int => Option[String] to a function of
Option[Int] => Option[Option[String]]. Yikes, we went a little bit over the top here, huh? We kind of like mapped something into an
Option and into an
Option this is how we ended up with an
Option[Option[String]]. You can think of this as a result of a composition of 2
Option Functors.
This is a special kind of
Functor that maps a category into itself and is called an
Endofunctor
Natural Transformations
Now that we have morphisms between objects of a
Category which are Scala functions and
Functors which are basically morphisms between categories it's time to introduce morphisms between
Functors.
Why do we need this? Well in the last example we ended up with an
Endofunctor (we mapped a
Category into itself). We need to get rid of one of the
Options. We do this with a morphism that maps the composition of 2
Functors F (
F composed with
F) to the
Functor F.
Lets do a concrete example that involves
List
scala> List(1,2,3) map { x => List(x + 1) }
res0: List[List[Int]] = List(List(2), List(3), List(4))
It happened again, but this time we ended up with a
List[List[Int]]! We now need a
Natural Transformation to join those lists together, this
Natural Transformation is called
flatten in Scala.
scala> List(1,2,3) map { x => List(x + 1) } flatten
res1: List[Int] = List(2, 3, 4)
List comes with a method that does both in one step, it's called
flatMap.
scala> List(1,2,3) flatMap { x => List(x + 1) }
res2: List[Int] = List(2, 3, 4)
This enables us to chain functions together in a very convenient way.
scala> Some(1) flatMap { x => Some(2) flatMap { y => Some(x + y) } }
res3: Option[Int] = Some(3)
or a little more concise
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res4: Option[Int] = Some(3)
Monads
This is actually what makes up a
Monad. It's an Endofunctor with two
Natural Transformations called
unit and
join (which is called
flatten in Scala). They are such a fundamental concept that Scala features a syntactic sugar for them, the
for-comprehension. Do NOT confuse this with a mere
for-loop, this is a different animal. The last example above can be written in the following way:
scala> for {
| x <- br="" some=""> | y <- br="" some=""> | } yield x + y
res5: Option[Int] = Some(3)
//translates to
scala> Some(1) flatMap { x => Some(2) map { y => x + y } }
res6: Option[Int] = Some(3)
Conclusion
This is an introduction on how to think about
monads and how to derive them from simple building blocks. They are a very powerful abstraction that pops up all the time. You use them all the time without knowing. Since programming is all about abstraction it's useful to recognize those underlying patterns. Don't let others fool you into believing that this is just some bizarre functional stuff that has no use in the real world. This is just the tip of the iceberg, an amazing journey lies ahead. Let's learn!
