de.velopmind | The Det about Programming

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.

Advertisements

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.

Blog at WordPress.com.