I finished the chapter three of the book, here the focus was on creating our own implementation of list and tree.

Pattern matching

Extensive use of the pattern matching, that is actually a switch on steroids, very powerful.
This example shows the implementation of the tail method, that is just returning everything but the head of a sequence

def tail[A](l: List[A]): List[A] = {
    l match {
      case Nil => Nil
      case Cons(_, t) => t
    }
  }

As you can see, we pass a list as argument of the function and than we match the structure of it: if Nil it just return an empty list (Nil and empty list mean the same in this specific implementation of List).
If it matches the structure that is an head and a tail, just returns the tail (to be precise for this match we don’t even take in account the first part of the structure, that’s why we are using the underscore).

Fold

An important concept on applying function traversing data structures is fold.
It’s helpful for generalizing the operation do execute to the elements of the data structure. A typical signature of the method is scala fold(list, initialValue)(f) where f is the function to be applied.
There are two type of fold called fold right and fold left.

Fold right

With fold right we apply the function between the initial value and the last element of the list and we recursively apply the result to the next element.

In the case of the sum operation, here the implementation using fold right

def foldRight[A,B](as: List[A], z: B)(f: (A,B) => B): B =
  as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

def sumR(ns: List[Int]) = foldRight(ns, 0)(_ + _)

sumR(List(1,2,3)) shouldBe 6

So starting from the value 0, the identity for the addition, we start summing all the elements of the list starting from the value 3 and recursively going back to the first, so

((0 + 3) + 2) + 1 = 6

Fold left

Fold left is actually doing the opposite of fold right, applying the function to the first element of the list and then recursively applying the function between the result and the next element.

@tailrec
def foldLeft[A,B](as: List[A], z: B)(f: (B,A) => B): B =
  as match {
    case Nil => z
    case Cons(h,t) => foldLeft(t, f(z, h))(f)
  }

def sumL(ns: List[Int]) = foldLeft(ns, 0)(_ + _)

sumL(List(1,2,3)) shouldBe 6

Difference between fold right and fold left

The two approaches look similar but the important difference is that with fold right we need to traverse the all data structure before starting applying the function recursively.

If you notice the fold left function is annotated as tail recursive because, in fact, the last operation is doing is calling itself. This is a big advantage on fold left over fold right, for data structures with a lot of elements, at least in the Scala implementation.

Notes

I added a the definition from the documentation of the programming language Haskell: in fact Scala borrows few concepts from the former.

Code

The following links are related to the source code for the chapter 3: