## Functional Data Structures

### Functional programming in Scala

The following set of sections represent the exercises contained in the book "Functional Programming in Scala", written by Paul Chiusano and Rúnar Bjarnason and published by Manning. This content library is meant to be used in tandem with the book. We use the same numeration for the exercises for you to follow them.

Assume the following functions are available for your reference:

``````sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head: A, tail: List[A]) extends List[A]``````

Exercise 3.1:

Examine the next complex match expression. What will be the result?

``````val x = List(1, 2, 3, 4, 5) match {
case Cons(x, Cons(2, Cons(4, _))) => x
case Nil => 42
case Cons(x, Cons(y, Cons(3, Cons(4, _)))) => x + y
case Cons(h, t) => h + sum(t)
case _ => 101
}
x shouldBe res0``````

Exercise 3.2:

Take a look at the implementation of `List`'s `tail` function, and check its behaviour on the following cases:

``````def tail[A](l: List[A]): List[A] =
l match {
case Nil => sys.error("tail of empty list")
case Cons(_, t) => t
}
tail(List(1, 2, 3)) shouldBe res0
tail(List(1)) shouldBe res1``````

Exercise 3.3:

`setHead` follows a similar principle. Let's take a look at how it works:

``````def setHead[A](l: List[A], h: A): List[A] =
l match {
case Nil => sys.error("setHead on empty list")
case Cons(_, t) => Cons(h, t)
}
setHead(List(1, 2, 3), 3) shouldBe res0

Exercise 3.4:

We can generalize `take` to the function `drop`:

``````def drop[A](l: List[A], n: Int): List[A] =
if (n <= 0) l
else
l match {
case Nil => Nil
case Cons(_, t) => drop(t, n - 1)
}

drop(List(1, 2, 3), 1) shouldBe res0
drop(List(1, 2, 3), 0) shouldBe res1
drop(List("a", "b"), 2) shouldBe res2
drop(List(1, 2), 3) shouldBe res3
drop(Nil, 1) shouldBe res4``````

Exercise 3.5:

`dropWhile` extends the behaviour of `drop`, removing elements from the `List` prefix as long as they match a predicate. Study its implementation and check how it works with the following examples:

``````def dropWhile[A](l: List[A], f: A => Boolean): List[A] =
l match {
case Cons(h, t) if f(h) => dropWhile(t, f)
case _ => l
}

dropWhile(List(1, 2, 3), (x: Int) => x < 2) shouldBe res0
dropWhile(List(1, 2, 3), (x: Int) => x > 2) shouldBe res1
dropWhile(List(1, 2, 3), (x: Int) => x > 0) shouldBe res2
dropWhile(Nil, (x: Int) => x > 0) shouldBe res3``````

Exercise 3.6:

`init` can be implemented in the same fashion, but cannot be implemented in constant time like `tail`:

``````def init[A](l: List[A]): List[A] =
l match {
case Nil => sys.error("init of empty list")
case Cons(_, Nil) => Nil
case Cons(h, t) => Cons(h, init(t))
}
init(List(1, 2, 3)) shouldBe res0
init(List(1)) shouldBe res1``````

### Recursion over lists and generalizing to higher-order functions

Exercise 3.x:

Let's run through the steps that `foldRight` will follow in our new implementation of `sum2`:

``````foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x, y) => x + y) shouldBe 6
res0 + foldRight(Cons(2, Cons(3, Nil)), 0)((x, y) => x + y) shouldBe 6
res1 + res2 + foldRight(Cons(3, Nil), 0)((x, y) => x + y) shouldBe 6
res3 + res4 + res5 + foldRight(res6, 0)((x, y) => x + y) shouldBe 6
res7 + res8 + res9 + res10 shouldBe 6``````

Exercise 3.8:

Now that we know how `foldRight` works, try to think about what happens when you pass `Nil` and `Cons` themselves to `foldRight`.

``foldRight(List(1, 2, 3), Nil: List[Int])(Cons(_, _)) shouldBe res0``

Exercise 3.9:

Let's try to use `foldRight` to calculate the length of a list. Try to fill the gaps in our implementation:

``````def l = List(1, 2, 3, 4, 5)
def length[A](as: List[A]): Int = List.foldRight(as, res0)((_, acc) => acc + res1)

length(l) shouldBe 5``````

Exercise 3.10:

Let's write another general tail-recursive list-recursion function, `foldLeft`, using the techniques we discussed in the previous chapter:

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

Exercise 3.11:

Let's write functions `sum`, `product` and `length` of a list using `foldLeft`:

``````def sum3(l: List[Int]) = foldLeft(l, res0)(_ + _)
def product3(l: List[Double]) = foldLeft(l, res1)(_ * _)
def length2[A](l: List[A]): Int = foldLeft(l, res2)((acc, h) => acc + res3)

def listInts = List(1, 2, 3, 4, 5)
def listDoubles = List(1.0, 2.0, 3.0)
sum3(listInts) shouldBe 15
product3(listDoubles) shouldBe 6.0
length2(listInts) shouldBe 5``````

Exercise 3.12:

As we saw above, we can write the previous functions we implemented using `foldRight` with `foldLeft`. Let's continue with `reverse`:

``def reverse[A](l: List[A]): List[A] = foldLeft(l, List[A]())((acc, h) => Cons(h, acc))``

Exercise 3.13:

In fact, we can write `foldLeft` in terms of `foldRight`, and the other way around:

``````def foldRightViaFoldLeft[A, B](l: List[A], z: B)(f: (A, B) => B): B =
foldLeft(reverse(l), z)((b, a) => f(a, b))

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)``````

Exercise 3.14:

Another function we can implement by using `foldRight` is `append`:

``````def appendViaFoldRight[A](l: List[A], r: List[A]): List[A] =
foldRight(l, r)(Cons(_, _))``````

Take a look at its implementation and check how it works:

``````append(List(1, 2, 3), List(1, 2)) shouldBe res0
append(List(1, 2, 3), Nil) shouldBe res1
append(Nil, List(1, 2)) shouldBe res2
append(Nil, Nil) shouldBe res3``````

Exercise 3.15:

`foldRight` can also be useful to write a function `concat` that concatenates a list of lists into a single list. Take a look at its implementation:

``````def concat[A](l: List[List[A]]): List[A] =
foldRight(l, Nil: List[A])(append)``````

Since `append` takes time proportional to its first argument, and this first argument never grows because of the right-associativity of `foldRight`, this function is linear in the total length of all lists.

### More functions for working with lists

Exercise 3.16:

Let's keep digging into the uses of `foldLeft` and `foldRight`, by implementing a function that transforms a list of integers by adding 1 to each element:

``````def add1(l: List[Int]): List[Int] = foldRight(l, Nil: List[Int])((h, t) => Cons(h + res0, t))
add1(List(1, 2, 3)) shouldBe List(2, 3, 4)``````

Exercise 3.17:

We can do something similar to turn each value in a List[Double] into a String:

``````def doubleToString(l: List[Double]): List[String] =
foldRight(l, Nil: List[String])((h, t) => Cons(h.toString, t))``````

Exercise 3.18:

Both `add1` and `doubleToString` modify each element in a list while maintaining its structure. We can generalize it in the following way:

``````def map[A, B](l: List[A])(f: A => B): List[B] =
foldRight(l, Nil: List[B])((h, t) => Cons(f(h), t))``````

Exercise 3.19:

Let's apply the same principle as we use in `map` to remove elements from a list, starting with a function to remove all odd numbers from a List[Int]:

``````def removeOdds(l: List[Int]): List[Int] =
foldRight(l, Nil: List[Int])((h, t) => if (h % res0 == res1) Cons(h, t) else t)
removeOdds(List(1, 2, 3, 4, 5)) shouldBe List(2, 4)``````

Exercise 3.20:

We're going to implement a new function that works like `map` except that the function given will return a list instead of a single result, and that list should be inserted into the final resulting list:

``````def flatMap[A, B](l: List[A])(f: A => List[B]): List[B] =
concat(map(l)(f))``````

Let's try it out:

``flatMap(List(1, 2, 3))(i => List(i, i)) shouldBe res0``

Exercise 3.22:

Now we're going to write a function that accepts two lists of integers and constructs a new list by adding corresponding elements. i.e.: `List(1, 2, 3)` and `List(4, 5, 6)` become `List(5, 7, 9)`:

``````def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
case (Nil, _) => Nil
case (_, Nil) => Nil
case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, addPairwise(t1, t2))
}``````

Exercise 3.23:

We can generalize the function above so that it's not specific to integers or addition, `zipWith`:

``````def zipWith[A, B, C](a: List[A], b: List[B])(f: (A, B) => C): List[C] = (a, b) match {
case (Nil, _) => Nil
case (_, Nil) => Nil
case (Cons(h1, t1), Cons(h2, t2)) => Cons(f(h1, h2), zipWith(t1, t2)(f))
}``````

Let's try out `zipWith` in the following exercise:

``````zipWith(List("a", "b", "c"), List("A", "B", "C"))(_ + _) shouldBe res0
zipWith(List(1, 2, 3), List(4, 5, 6))(_.toString + _.toString()) shouldBe res1``````

Exercise 3.24:

As a final example for working with lists, let's implement a `hasSubsequence` function 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:

``````@annotation.tailrec
def startsWith[A](l: List[A], prefix: List[A]): Boolean = (l, prefix) match {
case (_, Nil) => true
case (Cons(h, t), Cons(h2, t2)) if h == h2 => startsWith(t, t2)
case _ => false
}

@annotation.tailrec
def hasSubsequence[A](sup: List[A], sub: List[A]): Boolean = sup match {
case Nil => sub == Nil
case _ if startsWith(sup, sub) => true
case Cons(h, t) => hasSubsequence(t, sub)
}``````

Take a thorough look at the implementation of this function, and then try it out in the next exercise:

``````def l = List(1, 2, 3, 4, 5)

hasSubsequence(l, List(2, 3)) shouldBe res0
hasSubsequence(l, List(0, 1)) shouldBe res1
hasSubsequence(l, Nil) shouldBe res2``````

### Trees

Exercise 3.25:

Let's try to implement a function `size` to count the number of nodes (leaves and branches) in a tree:

``````def size[A](t: Tree[A]): Int =
t match {
case Leaf(_) => res0
case Branch(l, r) => res1 + size(l) + size(r)
}

def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
size(t) shouldBe 5``````

Exercise 3.26:

Following a similar implementation, we can write a function `maximum` that returns the maximum element in a Tree[Int]:

``````def maximum(t: Tree[Int]): Int = t match {
case Leaf(n) => n
case Branch(l, r) => maximum(l) max maximum(r)
}``````

Exercise 3.27:

In the same fashion, let's implement a function `depth` that returns the maximum path length from the root of a tree to any leaf.

``````def depth[A](t: Tree[A]): Int =
t match {
case Leaf(_) => res0
case Branch(l, r) => res1 + (depth(l) max depth(r))
}
def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
depth(t) shouldBe 2``````

Exercise 3.28:

We can also write a function `map`, analogous to the method of the same name on `List`, that modifies each element in a tree with a given function. Let's try it out in the following exercise:

``````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))
}

def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
Tree.map(t)(_ * 2) shouldBe res0``````

Exercise 3.29:

To wrap this section up, let's generalize `size`, `maximum`, `depth` and `map`, writing a new function `fold` that abstracts over their similarities:

``````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))
}``````

Let's try to reimplement `size`, `maximum`, `depth`, and `map` in terms of this more general function:

``````def sizeViaFold[A](t: Tree[A]): Int =
fold(t)(a => res0)(res1 + _ + _)

def maximumViaFold(t: Tree[Int]): Int =
fold(t)(a => a)(_ max _)

def depthViaFold[A](t: Tree[A]): Int =
fold(t)(a => res2)((d1, d2) => res3 + (d1 max d2))

def mapViaFold[A, B](t: Tree[A])(f: A => B): Tree[B] =
fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_, _))

def t = Branch(Branch(Leaf(1), Leaf(2)), Leaf(3))
sizeViaFold(t) shouldBe 5
maximumViaFold(t) shouldBe 3
depthViaFold(t) shouldBe 2
mapViaFold(t)(_ % 2 == 0) shouldBe res4``````