CH03-数据

定义函数式数据结构

函数式数据结构只能被纯函数操作，纯函数一定不能修改原始数据或产生副作用。因此，函数式数据结构被定义为不可变的。

比如单链表的实现：

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 sum(ints: List[Int]):Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }
  
  def product(ds:List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x, xs) => x * product(xs)
  }
  
  def apply(as: A*): List[A] = 
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail:_*))
}

List[+A]表示它是一个泛型数据类型。同时拥有两种实现，或者说是两种构造器，每种都由case关键字定义，表示它的两种可能的形式。如果List为空，则用Nil表示，如果非空，则用构造器Cons表示。一个非空列表由初始元素head和后续紧跟的也是List结构的tail构成，并且，这个tail可能为空，即他可能是一个Nil。

这就是一个典型的数据构造器声明，为我们提供了一个函数来构造该类型数据的不同形式：

val ex1:List[Double] = Nil
val ex2:List[Int] = Cons(1, Nil)
val ex3:List[String] = Cons("a", Cons("b", Nil))

模式匹配

在List的伴生对象中定义了两个方法，sum和product，他们都使用了模式匹配。同时他们都是以递归的方式定义，这在编写操作递归数据类型的函数时很常见。

模式匹配类似于switch，他可以侵入到表达式的数据结构内部，对这个结构进行检验和提取子表达式。符号=>左边为模式，右边为结果。

如果将模式中的变量分配给目标子表达式，使得它在结构上与目标一致，模式与目标就是一致的。匹配上的话，结果表达式就可以访问这些模式中定义的局部变量。

函数式数据结构的数据共享

当一个新的元素添加到已有的列表时返回一个新的列表。既然列表是不可变的，并不需要真的去复制一份原有列表，而是直接去复用它，比如向原有的列表 xs 添加一个数字 1，返回一个Cons(1, xs)。

同样，删除列表的第一个元素，比如myList = Cons(x, xs)，这时只需要返回尾部的xs。并没有真的删除任何元素。原始的myList依然可用，不会受到任何影响。

这被称为数据共享。

“函数式数据结构是持久的”，是指：已存在的引用不会因数据结构的操作而改变。

数据共享的效率

？？？

高阶函数的类型推导

当向一个高阶函数传递函数类型的参数时，需要标识该函数的类型。比如高阶函数dropWhile：

def dropWhile[A](l: List[A], f: A => Boolean): List[A]

当调用该函数时，参数函数f必须制定它的参数类型：

val xs:List[Int] = List(1,2,3,4,5)
val ex1 = dropWhile(xs, (x:Int) => x < 4)	// (x:Int) 指定参数类型为 Int

因为dropWhile的两个参数都使用类型参数A，前一个参数l的类型为Int，因此第二个参数的类型也必须是Int。

当函数定义包含多个参数组时，参数组里的类型信息从左到右进行传递。

因此我们把dropWhile的参数列表分开，让他成为一个柯里化函数：

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

现在可以这样调用dropWhile，dropWhile(xs)(x => x < 4)。当调用dropWhile(xs)时他会返回一个函数，这时已经确定第一个参数的类型为A，因此第二个参数时就不再需要进行类型标注了，它的类型只能为A。

通过将函数参数分组排序成多个参数列表(将函数柯里化)，来最大化的利用类型推导。

基于 List 的递归并泛化为高阶函数

回顾前面的sum和product函数：

def sum(ints: List[Int]): Int = ints match{
  case Nil => 0
  case Cons(x, xs) => x + sum(xs)
}

def product(ds:List[Double]): Double = ds match{
  case Nil => 1.0
  case Cons(x, xs) => x * product(xs)
}

这两个函数的结构类似，不同在于他们操作的数据类型(Int/Double)、Nil时返回的值(0/1.0)、以及对结果的组合操作(+/*)。

对于这两个函数的抽象，首先将Int/Double泛化为类型参数A，而Nil的返回值，可以作为一个函数参数由客户端提供。

如果一个子表达式引用了任何局部变量，把子表达式放入一个接收这些局部变量作为参数的函数。

比如上面这两个函数中的x + sum(xs)和x * product(xs)部分，都是对局部变量的引用，因此可以抽象为函数f: (A, B) => 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))
  }

def sum2(ns: List[Int]) = foldRight(ns, 0)((x, y) => x + y)
def product2(ns: List[Double]) = foldRight(ns, 1.0)(_ * _)

这里需要注意的是，与之前遇到的泛化不同，该函数的最终计算结果类型与传入的列表类型并不相同，如函数签名foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B所示，它的最终计算结果与传入的参数z类型一致，即类型B。

因为整个函数的计算过程就是对列表进行循环，一直遍历到列表末尾，这个过程中不断压栈，直至列表的末尾，即Nil。而遇到Nil时返回的值为传入的参数z，套用传入的函数f，也就是通过传入列表的最后一个元素(Nil 之前的元素)与z来调用函数f，得到栈顶的值。然后依次出栈，完成整个计算过程。

可以函数的调用使用传入的函数f进行替换：

Cons(1, Cons(2, Nil))
f	(1, f   (2, z  ))

foldRight函数为 Scala 标准库中List的内置函数，上面的替换过程也就是它的计算过程。

比如我们调用sum2(List(1,2,3), 0)((x, y) => x + y)，跟踪其运算过程：

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)))) // Nil, 终止递归，替换为(0 + 0)
1 + (2 + (3 + (0))
6

树

List 是代数数据类型(ADT)的一种，有些场景或称为抽象数据类型。

ADT 是由一个或多个数据构造器所定义的数据类型，每个构造器可以包含零个或多个参数。数据构造器通过累加(sum)或联合(union)构成数据类型，而每个数据构造器又是其参数的乘积(product)。因此称为代数数据类型。

ADT 用于构造其他数据结构。定义一个二叉树数据结构：

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]