Jump to: Navigation
Functional Programming for Mere Mortals (Part 2)
This is the second post in a series of blog posts where I work my way through the “Functional Programming in Scala” book.
We are now in Chapter 3 “Functional Data Structures”.
This has been the hardest chapter so far, and I think probably one of the harder chapters in the book. It covers a lot of new concepts, and there are a lot of exercises, each one building on the previous one.
The chapter opens with a definition of functional structures as being those that can be operated on using only pure functions. The rest of the chapter uses a functional implementation of the ubiquitous Linked List.
This is the definition of the List data type (all the code used in the book is available at https://github.com/fpinscala/fpinscala
sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]
object List {
def apply[A](as: A*): List[A] = {
if(as.isEmpty) Nil
else Cons(as.head, apply(as.tail: _*))
}
}
There is some new Scala syntax (i.e traits and object), which have similar equivalents in other programming languages.
From the book;
A trait is an abstract interface that may optionally contain implementations of some methods.
A good additional reference regarding Scala classes is “Scala for the Impatient” by Cay S. Horstmann
Case classes were also introduced, and they make more sense when you get to the section on Pattern Matching, but I’m getting ahead of myself here.
The big takeaways from this chapter for me were Pattern matching, foldRight and foldLeft. I’ll dive into each below
Pattern Matching
Pattern matching works a bit like a fancy switch statement that may descend into the structure of the expression it examines and extract subexpressions of that structure.
That is a really succinct and great explanation. Also think of it as a switch statement that will refuse to compile if you do not handle all possible cases. A simple example (its Christmas season, so lets pretend we’re Santa)
sealed trait Child
case class Good(name: String, age: Int) extends Child
case class Bad(name: String, age: Int) extends Child
val child: Child = Bad("Goody Two shoes", 2)
/*
Santa's Code to check whether to give a gift. However if a child is
one or younger, treat them like a good child
*/
val greeting = child match {
case Bad(name, 1) => "Hello " + name + "!. Here is a gift."
case Bad(name, _) => "Hello " + name + "!. Here is a lump of coal." //Comment out this line
case Good(name, _) => "Hello " + name + "!. Here is a gift."
}
println(greeting)
If Santa is careless and checks for bad children who are 1 year old but forget to check for bad children in general (by commenting out the line marked above), he will get a compile failure with the following error
pattern_matching.scala:14: warning: match may not be exhaustive.
It would fail on the following input: Bad(_, (x: Int forSome x not in 1))
val greeting = goodChild match {
^
one warning found
scala.MatchError: Bad(Goody Two shoes,2) (of class Main$$anon$1$Bad)
at Main$$anon$1.<init>(pattern_matching.scala:14)
at Main$.main(pattern_matching.scala:1)
at Main.main(pattern_matching.scala)
No more bugs during runtime because your switch statement did not account for certain combinations (or weird errors because you forgot a break: statement. Pattern matching is really powerful and you can write some really complex matching logic. The syntax also allows you to capture variables (in the case above, I capture the name used in the class constructor to use within the relevant block.
foldRight and foldLeft
For me the most interesting part of Chapter 3 is the section on recursion over lists and generalizing to high order functions. foldRight is introduced and it is here that things get really interesting.
foldRight operates on two types, A and B. It takes a list of type A, and an initial value (also of type A), and a function f that takes 2 values, one of type A and one of Type B, and return a value of type B.
Looking at the function, it uses pattern matching to call the function provided with the head of the list (the first element), and them passes a recursive call to itself as the second argument (since foldRight will return a value of type B).
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))
}
foldLeft is very similar to foldRight, except it is tail-recursive and can therefore be optimized by the compiler into a while loop, thereby avoiding the danger of a Stack overflow.
@annotation.tailrec
def foldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B = as match {
case Nil => z
case Cons(x, xs) => foldLeft(xs,f(z,x))(f)
}
Here is what the call stacks look like for both functions (in this case, using fold to sum all the elements of the list.)
//foldRight
foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x,y) => x + y)
1 + foldRight(Cons(2, Cons(3, Nil)), 0)((x,y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0)((x,y) => x + y))
1 + (2 + (3 + (foldRight(Nil, 0)((x,y) => x + y))))
//foldLeft
foldLeft(Cons(1, Cons(2, Cons(3, Nil))), 0)((x,y) => x + y)
foldLeft(Cons(2, Cons(3, Nil)), 1)((x,y) => x + y)
foldLeft(Cons(3, Nil), 3)((x,y) => x + y)
foldLeft(Nil, 6)((x,y) => x + y)
6
Trouble in Paradise
foldLeft/foldRight make intuitive sense once you understand what is going on, with one exception. Everything made sense until I got to the following exercise
Hard: Write a function that concatenates a list of lists into a single list. Its runtime should be linear in the total length of all lists. Try to use functions we have already defined.
I spent an inordinate amount of time trying to figure this out, and the reason is that I was thinking of A and B as simple arguments. The breakthrough came once I realized that A and B could be complex arguments (i.e Lists of type A/B).
concatenate has to return a list. That means that the function passed in needs to return a List of type B (List[B]. Once I realized that the solution became easy. Here is my solution (append was one of the previous exercises, it appends all the elements of one list to another list).
def append[A](a1: List[A], a2: List[A]): List[A] = foldRight(a1,a2)((a,b) => Cons(a, b))
def flattenList[A](as: List[List[A]]): List[A] = as match {
case Nil => Nil
case Cons(x, xs) => append(x,flattenList(xs))
}
Map
Write a function map that generalizes modifying each element in a list while maintaining the structure of the list. Here is its signature:12 def mapA,B(f: A => B): List[B]
In checking my answers against the answer key available on the authors web site, I noticed that I used a recursive solution for Map when I could just as well have used foldRight.
First, my solution
def map[A,B](as: List[A])(f: A => B): List[B] = as match {
case Nil => Nil
case Cons(x, xs) => Cons(f(x), map(xs)(f))
}
Then the authors solution (using foldRight)
def map[A,B](as: List[A])(f: A => B): List[B] =
foldRight(as, Nil:List[B])((h,t) => Cons(f(h),t))
foldLeft can also be used except it would reverse the order of the list. However, one of the previous exercises had been to write a function to reverse a list. I then used that function in the exercise to implement foldRight via foldLeft, so I could have used them together to achieve the same result (implementing foldRight via foldLeft makes it tail-recursive)
def reverse[A](as: List[A]): List[A] = as match {
case Nil => Nil
case Cons(x, xs) => foldLeft(xs, Cons(x,Nil))((a,b) => Cons(b, a))
}
def foldRightViaFoldLeft[A,B](as: List[A], z: B)(f: (B, A) => B): B =
foldLeft(reverse(as), z)((b,a) => f(b,a))
def map[A,B](as: List[A])(f: A => B): List[B] =
foldRightViaFoldLeft(as, Nil:List[B])((t,h) => Cons(f(h),t))
The common theme that emerges is that it becomes really easy to compose functions together to achieve the desired result. The rest of the chapter is relatively straightforward apart from 2 exercises. The first that I’ll tackle is subsequence
Hard: As an example, implement hasSubsequence for checking whether a List contains another List as a subsequence. For instance, List(1,2,3,4) would have List(1,2), List(2,3), and List(4) as subsequences, among others. You may have some difficulty finding a concise purely functional implementation that is also efficient. That’s okay. Implement the function however comes most naturally. We’ll return to this implementation in chapter 5 and hopefully improve on it. Note: Any two values x and y can be compared for equality in Scala using the expression x == y. def hasSubsequenceA: Boolean I found a solution, and don’t really like it. I also compared it to the official solution and it looks very similar (different but similarly complex).
My solution is below and I’m really curious to see how this is solved in chapter 5, because as currently implemented the solution is inelegant and confusing (on purpose, I suspect there is a concept introduced in Chapter 5 that simplifies this)
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
def loop[A](supRev: List[A], subRev: List[A], isSubSequence: Boolean): Boolean = supRev match {
case Nil => {
subRev match {
case Nil => isSubSequence
case _ => false
}
}
case Cons(x,xs) => subRev match {
case Nil => isSubSequence
case Cons(x2, xs2) => {
if(x == x2) loop(xs, xs2, true)
else loop(xs, subRev, false)
}
}
}
loop(sup, sub, false)
}
The second exercise I had difficult with actually came earlier in the chapter
Hard: Can you write foldLeft in terms of foldRight? How about the other way around? Implementing foldRight via foldLeft is useful because it lets us implement foldRight tail-recursively, which means it works even for large lists without overflowing the stack.
The foldRightViaFoldLeft came easy (the code is mentioned up above). The foldLeftViaFoldRight? Not so easy. I actually got stuck on this one and had to look at the solution (below)
def foldLeftViaFoldRight[A,B](l: List[A], z: B)(f: (B,A) => B): B =
foldRight(l, (b:B) => b)((a,g) => b => g(f(b,a)))(z)
I’ve looked at this and it still does not make sense to me. I will take some time and come back and revisit it.
The chapter closes by introducing a new data structure (tree, which is a binary tree), and there are some exercises to write functions to operate on the tree. Most of my solutions were recursive
sealed trait Tree[+A]
case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]
Here is one of the problems
Write a function size that counts the number of nodes (leaves and branches) in a tree.
And here is my solution
def size[A](tr: Tree[A]): Int = tr match{
case Leaf(_) => 1
case Branch(l, r) => 1 + size(l) + size(r)
}
This is also very similar to my solution for finding the node in the tree with the maximum value
def maximum(tr: Tree[Int]): Int = tr match{
case Leaf(v) => v
case Branch(l,r) => maximum(l) max maximum(r)
}
The books authors have a solution that uses fold (similar to rightFold and leftFold but that operates on the Tree data type). Here is their fold function
/*
Like `foldRight` for lists, `fold` receives a "handler" for each of the data constructors of the type, and recursively
accumulates some value using these handlers. As with `foldRight`, `fold(t)(Leaf(_))(Branch(_,_)) == t`, and we can use
this function to implement just about any recursive function that would otherwise be defined by pattern matching.
*/
def fold[A,B](t: Tree[A])(f: A => B)(g: (B,B) => B): B = t match {
case Leaf(a) => f(a)
case Branch(l,r) => g(fold(l)(f)(g), fold(r)(f)(g))
And here is how they use it to get the size of the tree
def sizeViaFold[A](t: Tree[A]): Int =
fold(t)(a => 1)(1 + _ + _)
*So what did I learn?
Chapter 3 was a tough chapter, with a lot of exercises, but it reveals the true power of immutable data structures and the functions that can be written to operate on them. I’m looking forward to the next chapter.
All the code I’m writing to work through the exercises is here;
Article originally published here