Saturday, December 24, 2011

Where my Scala makes my Zipper Optional

Houdy. 

As told in previous posts, I have read Learn You a Haskell for a great good. The book content, in addition to be humorous and filled with the author drawn-by-hand pictures, is worth while reading for people - who like me - embraced functional programming a few months ago. 
The reading took some time, and in some sense started changing my way of coding. Do not misunderstand me. As a Java developer by day I have no other choice than coding in a Object Oriented approach - as far as Java permits me - and do not specifically reject this approach. I simply found some answers to technical questions and more personal way of looking at code. 

Embracing a new paradigm leverages your ability to constantly make your approach of coding evolves. It is a matter of personal opinion, but I want my own code to evolve, always. Learn you a Haskell was a first shot, and at this very moment Programming Haskell and the Craft of functional programming lays beside me on the desktop while my pdf ordered copy of Real World Haskell patiently wait on my SSD USB key. 

For those who know me, I love both Clojure and Scala, and this is not just an excuse to buy fancy geeky t shirts, I mean it . Practicing so long Haskell, while not doing Scala has been a burden. At some point I had to come back to Scala doing a simple exercise of my own in order to restart coding in the language. I needed a small kata, nothing specific in particular in order to get in Scala again, even a single class. Unfortunately, without current position nor pet project to tease my mind, the ideas were not easy to find. I found amusing considering the last chapter of Learn you a Haskell and started coding a very small zipper. 
Today post is a just a very small rambling on coming back to Scala and trying to feel the code differently.  

In 1997 Gerard Huet from INRIA (even me sometimes have french references), published an interesting article on the Zipper, as a simple approach to tree navigation and modification. Instead of considering a tree as a global context, one can find suitable to focus on a node to work on, to navigate from, or to change a local information to, like some data bound to the node. And this is it . 
A zipper is mainly a magnifying glass focusing a specific branch of a piece of tree bound to a node. In order for us to move locally up, right, left from this branch after manipulating it, we just need to remember the little world around us and the path taken to get to this position (frequently the path issued from the root).
Supposedly having to modify some data bound to nodes - no so far one from another-, having the ability to move from node to node, remembering where we come from is a real bless. No need to seek out for each node from the root each time we want to modify it: let's fire a bunch of moving commands. Using Gerard Huet own words, going down and up through the tree is like zipping and unzipping a piece of cloth, aka the name.
As far as trees are concerned , knowing the world around our branch means knowing the owning node and the other tree branches.

Everything starts with a tree definition. 
After 3 months of Haskell, I could no see a tree definition as class template defining object grapes but as a union of types (You must trust me on this assertion :)). Stephan Boyer post on this point of view is quite explicit. A tree is either an empty leaf or a node. In haskell it is defined as :

data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)

which becomes in Scala

package com.promindis.data

sealed trait Tree[+A]
object Empty extends Tree[Nothing]  {override def toString = "Empty"}
final case class Node[+A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
The scala definition concedes two lines to the Haskell one (no big deal frankly, a a certain point, the line battle does not mean anything, generally battles around languages do  not mean a lot). 

Why making things complex? A tree definition can be hosted by a simple trait. The parameterized A type define the type of the data bound a tree node. A Tree instance can be Empty or a Node instance.

The Tree value constructors are defined to be co-variant. As so, a node binding a String value is compatible with a node binding a AnyRef value. A leaf by definition must be compatible with anything. In Scala all types have a common lower bound type impersonated by the Nothing type. Then the Empty  object extending Tree[Nothing] will be compatible with Tree instances holding data of any type. Considering the uniqueness of a leaf, I found more natural making an object of it. 

I call the little world around a tree node a Spot (and not a breadcrumb like Miran Lipovaca, I leave to him that cute definition :)). Spot definitions gathered in lists will make a complete path, noticing for each step whether we came from the right or the left. Therefore our  type definition becomes:

package com.promindis.data

sealed trait Spot[+A]
final case class LeftSpot[+A](value: A, right: Tree[A]) extends Spot[A]
final case class RightSpot[+A](value: A, left: Tree[A]) extends Spot[A]
Spot type is defined to be co-variant versus its parameterized type, the meaning attached to this co-variance reflecting the one attached to the Tree type co-variance. So far so good (I told you there would be little code).

 At that point we are ready to play with zippers. What is a zipper ? A friendly (immutable of course) object encompassing the current working Tree node, and a path we are coming from, so:

final case class Zipper[+A](tree: Tree[A], spots: List[Spot[A]])

As explained before, the list of spots makes a path.
By default the tree and spots fields are final (val in scala), so immutable. Good.

Focusing, on the up, right, left and update functions in our tree, we can simply create a new immutable Zipper as a result of invoking each operation. Or can we ? What would happen if by any mean we were rambling too deep in our tree structure ? No doubt that something bad would occur as no one can go left or right from a leaf for example.
This is a potential error case.
Not watching our steps and going too far should lead us nowhere, but we should not suffer from nasty side effect like null pointers or invalid method calls. A nice Scala solution does exist, that would confine our Zipper in a "cotton" context, protecting us from side effects .

We can take back our Zipper whenever we want from the context, but the "cotton" context will not harm us. The Option type is our solution. Our Zipper is simply optional. It can look like Some(Zipper(tree, list)) when existing or None which represent no Zipper. As so, the left() method definition becomes:

 def left(): Option[Zipper[A]]

The right and up methods will return too Option instances. 

Frankly, at that point, we are nearly done. Of course I am going to use a test driven approach. But wait a minute. In order to ramble through my tree, check my values , will I have to extract my zipper at each step?
That can become particularly cumbersome ! Scala provides us with the same tools as with Map or List. One can extract the content of an Option using the tools used for collection iteration, the <- sugar form. So, starting from the following structure

  val leftChild = Node(2,Node(3, Empty, Empty),Node(4, Empty, Empty))

  val rightChild = Node(5, Node(6, Empty, Empty), Empty)

  val updatedChild = Node(7, Node(6, Empty, Empty), Empty)

  val tree = Node(1, leftChild, rightChild)


we can test the zipper expression after going left and up this way :

 def e2() = {for (
      left <- Zipper(tree, List()).left();
      up <- left.up() )
    yield up}.should(beSome(Zipper(tree, List())))

where e2 defines a Specs2 match result. Going to the left, produces an Option context. 

Applying <- to Zipper(tree, List()).left(), binds the extracted value to the local left variable. We then reuse it on the next line in order to go up. The result is again bound into a protecting Option context. At this point Specs2 provides you with the suitable DSL to extract, then challenge the value.

You may have guessed it, the Option type is a Monad, offering you a context to embed your values and manipulate them protecting your code from some side effect. Quoting Miran Lipovaca, the list comprehension for and its <- form provide us with an easy to read syntax gluing together monadic values in sequence. In our case the for comprehension is very similar to the do notation in Haskell.
Of course Monads are not just programmatic applicable design patterns and everyone can learn from category theory their more profound meaning, but you can view them as design patterns very suitable in solving programming problems. The Option monad offers you a possible failure context wrapping around optional values, while a List Monad for example can be assumed as embedding non deterministic values. 
At some point one have to start working with this notions in order to progress and I think possible to start from the application level before leveraging to the more general notions in the category theory domain. The application level offers the advantage of the every day practice. 

So, now before I forget, the testing code I wrote:


package com.promindis.data

import org.specs2.Specification

final class ZipperSpecification extends Specification{def is =

  "Zipper Specification"                      ^
                                              p^
    "Left method in Zipper should"            ^
    "go left from current scope"              !e1^
    "return to root applying up to go Left"   !e2^
                                              p^
    "Right method in Zipper should"           ^
    "go right from root"                      !e3^
    "return to root applying up to go right"  !e4^
                                              p^
    "Navigation should"                       ^
    "prevent me from going too far"           !e5^
                                              p^
    "Update should"                           ^
    "allow me to update right node"           !e6

  val leftChild = Node(2,Node(3, Empty, Empty),Node(4, Empty, Empty))

  val rightChild = Node(5, Node(6, Empty, Empty), Empty)

  val updatedChild = Node(7, Node(6, Empty, Empty), Empty)

  val tree = Node(1, leftChild, rightChild)

  def e1()  =
    Zipper(tree, List()).left()
      .should(beSome(Zipper(leftChild, List(LeftSpot(1, rightChild)))))

  def e2() = {for (
      left <- Zipper(tree, List()).left();
      up <- left.up() )
    yield up}.should(beSome(Zipper(tree, List())))

  def e3() =
    Zipper(tree, List()).right()
      .should(beSome(Zipper(rightChild, List(RightSpot(1, leftChild)))))

  def e4() = {for (
      right <- Zipper(tree, List()).right();
      up <- right.up() )
    yield up}.should(beSome(Zipper(tree, List())))

  def e5 = { for (
      right <- Zipper(tree, List()).right();
      deeperRight <- right.right();
      tooFar <- deeperRight.right()
    ) yield tooFar}.should(beNone)

  def e6 = {for(
    right <- Zipper(tree, List()).right()
  ) yield right.updated(_ => 7)}
    .should(beSome(Zipper(updatedChild, List(RightSpot(1, leftChild)))))
}

leading to the implementation:
package com.promindis.data

final case class Zipper[+A](tree: Tree[A], spots: List[Spot[A]]) {

  def updated[B >: A](f: A => B): Zipper[B] = {
    tree match {
      case Node(value, left, right) => 
        Zipper(Node(f(value), left, right), spots)
      case Empty => this
    }
  }

  def left(): Option[Zipper[A]] = {
    tree match {
      case Node(value, left, right) => 
        Some(Zipper[A](left, LeftSpot(value, right)::spots))
      case Empty => None
    }
  }

  def right(): Option[Zipper[A]] = {
    tree match {
      case Node(value, left, right) => 
        Some(Zipper[A](right, RightSpot(value, left)::spots))
      case Empty => None
    }
  }

  def up(): Option[Zipper[A]] = {
    spots match {
      case LeftSpot(value, right)::xs => 
 Some(Zipper(Node(value, tree, right), xs))
      case RightSpot(value, left)::xs =>  
        Some(Zipper(Node(value, left, tree), xs))
      case Nil => None
    }
  }
}


Progressively coming back to Scala, more determined than ever you walked by my side creating a small Zipper finally making use of the Option Monad. Not bad for a Christmas day. Merry Christmas to all. Be seeing you !!! :)

0 comments:

Post a Comment