函数式数据结构-List（1）

什么是函数式数据结构？
函数式数据结构式只能被纯函数操作的数据结构，纯函数是不能修改数据结构的也不能产生副作用。
函数式数据结构有什么特点？
函数式数据结构最大的特点就是其被定义为不可改变的。假如我们有一个列表list，现在想给列表中添加元素，惯性思维我们会通过list.add(x)这样的方式添加元素，但是这样就相当于改变了list，因此list不是函数式数据结构。那么函数式的列表应该怎么添加元素呢？其实还是可以通过list.add(x)的方式添加元素，但是这样和普通列表有什么区别呢？关键就在于函数式list再添加完元素之后必须返回一个新的list且原list不能被修改。这就很有意思，因为这样岂不是需要额外复制，甚至消耗更多的内存。答案式否定，后面的章节我们解释原因。我们先来尝试定义一个单向链表，也就是一个只能从头部移动到尾部的链表，下面是单向链表的定义：

package org.fp.scala.datastruct

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(li: List[Int]): Int = li match {
    case Nil => 0
    case Cons(h, t) => h + sum(t)
  }

  def product(li: List[Double]): Double = li match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(h, t) => h * product(t)
  }

  def apply[A](as: A*): List[A] =
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail: _ *))
}

这里定义了一个trait：List[+A]，trait类似Java 8中添加了default method特性的interface。里面可以有没有实现的抽象方法，也可以有具体实现的方法。[+A]表示List是一个泛型数据结构，其中的+表示List[A]是协变的。这是什么意思呢？意思就是假如B是A的子类型，则List[B]是List[A]的子类型。已知Nothing是所有类型的子类型，可以推出List[Nothing]是任意类型List[A]的子类型，所以Nil可以匹配List[Int]，也可以匹配List[Double]。sealed trait表示密封特质，表示List的子类型只能在List当前scala文件中定义，这样的好处是在使用模式匹配的时候类型不至于发散。再来看下Cons，Cons包含两个属性head，tail。head表示List头部装载的元素，而tail表示List尾部。这里可以看出List是一个递归结构，当tail匹配上Nil即可跳出递归，所以List('z', 'd', 'x') = Cons('z', Cons('d', Cons('x', Nil)))，也可以形象的表示为：'z' :: 'd' :: 'x' :: Nil。

除了trait List，这里还定义了一个List的伴生对象object List。里面有三个方法：sum，product，apply。我们分别来看下这三个方法。sum方法和product的形式结构非常类似，都用到了模式匹配（pattern match）和递归调用。模式匹配有关键字match，这有点类似Java中switch，但是两者的差别还是很大的。在Java 8中swith只能匹配常量，枚举类型和字符串，Scala的模式匹配却可以匹配任何类型，匹配的过程会调用类型的提取器（extract），这个和构造器（contruct）是相反的过程，正如两者分别对应的unapply方法和apply方法。在Scala中可以说模式匹配是无处不在的，我们可以自定义apply方法也可以自定义unapply方法。再来看下递归调用，我们看一下List(1, 2, 3, 4)调用sum方法是如何展开的：
sum(List(1, 2, 3, 4))
1 + sum(List(2, 3, 4))
1 + 2 + sum(List(3, 4))
1 + 2 + 3 + sum(List(4))
1 + 2 + 3 + 4 + Nil
1 + 2 + 3 + 4 + 0
10
可以看到求解sum(List)只要转化成求head + sum(tail)即可，直到匹配带tail匹配到Nil, 而sum(Nil) == 0，可以看到这里其实就是一个简单的递归调用，注意这不是一个尾递归调用，存在优化的空间，这会再后面的章节说明。再来看下List(1, 2, 3, 4)调用product方法是如何展开的：
product(List(1, 2, 3, 4))
1 * product(List(2, 3, 4))
1 * 2 * product(List(3, 4))
1 * 2 * 3 * product(List(4))
1 * 2 * 3 * 4 * Nil
1 * 2 * 3 * 4 * 1
24
这个展开的过程和sum方法展开的过程是一样的。其中有一点需要注意，即：case Cons(0.0, _) => 0.0，这其实表示的是递归调用的一个短路点，表示列表中存在0时，递归终止product返回0，因为0乘以任何的结果都是0，后面的递归调用已经没有必要了。

最后看下apply方法，apply方法其实就是给List添加构造方法，因为有他存在，所以才有List(1, 2, 3, 4) == List.appy(1, 2, 3, 4) == Cons(1, Cons(2, Cons(3, Cons(4, Nil))))。

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

在列表中添加一个元素或者删除一个元素的时候，因为数据结构不可变，所以添加一个元素或者删除一个元素都会返回一个新的列表，那这里是不是意味着需要每次都需要复制原列表来生产新的列表呢？答案时否定的，正是因为列表时不可变的，删除元素的时候我们可以直接复用子列表，这个被称为数据共享。让我们来看一些练习：

  //实现函数tail，删除List的第一个元素，注意函数的时间复杂度时常量级别的
  def tail1: List[A] = this match {
    case Nil => Nil
    case Cons(_, t) => t
  }

  def setHead[B >: A](h: B): List[B] = this match {
    case Nil => Nil
    case Cons(_, t) => Cons(h, t)
  }

在实现tail和setHead方法的时候，我们同样使用到了模式匹配（pattern match），通过模式匹配我们很容易将List进行拆解。tail方法强调时间复杂度时常量级别的，因为数据共享我们直接复用了List的子列表tail，没有额外的再去复制列表。所以这里的时间复杂度是常量级别的，和List的长度没有任何关系。

数据共享的效率

数据共享可以让实现有更好的性能，我们看一些练习：

  //实现函数drop，从列表中删除前n个元素，时间复杂度只和drop的元素成正比
  def drop(n: Int): List[A] = {
    if (n <= 0) this
    else this match {
      case Nil => Nil
      case Cons(_, t) => t.drop(n - 1)
    }
  }

  //实现dropWhile，删除列表前缀全部满足符合判定的元素
  def dropWhile(f: A => Boolean): List[A] = this match {
    case Cons(h, t) if f(h) => t.dropWhile(f)
    case _ => this
  }

  //实现append，将一个列表所有的元素添加到另一个列表之后
  def append[B >: A](li: List[B]): List[B] = this match {
    case Nil => li
    case Cons(h, t) => Cons(h, t.append(li))  
  }

从上面的例子可以看出，利用数据共享，drop(n)时不需要去复制列表，时间复杂度只和n有关系，append(li)的时候，不需要去复制li，时间复杂度只和当前列表的长度有关系，在这里不可变列表比数组是更有效率的。但是这当然比不上双向链表，传统的双向链表只需要将最后一个节点next指针指向li即可，时间复杂度是常量级别的。我们再来看一个练习：

  //实现init，返回一个列表除最后一个元素之外所有的元素
  def init: List[A] = {
    @scala.annotation.tailrec
    def go(li: List[A], res: List[A]): List[A] = li match {
      case Nil => res
      case Cons(_, Nil) => res
      case Cons(h, t) => go(t, Cons(h, res))
    }
    go(this, Nil).reverse
  }

  def reverse: List[A] = {
    @scala.annotation.tailrec
    def go(li: List[A], res: List[A]): List[A] = li match {
      case Nil => res
      case Cons(h, t) => go(t, Cons(h, t))  
    }
    go(this, Nil)
  }

这里可以看到init的实现就复杂很多了，因为无法利用数据共享，所以必须多次拷贝列表。又因为init方法抛弃的是最后一个元素，而不是第一个元素；而Cons(h, t)是和栈一样，先进入的排在最后面，后进入的排在最前面，所以最后还需要reverse一下。同样在执行reverse方法的时候又需要复制数组，这是因为这里没有数组一样建立索引，因为列表是不可变的，我们不能通过索引来修改原列表中的元素。
接下来我们将看看如何抽象递归并泛化成高阶函数。