Scala Functional Design & Programming - Chapter 3 (3)
I bought "Scala Functional Design & Programming - A Comprehensive Guide to Functional Programming by Scalaz Contributors".
I'll read it bit by bit and summarize each chapter.
This time, I'll cover up to Chapter 3. The main topic is data updates using pure functions, which is a key aspect of functional programming.
Chapter 3
This chapter focuses on how to update data using pure functions, which do not have side effects. It starts with the definition of a list and explains pattern matching.
As expected, match is very handy.
There's a simple quiz on pattern matching (omitted).
Next, it discusses how to take advantage of the fact that data is immutable to reduce memory usage. This is followed by a series of exercises.
From here, a barrage of practice problems begins.
Many appear one after another; it feels intense.
It really feels like cramming-style programming.
Implement tail, setHead, drop, dropWhile, and init for lists.
These exercises are designed to help you understand how to work with lists in a functional programming style.
They’re short and focused, which helps build intuition.
The list data type and exercise stubs are available on GitHub.
For error handling, there are several possible approaches, but I chose to return Nil for simplicity here.
def tail[A](l: List[A]): List[A] = l match {
case Cons(_, xs) => xs
case Nil => Nil
}
def setHead[A](l: List[A], h: A): List[A] = l match {
case Cons(_, xs) => Cons(h, xs)
case Nil => Nil
}
def drop[A](l: List[A], n: Int): List[A] = {
if(n <= 0)
l
else {
l match {
case i =>
l match {
case Cons(_, xs) => drop(xs, n - 1)
case _ => l
}
}
}
}
def dropWhile[A](l: List[A], f: A => Boolean): List[A] = l match {
case Cons(x, xs) if f(x) => dropWhile(xs, f)
case _ => l
}
def init[A](l: List[A]): List[A] = l match {
case Cons(_, Nil) => Nil
case Cons(x, xs) => Cons(x, init(xs))
case Nil => Nil
}
The following is test code:
object Main extends App {
val x = List(1,2,3,4,5)
val y = List()
println(" ## ex 3.2")
println(List.tail(x))
println(List.tail(y))
println(" ## ex 3.3")
println(List.setHead(x, 10))
println(List.setHead(y, 10))
println(" ## ex 3.4")
println(List.drop(x, 1))
println(List.drop(x, 4))
println(List.drop(x, 10))
println(List.drop(y, 1))
println(" ## ex 3.5")
println(List.dropWhile(x, (a:Int)=> a < 4))
println(List.dropWhile(x, (a:Int)=> a > 4))
println(List.dropWhile(x, (a:Int)=> a < 100))
println(" ## ex 3.6")
println(List.init(x))
println(List.init(y))
}
The drop function is a bit messy, but it's a good exercise.
As a small tip, the book shows how to improve type inference for dropWhile by currying so that the second argument becomes inferable. That makes the call sites cleaner. Nice.
Can product via foldRight immediately stop recursion and return 0.0 when it detects a 0.0?
You can certainly write a custom product that returns 0.0 once it encounters a 0.0 element and avoids recursing further. However, with foldRight, the combining function f is applied after the entire structure is expanded, so you can’t short-circuit “immediately” in the strict sense. In that sense, the answer is No.
What happens if we pass
NilandConsthemselves tofoldRight? How does this relate to data constructors?
Through folding, you can reconstruct the list using its own constructors. Treating “combine two elements” as an operation and repeating it lets you build a singly linked list—an example of abstract thinking with data constructors.
Next, the book introduces foldRight and foldLeft, which are essential functions in functional programming.
Implement product using foldRight.
def product(l: List[Double]): Double = foldRight(l, 1.0)(_ * _)
Implement length using foldRight.
def length[A](l: List[A]): Int = foldRight(l, 0)((_, y) => y + 1)
Implement foldLeft, which is tail-recursive.
@tailrec
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
case Nil => z
case Cons(x, xs) => foldLeft(xs, f(z, x))(f)
}
Implement sum, product, and length using foldLeft.
def flSum(l: List[Int]) = foldLeft(l, 0)(_ + _)
def flProduct(l: List[Double]) = foldLeft(l, 1.0)(_ * _)
def flLength[A](l: List[A]): Int = foldLeft(l, 0)((x,y) => x + 1)
Implement reverse using foldLeft.
def reverse[A](l: List[A]): List[A] = foldLeft(l, Nil: List[A])((x,y) => Cons(y, x))
It’s neat to see how foldLeft can build a reversed list succinctly.
When you construct with foldRight you get the normal order, while foldLeft naturally builds the reverse.
Implement foldRight using foldLeft.
def foldLeft2[A, B](l: List[A], z: B)(f: (B, A) => B): B = {
val f2: (A, B) => B = (a: A, b: B) => f(b, a)
foldRight(reverse(l), z)(f2)
}
At first glance this looks straightforward, but the book also presents a gnarly implementation that flips evaluation order using higher-order functions.
Because the application order differs, I also prepared f2 with flipped argument order.
def foldRightViaFoldLeft_1[A,B](l: List[A], z: B)(f: (A,B) => B): B =
foldLeft(l, (b:B) => b)((g,a) => b => g(f(a,b)))(z)
This is hard to grasp without concrete examples, but by substituting actual values you can see how the control flow changes.
The book also covers more advanced topics, such as implementing append, concat, plusOne, doubleToString, map, filter, and flatMap using foldRight and foldLeft.
Here are some additional implementations I tried, following the flow of the chapter:
Implement
appendusing fold.
def flAppend[A](a1: List[A], a2: List[A]): List[A] =
foldRight(a1, a2)(Cons(_, _))
[Hard] Concatenate a list of lists into a single list.
def concat[A](l: List[List[A]]): List[A] =
foldLeft(l, Nil: List[A])(append)
The problems marked [Hard] in the book are indeed a bit painful.
With IDE help (e.g., IntelliJ), you can partially apply append directly:
foldLeft(l, Nil: List[A])(append)
Return a list where each element is incremented by 1.
def plusOne(l: List[Int]): List[Int] =
foldRight(l, Nil: List[Int])((x,y) => Cons(x + 1, y))
Convert
List[Double]toList[String].
def doubleToString(l: List[Double]): List[String] =
foldRight(l, Nil: List[String])((x,y) => Cons(x.toString, y))
Implement
map.
def map[A, B](l: List[A])(f: A => B): List[B] =
foldRight(l, Nil: List[B])((x,y) => Cons(f(x), y))
Implement
filter.
def filter[A](as: List[A])(f: A => Boolean): List[A] =
foldRight(as, Nil: List[A])((x,y) => if (f(x)) Cons(x, y) else y)
Implement
flatMap.
def flatMap[A, B](as: List[A])(f: A => List[B]): List[B] =
concat(map(as)(f))
Clean.
Implement
filterusingflatMap.
def ffilter[A](as: List[A])(f: A => Boolean): List[A] = {
val t = (a: A) => if (f(a)) Cons(a, Nil) else Nil
flatMap(as)(t)
}
Implement
plusthat adds twoList[Int]element-wise.
def plus(l1: List[Int], l2: List[Int]): List[Int] = {
def loop(xs1: List[Int], xs2: List[Int]): List[Int] = xs1 match {
case Cons(x, xs) => xs2 match {
case Cons(y, ys) => Cons(x + y, loop(xs, ys))
case Nil => Nil
}
case Nil => Nil
}
loop(l1, l2)
}
Generalize to
zipWith.
def zipWith[A, B, C](l1: List[A], l2: List[B])(f: (A,B) => C): List[C] = {
def loop(xs1: List[A], xs2: List[B]): List[C] = xs1 match {
case Cons(x, xs) => xs2 match {
case Cons(y, ys) => Cons(f(x, y), loop(xs, ys))
case Nil => Nil
}
case Nil => Nil
}
loop(l1, l2)
}
Alternative patterns for two lists at once.
def plus2(l1: List[Int], l2: List[Int]): List[Int] = (l1, l2) match {
case (Nil, _) => Nil
case (_, Nil) => Nil
case (Cons(x,xs), Cons(y,ys)) => Cons(x + y, plus2(xs, ys))
}
def zipWith2[A](l1: List[A], l2: List[A])(f: (A,A) => A): List[A] = (l1, l2) match {
case (Nil, _) => Nil
case (_, Nil) => Nil
case (Cons(x,xs), Cons(y,ys)) => Cons(f(x, y), zipWith2(xs, ys)(f))
}
Implement
takeand then use it to implementhasSubsequence.
def take[A](l: List[A], n: Int): List[A] = n match {
case 0 => Nil
case _ => l match {
case Cons(x, xs) => Cons(x, take(xs, n-1))
case Nil => Nil
}
}
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = {
def make(l: List[A], n: Int): Boolean =
if (take(l, n) == sub) true else l match {
case Nil => false
case Cons(_, xs) => make(xs, n)
}
make(sup, length(sub))
}
The behavior looks fine, though it still feels a bit clunky.
Looking at the book’s answer, it first defines startsWith and then uses that. The idea is to keep checking prefix matches from the front—simple and sufficient.
Both versions are tail-recursive and pleasantly simple, but as the authors note, it’s not always obvious to convince yourself they’re correct. This gets revisited in Chapter 5, so I’ll wait until then.
Finally, it introduces trees as a new data structure and explains how to implement functions such as size, maximum, depth, and map for trees.
Trees
After a large number of list exercises, a new data structure appears: the tree. There is an explanation of algebraic data types, implementations for Tree, and practice problems. Finally, we generalize these functions with a fold over trees and reimplement them using that abstraction.
Implement
size,maximum,depth, andmapfor a binary tree.
def size[A](t: Tree[A]): Int = t match {
case Leaf(_) => 1
case Branch(l, r) => size(l) + size(r)
}
def maximum(t: Tree[Int]): Int = t match {
case Leaf(a) => a
case Branch(l, r) => maximum(l).max(maximum(r))
}
def depth[A](t: Tree[A]): Int = t match {
case Leaf(_) => 1
case Branch(l, r) => depth(l).max(depth(r))
}
def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
case Leaf(a) => Leaf(f(a))
case Branch(l, r) => Branch(map(l)(f), map(r)(f))
}
We can also define a general fold over trees and reimplement the above using it:
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))
}
def size2[A](t: Tree[A]): Int = fold(t)(_ => 1)(_ + _)
def maximum2(t: Tree[Int]): Int = fold(t)(a => a)(_ max _)
def depth2[A](t: Tree[A]): Int = fold(t)(_ => 1)((x,y) => 1 + (x max y))
def map2[A,B](t: Tree[A])(f: A => B): Tree[B] =
fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_, _))
These implementations are pleasantly short, and the types help guide the design.
It’s finally over. The chapter closes by encouraging readers to hone their generalization skills through practice.
Thoughts
I was surprised by how short the implementations were. As I worked through the exercises, I started to see patterns and ways of thinking that are characteristic of functional programming.
Even for tasks like tree traversals that tend to feel “tedious,” being able to write them simply is worth experiencing at least once.
The next chapter will cover error handling, which is an essential aspect of programming.
Continued:
