Ch3 covers functional data strucure: what structures, how to define and how to use them. Contents include functional data types, pattern matching and pure function generalization.

1 Functional Data Structure

A pure function must not change data in place or perform other side effects. Functional data structure are by definition immutable. An empty list is immutable, so is the result of two lists combined.

1
2
3
4
5
6
7
8
9
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: _*))
}

The List data type is polymorphic in the type of its elements. The two implementations are called data constructor of List: one empty Nil, one nonempty Cons (short for construct).

The apply function in the companion object is a variadic function that accepts zero or more argument of type A. Insdie the function, the argument has a type of Seq[A] . Seq has methods such as head, tail etc. The syntax _* type is used to pass a Seq to a variadic method.

2 Pattern Maching

A patern may match

  • literals
  • variables (an identifier starting with a lowercase letter or undercore)
  • data constructors

Pattern matching may be nested arbitrarily. A pattern matches the target if there exists an

3 Data Sharing

Since functional data structure is immutable, data can be shared for different operations.

Using parameter list helps the type inference for higher-order functions.

4 Recursion Over Lists and Generalization

The similarity between contractors and foldRight:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
// travel to the end of the list before it can begin collapsing (execute f) the list
def folderRight[A, B](as: List[A], z: B)(f: (A, B) => B): B =
  as match {
    case Nil         => z
    case Cons(x, xs) => f(x, folderRight(xs, z)(f))
  }

def sum2(ns: List[Int]) = folderRight(ns, 0)(_ + _)
def productr2(ns: List[Double]) = folderRight(ns, 1.0)(_ * _)

// this shows the similarity of the definition and folderRight
Cons(1, Cons(2, Cons(3, Nil)))
// f(1, f(2, f(3, z))) use Cons for f and Nil for z
List.folderRight(List(1, 2, 3), Nil:List[Int])(Cons(_, _))