de.velopmind | The Det about Programming

April 28, 2012

Functors, Monads, Applicatives – can be so simple

Filed under: FunctionalProgramming, Scala — Tags: , , , , — de.velopmind @ 5:37 pm

When I started trying to get into these weird topics named “functors” and “monads” and so on, which came up in the Scala mailing list, I was more than slightly confused [1]. I read some articles (in the beginning not many existed), listened to mails, consulted book chapters, and even started learning Haskell to consult the very fine “Learning a Haskell for great good” chapters on that matters. Different authors use different ways to explain -and implement!- these concepts, what in the end is helpful. You can read an article, think, read some other perspective, come back to the first article again, a.s.o.

But it took some time to realise how darn simple it all can be in principle (and took more time to finally write about it). I worked with and restructured some examples until the simplicity of it all became obvious. So let me now present you my perspective on it, and perhaps it will help you to get into these seemingly strange things:

Given some type constructor C[_] and two types A and B, we want to apply functions of type C[A]=>C[B] .
Unfortunately we have only functions of types A=>B,  A=>C[B] and C[A=>B] at hand, so we need adequate transformations for them:

a) ( A=>B ) => ( C[A]=>C[B] )
b) ( A=>C[B] ) => ( C[A]=>C[B] )
c) ( C[A=>B] ) => ( C[A]=>C[B] )

All these are transformations of some given functions into the function type we need, and all these transformations even have names.

a) ( A=>B )      => ( C[A]=>C[B] )   | Functor
b) ( A=>C[B] ) => ( C[A]=>C[B] )   | Monad
c) ( C[A=>B] ) => ( C[A]=>C[B] )   | Applicative

That is the pattern we have to learn by heart and keep in mind. All other is simply applying that pattern, present it in different forms and implementations [2].

Too fast? Too abstract?
Ok, now that you surely have learned this scheme by heart and can reproduce it without spiking into this article, we’ll have a closer look at how and why that works.
It all starts with a container of some type C, which is able to hold one or more values of some type A. So we have C[A] to start with.
The container itself can serve different purposes. We will come back to that in a  follow-up post.
To keep things easy for now, let’s start with the most simple: A box.


class MyBox[T](val value:T)

Then we can put a value of some type into such a box, for example a string.


val boxedstring:MyBox[String] = new MyBox("Hello")

Now we want to apply some computation or transformation on the value (type A) in C, without leaving C. That means, the result value of some type B shall also be in a C. In other words: We want to apply functions of type C[A]=>C[B].

In our example: Let’s assume we want to compute the length of the string in MyBox, and get the result again in MyBox. This would need a function of type MyBox[String] => MyBox[Int], which would calculate the lenght but somehow stay inside the box:


def lengthOf( a:MyBox[String]) : MyBox[Int] = ....

The problem is that we already have some interesting computations -like the length of a string- at hand, but they are not of the correct type. They are of much more functions on the raw types A=>B, or functions of type A=>C[B] or even the raw functions already wrapped in C, resulting in C[A=>B] (Why that is, we talk about later).

In our example, we have a function:


def rawLengthOf(a:String) : Int = a.length

We can see, that we need to transform it. So let’s write a transformation for it:


def map[A,B]( rawfunc:A=>B ) : MyBox[A]=>MyBox[B] = (a:MyBox[A]) => new MyBox( rawfunc(a.value) )

Let’s look closer into it: map is a function that takes another function of the raw types A=>B as parameter and returns a new function that takes a MyBox[A], applies the raw function, and wraps the result in a MyBox again.

Now let us put all these things together:


class MyBox[T](val value:T)

def map[A,B]( rawfunc:A=>B ) : MyBox[A]=>MyBox[B] = (a:MyBox[A]) => new MyBox( rawfunc(a.value) )
 val boxedstring:MyBox[String] = new MyBox("Hello") // a boxed value

def rawLengthOf(a:String) : Int = a.length // the raw function we want to use

val transformedLenghtOf = map(rawLenghtOf) // applying the transformation, so we get our new function

val result:MyBox[Int] = transformedLengthOf( boxedstring ) // applying the new function

So we have a MyBox[_], and we have a map function for MyBox. Congratulations, this is your first Functor!

The other two examples work similarly.

We start with our boxedstring again, but then we have:


def lengthOf(a:String) = new MyBox( a.length ) // a function which takes a raw type but boxes the result itself

Why such things can happen, we will see later.

So we need a new transformation:


def flatMap[A,B]( func:A=>MyBox[B] ): MyBox[A]=>MyBox[B] = (a:MyBox[A]) => func( a.value )

flatMap is a function that takes a semi-raw function of type A=>MyBox[B] -e.g. String=>MyBox[Int]-, and returns a new function that takes a MyBox[A], applies the semi-raw function and simply returns its result.

The rest now looks almost the same:


val transformedLenghtOf = flatMap(lenghtOf) // applying the transformation, so we get our new function

val result:MyBox[Int] = transformedLengthOf( boxedstring ) // applying the new function

Again: We have a MyBox[_], and we have a flatMap function for MyBox.
This, my dear, is a Monad!

The third pattern shouldn’t be much of a problem here.

Again we start with our boxedstring, but now we found our rawLengthOf again, surprisingly itself boxed in a MyBox:


val boxedLengthOf:MyBox[String=>Int] = new MyBox( rawLengthOf _ )

But this is no problem, we only need another converter, this time without any “map” in its name.


def apply[A,B](b:MyBox[A=>B]): MyBox[A]=>MyBox[B] = (a:MyBox[A]) => new MyBox(b.value(a.value))

apply now is a function that takes a boxed raw function and returns a new function that takes a MyBox[A], applies the unboxed raw function to its unboxed value, and returns the result in a new box.

val transformedLenghtOf = apply(boxedLenghtOf) // applying (*haha*) the transformation, to get our new function
val result:MyBox[Int] = transformedLengthOf( boxedstring ) // applying the new function

Applicative on stage!

Let’s sum it up by listing all these transformations together. All transformations result in MyBox[A]=>MyBox[B], so I will leave this type away:


class MyBox[T](val value:T)

//Functor
 def map[A,B] ( rawfunc:A=>B ) = (a:MyBox[A]) => new MyBox( rawfunc(a.value) )

// Monad
 def flatMap[A,B]( func:A=>MyBox[B] ) = (a:MyBox[A]) => func( a.value )

// Applicative
 def apply[A,B] ( b:MyBox[A=>B] ) = (a:MyBox[A]) => new MyBox(b.value(a.value))

So far for the basic stuff. In the next article we will talk about alternative ways to implement such concepts in Scala, so we are able to recognise them, no matter how they are implemented or how the transformation functions are named.

[1] “A Monad is a monoid in the category of endofunctors” became a popular term of debate about the usefulness of such explanations.
[2] Well, there may be more about the theoretical concept of Functors, Monads and Applicatives -and Category Theory- but that is all you need to know to start.

Create a free website or blog at WordPress.com.