Accueil Le blog ebiznext
2. FP My very first functional pattern

This note is the second in a series of posts dedicated to functional programming. It highlight how FP is of great help in dealing with parallel programming. It follows that previous post

It is not a secret to anyone that “synchronisation” is your single greatest enemy in parallel programming. So how to cope with it ? Simply avoid updating any value in your program and you’re free to run on your processor at maximum speed i.e. no lock barrier !

So how do we do it ? Instead of thinking of a program as a collection of objects having a state that change over time, think of a program as a collection of functions that return newly allocated immutable objects across function calls.

Let’s write a very common data structure : The List class. I’ll start writing it in Java and then in Scala.

The List Class : The OO Way

class ListCell<T> {
    private T car;
    private ListCell<T> cdr;
    public ListCell(T value, ListCell<T> cdr) { car = value; this.cdr = cdr; } 
}

public List<T> {
        ListCell<T> elements;
        List<T>() { elements = null; }
        public T getHead() { return elements.car; }
        public void setHead(T value) { elements.car = value; }
        public void addHead(T headValue) { elements = new ListCell<T>(headValue, elements); }
        public int size() { 
            List<T> elts = elements;
            int len = 0;
            while (elts != null) {
                len++;
                elts = elts.cdr;
            }
            return len;
        }
}

P.S. I used car / cdr   as we are going to implement our list the Lisp way. 
If this list is accessed by multiple threads at the same time then we have to deal the messy lock.

Let’s handle the exact same list using an FP approach.
sealed trait List[+A] {
def size() : Int = this match {

    case Nil => 0
    case Cons(_, cdr) => 1+ size(cdr)
}
}
case object Nil extends List[Nothing]
case class Cons+A extends List[A]

// a List of two elements
val myHellozList = Cons(“Helloz”, Cons(“World”, Nil))

// Let’s update the first element
val myHelloList = Cons(“Hello”, myHellozList.cdr)

println(myHelloList.size)

Not only are we able to define the immutable list that we can change freely over time if we stick to FP principle defined above but we are also getting type covariance that the OO way cannot provide us with.

In the remaining of this note i’ll explain how to structure our code and what is the meaning of each of the Scala feature introduced above and listed below :

  • What is a case class ? And why use it ?
  • Why is the trait sealed ?
  • What’s type covariance and why didn’t we get it in Java
  • How to implement size through a HOF and make our class close to perfection
  • Why do we use the keyword object and define the Nil singleton ?

What’s a case class The short answer could be : It’s a value Object.
Basically a case class is a class that :

  • you can use in pattern matching expressions
  • you can instantiate without the new keyword in front of the class name - new Cons(…) <=> Cons(…)
  • automatically has the apply and unapply functions defined on it
  • implement for you all the getter/setter on its attributes

The apply function is like the constructor in Java. Actually a call to Cons(…) is nothing else than a call toCons.apply(…) The unapply function does exactly the opposite. It extract the object components. This method is implicitly used in pattern matching expressions. In the example above, the extract should extract the values of ‘_’ and ‘cdr’.
The expression list match { case Cons(,cdr) …}** should be read as  **Cons.unapply(list) == Some(,cdr) The case class Cons has implemented for us the following :
def unapply( list:Cons) : Option[(A, List)] = Some(car, cdr)

The sealed keyword
What if a developer decide to extend the List class and add a third subclass. This will break our pattern matching code that take into account only two subclasses (case Nil & case Cons). That’s where thesealed keyword comes to help. It simply tell developers who wish to extend the class that they can extend the List trait if and only if they do it in the very same scala file, hence keeping all case classes in the same location.

P.S. I think that Scala 2.10 compiler complains if you do not seal you case classes base class/trait.
Covariance
Covariance means that if A is B then List[A] is List[B]. That’s completely unsafe when the List can can be updated in place and that’s why the Java version does not get it.
Let’s see it through an example :
A= Rectangle
B = Shape
C = Circle
Obviously,  A is a B and C is B.

A Rectangle is a Shape and a Circle is Shape but in the Java version a List of rectangle is not a list of shape, while in the Scala version it is. How come ? As I said because The Java version List is updatable. The following lines highlight it :

Rectangle r = new Rectangle(…)
Shape s = r // OK, a rectangle is a shape
List<Rectangle> rectList = new List< Rectangle >
List<Shape> shapeList = rectList
shapeList.addHead(new Circle(…)) // The first element of my shape list is a Circle, nothing wrong ???
Rectangle rect = rectList.getHead(); //oh No crash/ BSOD / JVM Exception ect … 

This situation above cannot happen in our Scala version of List simply because the list is not updatable in place.

In FP you usually get covariance almost all the time and that’s cool & powerful:)

Scala goodies
Why does the call to size does not require us to suffix the call with parenthesis ? Simply because Scala considers that the caller does not have to be aware of the implementation details of a class. i.e; you do not have to worry as a caller wether size is implemented as an attribute or as a function. You just callsize and Scala will handle the rest for you by calling size() instead of size. Moreover if we decide to implement size as an attribute instead of a function in the List trait, the caller code would remain the same. So remember, free yourself from implementation details and call zero argument functions without the parenthesis.