de.velopmind | The Det about Programming

May 4, 2012

Functors, Monads, Applicatives – different implementations

Filed under: FunctionalProgramming, Scala — de.velopmind @ 8:49 pm

In the previous blog post I claimed that Functors, Monads and Applicatives can be presented in an easily comprehensible way:

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

Thus they are perceived  as transformations/conversions from some function type involving an A and a B to the type C[A]=>C[B] .

We then created a container MyBox, which can keep a value of some type, and some functions which implemented the above mentioned signatures.

For example the Functor transformation was implemented as a standalone function named map :

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

But what I want you to understand in this post, is that this -map as a function taking a function- is only one possible implementation, and that there are very different ways to structure the concept represented by the function map . This is much more true for Scala, which is a feature rich hybrid OO-FP language. To demonstrate this, let’s stay with Functors and the shown map function. What you see here will be applicable for the other concepts, Monad and Applicative, too.

First, let us again have a look at the signature of map:

( A=>B ) => ( MyBox[A]=>MyBox[B] )

According to this signature, map takes a function of type A=>B and returns a function which takes a MyBox[A].  In the end the result is of type MyBox[B]. The second pair of parens can easily be left out:

( A=>B ) => MyBox[A] => MyBox[B]

What we now see is a curried form that we can transform back into a multi-parameter function:

((A=>B), MyBox[A]) => MyBox[B]

We now have a function taking two parameters -a function A=>B and a MyBox[A]- and resulting in MyBox[B]. In such a case the order of the parameters isn’t really important, so we can change that easily to

( MyBox[A],(A=>B)) => MyBox[B]

what in curried form again is

MyBox[A] => (A=>B) => MyBox[B]

Let’s take our first implementation and adapt that according to this signature:

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

Now map first takes the container to work on and then returns a  function that is bound to that container, but  expects as parameter the bare typed function which shall be applied to produce the result.

This is a signature for map that you will also find in articles, either as a primary way to implement it, or as a helper function, delegating to  the other signature (like here).

So far the class MyBox and the function map are only loosely related, i.e. the function map can be located anywhere in our code base. To organize it better and document the relationship of map with MyBox, we could possibly declare it as a method on a companion object:

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

Much more, if we have a function that takes an instance of some class as its first parameter, this is only a functional way to describe a method, which in classical OO would belong to the class itself. So the signature

(MyBox[A],(A=>B)) => MyBox[B]

is a hint, that maybe map should be implemented like this:

class MyBox[A](val value:A) {
 def map[A,B](rawfunc:A=>B) = new MyBox( rawfunc(this.value) )
}

So now we can call map directly on an instance of MyBox:

val n = new MyBox("hello")
n.map( (a:String)=>a.length ).value // -> 5

This is a nice way to implement Functors and Monads in case you are the class’ author and have such features already in mind. As you may know, Scala’s for-comprehension is only syntactic sugar for calls to map and flatMap on instances. Therefore our class can be used inside such expressions too.
Another Scala-typical way to provide methods on objects although their class does not implement them are wrapper classes and implicit conversions. How this would look like for our MyBox, you see below, including also the Monad method flatMap.

class MyBox[T](val value:T) {
   override def toString() = "MyBox("+value+")"
}

class MyBoxWrapper[T](w:MyBox[T]) {
    def flatMap[R](f:T=>MyBox[R]) = map(f).value
    def map[R](f:T=>R) = new MyBox(f(w.value))
}

object TestMonadWrapper {
    implicit def myBoxToWrapper[S](mb:MyBox[S]) = new MyBoxWrapper[S](mb)

    def main(args:Array[String]) {
        val ma = new MyBox("hello world")
        println ( ma.map((a) => a.length) )

        val res = for {
                    a <- ma
                  } yield a.length + 2

        println(res)

        val mb = new MyBox("hola mundo")

        val res2 = for {
                     a <- ma
                     b <- mb
                   } yield a.size + b.size

        println (res2)
    }
}

This is an extended example, so let’s have a walk-through.  Class MyBox implements a toString Method to allow for convenient printing on console, so we don’t have to call .value to see what the value is. MyBox does not implement the methods map and flatMap itself, but we have a wrapper class MyBoxWrapper that implements them for us. Our application object TestMonadWrapper contains some tests in the main method, and an implicit conversion that wraps a MyBox instance into a MyBoxWrapper whereever the methods map and flatMap are called on a MyBox instance. This is the case for ma and mb inside the for-comprehensions.

Last but not least Scala also knows typeclasses -not as a language feature but as a pattern-, which are just another way to provide function implementations for specific types, a concept taken from Haskell. I don’t want to dive into that matter here now. To see Monads implemented as a typeclass, have a look into Daniel Spiewak’s article Monads are not metaphors , where the concept Monad is shown as a trait, implemented by two implicit objects for different types, or at Eric Torreborre’s article The Essence of the Iterator Pattern, where he demonstrates Functor and Applicative as typeclasses right from the beginning.

In my examples you have so far always seen the functions named map, flatMap and apply. The first two match with how the Scala standard library is implemented and the for-comprehension works. But the name apply must be taken with care, as this is in Scala a conventional method to use object references like functions.

Indeed, other languages implement the concepts of Functor, Monad and Applicative too but use other names for the functions. Namely in Haskell, the source of those ideas, the methods are named differently and sometimes confusingly for a Scala developer. So is the method map named fmap there, not to be confused with Scala’s flatMap, which is named bind in Haskell. Beside that, Haskell uses even symbolic names for the functions.

Another blog post which I found recently and which presents Functors, Monads and Applicatives in a similar reduced way like my first post, is Functors, Applicative Functors, and Monads aren’t that scary. The author took the Haskell function names for Scala too.

All in all, the names are of no importance.  Much more, have a look at the signatures to recognise the patterns shown in the first post, even when they are mutated, like seen in this post.

In the next post we will play with map, discover the other two function signatures of the first post, and think about how it comes that we would need flatMap and apply.

About these ads

5 Comments »

  1. I like your post very much, it’s very instructive. Many Thanks.

    Comment by simon — May 16, 2012 @ 2:11 pm

  2. […] the last post in this series I used the map function as a demonstration for different styles to implement the three concepts. […]

    Pingback by Functors, Monads, Applicatives – playing with map (Functor) « The Det about Programming — May 20, 2012 @ 5:37 pm

  3. […] also had a different implementation in the second article (I change the type variables here, and method to function, to harmonise with the code […]

    Pingback by Functors, Monads, Applicatives – taking Monad apart [DRAFT] « de.velopmind | The Det about Programming — January 21, 2013 @ 1:22 am

  4. […] post is about Functors, or more precisely the map method, and is especially related to my post: Functors, Monads, Applicatives – different implementations . It is therefore recommended that you (re)read that one, and best its predecessor,  before. (I […]

    Pingback by Functors in images « de.velopmind | The Det about Programming — February 11, 2013 @ 2:40 pm


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The Silver is the New Black Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: