de.velopmind | The Det about Programming

January 21, 2013

Functors, Monads, Applicatives – taking Monad apart

Filed under: FunctionalProgramming, Scala — de.velopmind @ 1:22 am

Welcome to a new (and long overdue) article in the series around Functors, Monads and Applicatives.

As promised in the last article, we will have now a closer look at Monads.  I think it would be good if you read the last post again.

We talked about the two type variables A and B that form the signature of the function given to map, A=>B. We detected, that B stands for any type, even if it is as complex as List[String], or even MyBox[Char]. As an example we mapped a function of type String=>MyBox[Char] to a MyBox[String], and the result was a MyBox[MyBox[String]. But we detected also that there already is another function, flatMap, that already takes the more specific signature A=>C[B], or here: A=>MyBox[B]. So we concluded:

It seems that flatMap is only a special case of the more general map.

Let us reconsider:

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

map takes a function A=>B, and converts it to a function taking a MyBox[A] and resulting in a MyBox[B]

if we give map a function A=>MyBox[T], applying that to a Mybox[A] results in a nested MyBox[MyBox[T]] .

flatMap is more specific and takes only functions of type A=>MyBox[T], and results only in a MyBox[T].

This is crucial: The result of flatMap is a flat Container, not a nested one!

So let us look at how this function flatMap may be implemented. We already presented an implementation in the first article:

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

Well, if you compare that to the implementation of map some lines before that, the difference is simple: flatMap calls func(a.value) and does nothing but returning the result of func, while map wraps this result into a new MyBox .

If we would compare the object id of the func result with the object id of the flatMap result, we would see: It is identical. It is exactly the result of func that is returned.

We also had a different implementation in the second article (I change the type variables here, and method to function, to harmonise with the code above) :

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

This implementation routes the given function of type A=>MyBox[B] to the map function, which -as we already know- results in a nested MyBox[MyBox[B]]. Then the value method on this result is called, which results in exactly the wrapped MyBox[B] instance. The effect is similar as above: if we would inspect the object id of the result of func and the object id of the overall flatMap result, it would be the exact same object.

Now let’s do something funny: Let’s reduce flatMap to the application of map, and let us abstract the subsequent unwrapping into a new function:

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

Voilá, the new function is called flatten, and if we look at the implementation of flatMap, it becomes obvious why it is named so in Scala:

It is the combined effect of map and flatten.

It is interesting that -although flatMap has such an important meaning for Monads, e.g. in for-comprehensions- it is often this flatten function that is considered the specific property of Monads, and flatMap is only considered a convenience function (see: “Scala in Depth” – J.Suereth, Ch. 11.2.1).  (For more on that, read this paragraph in the Wikipedia article about Monad). But keep in mind that the important part for programming in Scala (e.g. the for-comprehension) is the flatMap method.

Well, by now we haven’t gained much. The result of some flatMap(somefunc) applied to an MyBox[A] is a MyBox[B] that comes directly from somefunc, and the MyBox wrapping the A is forgotten. Why not, it wouldn’t change anything, would it?   Same for Option:  A Some(Some(“hello”) would become a Some(“hello”), a Some(Nothing) would become that Nothing. Wouldn’t it?

So let’s now broaden the view somewhat:

Let’s start with the List class. Assumed we have a list val mylist =  List(1,2,3) and we call map( x => List(x, x*x, x*x*x)) on it, it would result in

List[List[Int]] = List(List(1, 1, 1), List(2, 4, 8), List(3, 9, 27))

Now, if we would have to implement the flatten method on List now, so that the result is

List[Int] = List(1, 1, 1, 2, 4, 8, 3, 9, 27)

How would we do that? Well, our flatten method would have to look somehow like this:

def flatten(xs:List[List[Int]]) =
    xs.foldLeft(List[Int]()) ((res,item) => res ::: item)

We take our list of lists and call foldLeft on it with a startvalue of an empty result list. Then each item in the list of lists (i.e. each List[Int]) is concatenated to the actual result. (You should be familiar with the functionality of foldLeft. If not, look it up now).

The thing here is: The result is a totally new list, built as a concatenation of the many lists contained in the map result. So it made sense to extract the flatten function.

But there’s even more to it:  MyBox, Option, List have all in common, that they are about holding values and nothing more. They are mainly containers.

Now let’s enhance our MyBox implementation, and rename it on the fly:

class LogBox[T](val value:T, val mesg:String="")

Our new class has an additional attribute mesg of type string which defaults to the empty string. Thus we can still create an instance by only providing a value, but we can also put some additional log message in:

class LogBox[T](val value:T, val mesg:String="")
val boxedint1:LogBox[Int] = new LogBox(1)       // --> boxedint =  LogBox(1, "")
val boxedint2:LogBox[Int] = new LogBox(2,"two") // --> boxedint =  LogBox(2, "two")
val boxedint3:LogBox[Int] = new LogBox(2,"three") // --> boxedint =  LogBox(2, "two")

So far, the interesting part comes when we implement map and flatten (and surely flatMap) on this new class, to use it in monadic style.
Let’s start with map and an example of its function:

class LogBox[T](val value:T, val mesg:String="") {
    def map[B](f:T=>B) = new LogBox(f(value), mesg)
}

val test = new LogBox(2, "hello")
val result = test.map( v => v*2 )

result.mesg  // --> "hello"

What is notable here: The map method creates as its result a new LogBox with the value being the result of the application of f. This is known. But this new LogBox also gets the mesg value of the current instance, thus carrying the mesg forward. If we call .mesg on the result, it is the same as we had in the former LogBox.

Not let us implement flatMap and flatten:

class LogBox[T](val value:T, val mesg:String="") {
    def map[B](f:T=>B) = new LogBox(f(value), mesg)
    def flatMap[B](f:T=>LogBox[B]) = flatten( map(f) )
    def flatten[B](m:LogBox[LogBox[B]]) = new LogBox( m.value.value, m.mesg+m.value.mesg+"\n")
}

flatMap  is as we would expect it to be, only now implemented as a method: it is flatten after map with the given f .

The flatten itself is now the interesting part.  Let us assume, that the current instance of LogBox looks like this: LogBox(7, “hello”).

Let us further assume that the function f calculates its argument times 6 and so returns a LogBox like this: LogBox(42, “world”).

Then what map would return would be:    LogBox(   LogBox(42, “world”),   “hello” ) .

That is: The outer LogBox contains as value the inner LogBox which is the result of applying function f to the former value. And the outer LogBox contains as mesg its former content, as this is kept by map and carried forward.

flatten now constructs a new LogBox whose value is the value of the inner LogBox, as that is the calculation result. The new mesg on the other hand is a concatenation of the outher mesg and the inner mesg, extended by a newline:  “helloworld\n”.

At the end of this post let us see that in action, based on a start value on which some calculations are done and logged:

val one = new LogBox(1)

val two = one.flatMap( x => new LogBox( x+1, "plus one"))

val four = two.flatMap( x => new LogBox( x*2, "times two"))

four.value  // --> 4

four.mesg   // --> "plus one
                    times two
                   "

So far for now. I can’t tell what will be the topic of the next post, so I avoid any promises. This last paragraph will be replaced once a new post becomes available.

Advertisements

4 Comments »

  1. […] far for now, and happy mapping. In the next post we will play a bit with […]

    Pingback by Functors, Monads, Applicatives – playing with map (Functor) « de.velopmind | The Det about Programming — January 21, 2013 @ 1:24 am

  2. If I’m correct LogBox is a writer monad. It may be better to add this to this post, as people finding this kind of code will be able to put the right name of it.

    Comment by Ludovic Claude (@ludovicc) — January 21, 2013 @ 6:05 pm

  3. I really like your serie!
    The sentence about “function f calculates its argument times 6” is a bit confusing. I assume f would be v => new LogBox(v*6, “world”), right?

    Comment by Jörg Keller — October 11, 2013 @ 10:10 pm

    • Exactly!
      I will put more detail into this paragraph.
      Thanks for your feedback.

      Comment by de.velopmind — October 12, 2013 @ 7:51 am


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

Create a free website or blog at WordPress.com.

%d bloggers like this: