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!
