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(_, _))``````