de.velopmind | The Det about Programming

November 17, 2013

Folien zu Java8 – neue Sprachfeatures.

Filed under: FunctionalProgramming, Java, Language — de.velopmind @ 7:05 pm

February 11, 2013

Functors in images

Filed under: FunctionalProgramming, Scala — Tags: , , — de.velopmind @ 2:40 pm

During the long break between my posts in the end of last year I pondered how a visual representation for all that Functor, Monad, Applicative stuff would look like. I myself are a visual thinker, i.e. thinking always involves images moving and rotating through my head. Visual representation now helps to get an imagination of concepts and make thinks more clear, at least to me.

Now, this is the first post where I try to present a visual representation. Fiddling with images on a computer now is not my kind of art, and time is scarce. But I didn’t want to wait longer to present a first result, so bare with some lack of aesthetics in the pictures.

This 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 thought about changing those posts to include the images, but decided against it).

Now, it all starts with an instance of class MyBox[A] and a function from A to B, in this case a MyBox[String] and a function String=>Int :

FunctorsInGraphics-1

As we have seen in the post referenced above, map can be implemented as a standalone function or as a method on class MyBox. We will begin with the latter. Let us now turn the MyBox image slightly in our direction:

FunctorsInGraphics-2

We now have this MyBox thing and the function. Let us now think about the function to be some sort of pipe that can take a string on one end and outputs an integer on the other end. Calling the map method/function is now comparable to plumbing the pipe to the MyBox thing:

FunctorsInGraphics-3

Ok, here we “put the pipe on it”. Beneath the picture you see three different ways to implement map, and the first one in black is the one this image is about .

When we now let the plumbing do its work due to the map method, it not only gives the result value of the mapped method, but this value is wrapped in a MyBox again.

So this is the complete picture of this scene:

FunctorsInGraphics-4

This is very easily grokkable, and holds for may cases where map is implemented as a method on a class. For example for Option, or for collections:

FunctorsInGraphics-8

Here is how it is applied maybe to a List. The original box has many values, and the plumbing puts each into the pipe and produces a similar box with the output values.

That was easy and matches mostly the first experiences we make with map in Scala. But the original notion presented in the first post was more according to this:

FunctorsInGraphics-6

Map is here thought as being a function that converts (lifts) a function from A to B into a function from M[A] to M[B]. Fed with a function String=>Int, it produces a function  MyBox[String]=>MyBox[Int]. And this “lifting”, presented in the right way, seems more in the line of thinking of category theorists.

FunctorsInGraphics-7-2

We now have  a world with some values of some types on the left, together with functions between those types. In the picture the types are String (value “hello”) and Int (value 5), and the function is what you see in the red box. In this imagination we consider the function map now being a pipe, in fact one which moves the function from the left side world to the right side world, where any value is hidden in a box of some type (here: MyBox). And as surely as the original function could work with “hello” and produce the 5, the transfered function can handle a “hello” in a MyBox and produce a MyBox with a 5 in it.

Hopefully you found this representation of map with images as useful as I did. I try to use this way of representation in further posts, perhaps even inline in the “Functors, Monads, Applicative” series.

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.

January 20, 2013

Time is running …

Filed under: Uncategorized — de.velopmind @ 1:23 pm

Wow, time is running!

It was a really shocking experience, when I realised that my last post is far more than a half year old.

I am sorry that I could not follow up my series about Functors, Monads and Applicatives as well as I wanted, due to heavy workload, and I hope that I will be able to post more in-time than last year. We will see.

In the meantime I thought about how that whole stuff could be presented more graphically, as sometimes images are better suited to create a mental model about stuff than only text.

So you can expect me to present some more on that topic in the future. (No promise about time, though).

May 20, 2012

Functors, Monads, Applicatives – playing with map (Functor)

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

The first blog post about Functors and co.  introduced the three basic function transformations that form Functor, Monad and Applicative.

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

In the last post in this series I used the map function as a demonstration for different styles to implement the three concepts. Let’s now stay a bit longer with our Functor, play a bit with map and look what we detect.

Although these patterns are not metaphors, I will neverless begin to think a little bit metaphorically about a Functor – or more precisely: about our MyBox.

In the examples so far we have seen the class MyBox as a carrier of a value:

class MyBox[T](val value:T)

And we have also seen implementations like the following:

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

or even

n.map( (a:String)=>a.length ).value // -> 5

Notice here the access to the box’s value with a.value . While the first example, map, encapsulates this access in its implementation, it is done in the open in the last example.

But an important fact about Functors et al is exactly this: The value is hidden inside the Functor wrapper, and access to it is only possible by passing a function to some sort of “guardian” (map, flatMap). This “guardian” has the control over the Functor, and he “grants” the access to the value to the “visitor”, i.e. the given function.

It is as if the value will never get out of the Functor, but stay inside. So, if you want to cause any effect on it, you have to pass a transformation into the functor. The result of the effect stays in the Functor.

Another metaphor is to think of a Functor wrapper as a test tube. You have some dark blue liquid in it. Then you open the tube and give some reagent into it, and after a short while the dark blue liquid is transformed into a light green sort of sirup. All that happened inside the test tube.

So now we have our MyBox, containing a string value, and we open the lid, throw a function into it, and now the value and the function react, resulting in an integer value inside that MyBox.

Ahem, ok, so far for the metaphors. The thing is, that our MyBox is a nice wrapper for demonstration, but it is absolutely useless. There is no reason to keep the value inside, and no reason why we shouldn’t do something like this:

val boxedstring = new MyBox("Hello")
val hellolenght = boxedstring.value.length

But let’s assume that instead of this boring MyBox the wrapper would be more interesting. It could be a collection, like List. Then applying the function to every element and collect the results in another List would be a tedious task. We would have to externally iterate over the elements. The map function does this for us internally. Or consider the Option class. It is very much like our MyBox, but it has some kind of semantics. And transforming the value via map plus a given function keeps this semantic. That is, when used seriously, a Functor is not such a dull thing like MyBox, but provides some interesting information or functionality. It is a context around the value.

Ok, I digressed a bit, so let us come back to map:  ( A=>B ) => ( C[A]=>C[B] ) 

The map function allows us to access the value inside a wrapper C[_], in our case MyBox, and allows us to transform not only the value itself, but also the type of the value. We saw that in our example, where the string value “Hello” in the MyBox was transformed into an int value representing the length.

If one starts to work with generics and type parameters, one can easily be confused by the meaning of a type parameter like A or B. These two letters each simply stand for a “type”, but there is no statement about what this type is. It can be a simple type, like String or Int in our example, but it can also be a complex generic type.

For example, the result type B could be a List[String]:

val boxedstring = new MyBox("Hello")
val splitter = (a:String) => a.split("").toList
map(splitter)( boxedstring ) // Result: MyBox[List[java.lang.String]]

Splitter is a function of type String=>List[String], and according to how map works, the overall result is of type MyBox[List[String]]. You can imagine that this works for many other types too, like e.g. Option, so given a function of type String=>Option[Int] we would get a MyBox[Option[Int]].

Now let’s do a funny thing:

val boxhead = (a:String) => new MyBox(a.head)
map(boxhead)( boxedstring ) // Result: MyBox[MyBox[Char]]

Wow, two things are interesting here:

  1. The result type is a MyBox containing a value of type MyBox[Char] – we have a box in a box!
  2. The function type of function boxhead is String=>MyBox[Char]

The general signature of map is (A=>B), in this case it is (String=>MyBox[Char]).

But we already have a function with the general signature A=>C[B], which in our case would be A=>MyBox[B]. That is the signature of flatMap !

It seems that flatMap is only a special case of the more general map. There is a relationship between Functor and Monad, and we will take a closer look to flatMap in the next article.

For now let’s try something else. Until now we have only worked with functions that take one parameter. But what happens if we have one value but a function that takes two?  That is where currying comes into play:  Each function taking two parameters and returning a result can also be expressed as a function taking one parameter and returning another function which takes the second parameter and then returns the result:

scala> val add = (a:Int, b:Int) => a + b  // function with two parameters returns result
add: (Int, Int) => Int = <function2>

scala> add(3,5)
res13: Int = 8

is equivalent to

scala> val add = (a:Int) => (b:Int) => a + b // function with one parameter returns function
add: Int => (Int => Int) = <function1>

scala> val add3 = add(3)    // new function based on argument 3
add3: Int => Int = <function1>

scala> add3(5)     // function returns result
res15: Int = 8

More generally: Every function taking more than one parameters can be expressed as a chain of functions taking one parameter and returning a function which also takes one parameter. That should not be new to you, as we used that technique in the last post to transform the map function from one implementation style to another.

Now back to map. As map takes a function with only one parameter, each function with more than one parameter has to be changed into its curried form.

An example:
A function with two parameters

val conc = (a:String, b:String) =>  a + b

is changed to its curried form.

val conc = (a:String) => (b:String) =>  a + b

Now let’s try what happens when we put that into our map for boxedstring.

map(conc)(boxedstring) // Result: MyBox[String => String]

Wow, and suddenly we have a function inside a box! It seems here we are at the fundaments of Applicative, as the result type is exactly the signature of the apply function.

We talked a bit about what a Functor wrapper like MyBox in practice can be, and we played a bit with the map function. Perhaps this encourages you to experiment more with it.

So far for now, and happy mapping. In the next post we will play a bit with flatMap.

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.

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.

April 25, 2012

y ( is ( 6 afraidOf 7 ) )

Filed under: Scala, Uncategorized — de.velopmind @ 5:49 pm

Or: What happens when a simple number joke meets a bored Scala developer …

Save the following code into a file, e.g. named Fears.scala.

type Reason = () => String

class ReasonedState(val state:Boolean, val reason:Reason)

case class True(why:Reason)  extends ReasonedState(true, why) {
   override def toString() = "yes"
}
case class False(why:Reason) extends ReasonedState(false, why) {
   override def toString() = "no"
}

class Fears(value:Int) {
   def afraidOf(other:Int) = (value,other) match {
      case (6,7) => True (() => (7 to 9).toList.map(_.toString).reduce(_+" "+_))
      case _     => False(() => "nothing to fear")
   }
}

implicit def numbersFears(nu:Int) = new Fears(nu)

def is(rs:ReasonedState) = rs
def y (rs:ReasonedState) = rs match {
    case rs:True => "because "+rs.reason()
    case _       => "wrong question"
}

Then open the Scala REPL in the same directory as the file you saved and type:

scala> :load Fears.scala

Now type:

scala > y ( is ( 6 afraidOf 7 ) )

…and enjoy the result.

Tip: If you don’t already know it, read the input and the result aloud (in english).

September 4, 2011

The truth behind Scala

Filed under: Language, Scala — de.velopmind @ 5:58 pm

Now that the discussion about Scala’s complexity, mind broadening or mind twisting features and so on is on the board again with posts like

Yes, Virginia, Scala is hard (David Pollak)

and

Scala is for drivers (Michael Fogus)

I am delighted that my vacation lecture gave me the ultimate answer, why I in contrast to other fellows in development got the impression that the occupation with Scala has broadened and is further broadening my mind.

The hint to the answer is here:

Where does the name “Scala” come from?

And the answer itself  is in this quote of my lecture:

“The Winding Staircase, as it was known, [...] represented man’s intellectual climb toward the Divine Truth. Like Jacob’s ladder, the Winding Staircase was a symbol of the pathway to heaven [...] the connection between the earthly and spiritual realms. Its steps represented the many virtues of the mind.”

Dan Brown, you never imagined to be quoted in this context, eh?

Well. Scala is not a one-step replacement for Java. That is true, and it is good that it is.

Trying to learn Scala has indeed similarities with the Masonic degrees: Once you are initiated, you learn step by step the secret symbols and rites. Scala seems to be dangerous in the hands of the uninitiated, but it is a artefact of great power in the hands of the initiated ones.

Here are the degrees and the secrets that are unveiled when initiated to each:

Scala levels: beginner to expert, application programmer to library designer

I am happy that I came to know Scala, which, at least for me, is enlightening.

So I think, that The Lost Symbol looks like this:

(PS: Don’t take this post too serious, heh?. In the end it’s my vacation. Serious stuff is left for later).

July 16, 2011

Quicknote: Very interesting interview with M.Odersky

Filed under: Language, Scala — de.velopmind @ 4:42 pm

A very interesting interview with Martin Odersky about Scala at Dr.Dobbs:

http://drdobbs.com/231001802

Notable the hints about Scala on .Net,  for LLVM and for JavaScript.

Older Posts »

The Silver is the New Black Theme. Blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.