8/18/11

Functors, Applicative Functors, and Monads aren't that scary

I'm currently reading "Learn You a Haskell for Great Good" (really great book, if you want to learn Haskell, you can read it online or better, buy it now! ) and it has a very good explanation of Functors, Applicative Functors, and Monads. I refuse to write another Monad tutorial (I'm not knowledgeable enough) but I'll write about what I've understood so far. (Be kind enough to correct me)

Here is all you need to know about functors, applicative functors, and monads (Haskell code):



Or it's equivalent Scala code:


Crystal clear, isn't it? Just kidding.
IMPORTANT NOTE:THIS ARE ONLY THE THE TYPE SIGNATURES, ANY IMPLEMENTATION HAVE TO COMPLY WITH THE FUNCTOR/MONAD LAWS (see ADENDUM at the bottom)

The TL;DR version
Want to apply a function to things in some "context"? Use a functor.
The functions are already in some "context"? Use applicative functor.
What if your function put things in the "context"? Use a Monad (... and flatMap that shit!)
That's all you need to know.


Functor
Let's start with the functor.
First, the trait has a type parameter, T[_] (it's a polymorphic type constructor or higher kinded type, but you aren't the type that get scared easily, right?)
For now, you can consider it as a "context": it can be a data structure, like a list, or something else that holds the parameter type inside plus whatever you want to add.
Let's look now at the method signature:
  def fmap[A,B](f:A=>B)(ta:T[A]):T[B]
You take a function f from A to B, and ta context of A and returns a context of B.
In Scala collections is the map function. It transforms T[A] into T[B] by applying f to the elements wrapped "inside" T[A].
That's all you need for a functor! It doesn't look that scary...

Applicative Functor
Now let's look at the applicative functor. For starters, the applicative functor is also a functor (I guess the "functor" in the name is a big hint) so we have the map function available.
With map, you can apply functions to things already in some context, but what if what you have in the context are functions? you need more than fmap to apply them.
Enter the applicative functor.
The applicative functor defines two methods pure and <*>:
  def pure[A](a:A):T[A]
Pure is for putting things in the context, it takes an element of A and returns that element in the minimal context that makes sense (e.g. for lists, would be a list with a single element a).
The next function, "apply" or <*> (you can call it advanced TIE fighter or clenched angle arse if you want) takes functions already in the context and applies them to values in the context, yielding the results also in the context. The way it combines the functions with the values depends on the implementation of the applicative functor itself (e.g. for lists, it applies every function in the list of functions to every value in the list of values).
You can see Tony's message to the Scala mailing list for an amazing example of why the applicative functor is useful.

Monad
And now, the famous Monad !. Monads are applicative functors, but with another method ">>=" (in Scala, you know it as flatMap ). We saw that applicative functors are like functors but the <*> allows you to apply functions already in a context unlike fmap wich needs the functions directly. But what if you have a function that takes a value of A (outside a context) and returns a value of b in the context? (they're pretty common: think of a function that may fail, returning Option[A] ). To apply those kind of functions to things already in the context is why we have >>= function: is pretty similar to the applicative functor's "apply" but instead of a function already in context, it takes a function from A to a context of B.

For my next post, I want to show that using Option as a monad in Scala CAN save you from NullPointerExceptions...

Notes:
  • Eric explained most of this way better than me in  "The essence of the iterator pattern"
  • The traits above are just for illustrative purposes, for the real thing use Scalaz
  • I'm no authority, take all I've said with a grain of salt, I just hope it helps in your explorations. For me, applicative functor was the missing piece in my understanding of monads.



ADENDUM: There's a great (and WAY better than mine) explanation of all of this in Haskell's Typeclassopedia. I don't know why nobody called me on it, but to actually have an instance of Functor/Applicative/Monad the implementation has to obey the following laws:


Functor laws
fmap id = id
fmap (g . h) = fmap g . fmap 




Applicative Functor laws
pure id <*> v = v                            -- Identity
pure (.) <*> u <*> v <*> w = u <*> (v <*> w) -- Composition
pure f <*> pure x = pure (f x)               -- Homomorphism
u <*> pure y = pure ($ y) <*> u              -- Interchange




Monad laws
m >>= return     =  m                        -- right unit
return x >>= f   =  f x                      -- left unit
(m >>= f) >>= g  =  m >>= (\x -> f x >>= g)  -- associativity
Post a Comment