Sonntag, 10. Juli 2011

From Functions to Monads in Scala

"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!

Kommentare:

Sébastien Bocq hat gesagt…

Excellent! Thank you!

Heiko Seeberger hat gesagt…

Nice write-up, thanks. I have some comments, though:

Call me picky, but categories are not necessarily restricted to sets, but more generally to collections of objects, which could also be classes. Not too important for computer science, though.

In the functors section there is a typo: It should be "... and for hom(D) it would be ..."

fmap (aka map) is all a functor needs. If you add the "factory" function pure (aka unit aka ...) you end up with a pointed functor.

In my opinion your explanation of endofunctors is misleading: You are still mapping from category C to category D. In your example Int => Option[String] is an element of hom(C) (with Int and Option[String] elements of ob(C)) and Option[Int] => Option[Option[String]] is an element of hom(D) (with Option[Int] and Option[Option[String]] elements of ob(D)).
Well, as D is a subcategory of C you have indeed an endofunctor, but that's true of every functor in a program, because they will always deal with types and functions, right? Therefore "your" endofunctor is not that special ...

xRaich[o]²x hat gesagt…

Hi Heiko,

Yes, you are absolutely right. Endofunctors are indeed not THAT special in this situation (http://stackoverflow.com/questions/3273373/are-all-haskell-functors-endofunctors). I just wanted to point out what they are since monads are sometimes explained as "Endofunctors with 2 Natural Transformations" (I also left out monoids etc.). I find them to be quite a good vehicle to explain what's happening. Of course others might think different about this.

Being picky is a good thing ;) Keeps the mind healthy.

Regards!

Julio hat gesagt…

Nice post, thanks. Is there a book or article you would suggest for those who woule like to learn more about this subject?

xRaich[o]²x hat gesagt…

@Julio: The Haskell Wiki http://www.haskell.org/haskellwiki/Haskell has a lot to offer about this topic.

Regards!

tuxslayer hat gesagt…

>> elements of ob(D) would be something like F[A] and for hom(F) it would be something like F[A] => F[B].

you meant hom(D)? :)

xRaich[o]²x hat gesagt…

@tuxslayer: Thank you. Fixed ;) Heiko already pointed that out but I somehow always forgot about it ^^