Question

1. List 并不是 Scala 内建的语法结构，它是由scala 包里的抽象类 List 定义的，这个抽象类有两个子类:: 和 Nil 。

   
   xxxxxxxxxx
   package scala
   abstract class List[+T]{
     ...
   }

   继承关系：

   
   xxxxxxxxxx
                               List[+T]
                          <<sealed abstract>>
                         /                    \        
                      ::[T]                    Nil
                   <<final case>>         <<case object>>

   • 由于 List 是一个抽象类，因此无法通过调用空的List 构造方法来定义列表，即：new List 是非法的。

   • List 有一个类型参数 T，参数前面的 + 表明列表是协变的。正因为如此，我们可以将类型为 List[Int] 的对象赋值给类型为 List[Any] 的变量：

     
     xxxxxxxxxx
     val xs  = List(1,2,3)
     val ys: List[Any] = xs

   • 所有的列表操作都可以通过三个基本的方法来定义：

     
     xxxxxxxxxx
     def isEmpty: Boolean
     def head: T
     def tail: List[T]

     这些方法在 List 类中都是抽象的，其具体定义出现在子类 :: 以及子对象 Nil 中。

2. Nil 对象：它定义了一个空列表，其定义如下。

   
   xxxxxxxxxx
   case object Nil extends List[Nothing]{
     override def isEmpty = true
     def head: Nothing = throw new NoSuchElementException("head of empty list")
     def tail: List[Nothing] = throw new NoSuchElementException("tail of empty list")
   }

   Nil 对象继承自类型 List[Nothing]，因为协变的原因，这意味着 Nil 和 List 类型的每个实例都兼容。

   这里的三个抽象方法的实现非常简单：

   • isEmpty 直接返回 true。
   • 其它两个方法都直接抛出异常。因为 head 没办法返回一个正常的值，所以它只能够通过抛出异常的方式非正常的返回；tail 方法也是如此。

3. :: 类：该类表示非空列表，读作 cons（即英文的 construct）。它之所以如此命名，是为了支持用中缀 :: 实现模式匹配。

   由于模式匹配中的每个中缀操作符都被当作是用入参调用该中缀操作符对应的构造方法处理，所以 x :: xs 被处理为 ::(x, xs)，其中 :: 是一个样例类。

   
   xxxxxxxxxx
   final case class ::[T](hd: T,  tl: List[T]) extends List[T]{
     def head = hd
     def tail = tl
     override def isEmpty: Boolean = false
   }

   可以通过构造方法的参数直接实现超类的 head 和 tail 方法：

   
   xxxxxxxxxx
   final case class ::[T](head: T, tail: List[T]) extends List[T]{
     override def isEmpty: Boolean = false
   }

   之所以可行，是因为样例类的每个参数都隐式的作为该类的字段，就跟在类内部定义了 val head 和 val tail 字段一样。而 Scala 允许我们用字段来实现抽象的无参方法。

4. List 的所有其它方法都可以用这三个基本方法来编写，如：

   
   xxxxxxxxxx
   def length: Int = if(isEmpty) 0 else 1 + tail.length
   def drop(n: Int): List[T] = if(isEmpty) Nil else if(n <= 0 ) this else tail.drop(n-1)
   def map[U](f: T => U): List[U] = if(isEmpty) Nil else f(head) :: tail.map(f)

5. 列表的构造方法 :: 和 ::: 是以冒号结尾，所以它们会绑定到右操作元上。即：x :: xs 会被当作 xs.::(x)，而不是 x.::(xs)，因为 x 的类型是列表元素的类型。

   事实上 x 的类型和 xs 的元素类型可以不同：

   
   xxxxxxxxxx
   abstract class Fruit
   class Apple extends Fruit
   class Orange extends Fruit
   val apples = new Apple :: Nil
   val fruits = new Orange :: apples

   :: 返回原始列表元素类型 Apple 和待添加元素的类型 Orange 最具体的公共超类。这种灵活性归功于 :: 方法的定义：

   
   xxxxxxxxxx
   def ::[U >: T](x: U): List[U] = new scala.::(x, this)

   这个方法本身是多态的，其类型参数 U 受到 [ U >: T] 的约束，它必须是列表元素类型 T 的超类。要添加的元素必须是类型 U 的值并且结果是 List[U] 。

6. 和 :: 一样，拼接方法也是多态的，结果类型会按需“自动放宽” 从而包含所有的列表元素。

   由于 ::: 和 :: 都是以冒号结尾，因此它们都是和右操作元绑定，也就是右结合的。

7. List 类大多数方法的真实实现并没有使用递归，因为递归会出现栈溢出的问题（很多递归都不是尾递归）。这些方法都是通过循环和ListBuffer 来实现。

   ListBuffer 的 toList 方法调用一般是常量时间复杂度，和列表长度无关。

   
   xxxxxxxxxx
   package scala.collection.immutable
   final class ListBuffer[T] extends Buffer[T]{
     private var start: List[T] = Nil        // 指向 ListBuffer 中保存的所有元素的列表
     private var last0: ::[T] = _            // 指向该列表最近一个添加的 :: 
     private var exported: Boolean = false   // 表示该 ListBuffer 是否已经使用过 toList 转换
     
     override def += (x: T) = { // 追加元素
       if (exported) copy() // 已经导出过，但是需要扩展，则拷贝底层数据
       if(start.isEmpty){
         last0 = new scala.::(x, Nil)
         start = last0
       }else{
         val last1 = last0
         last0 = new scala.::(x,Nil)
         last1.tl = last0
       }
     }
   }

   其中：

   
   xxxxxxxxxx
   final case class ::[U](hd:U,  private[scala] var t1: List[U]) extends List[U]{
     def head = hd
     def tail = tl
     override def isEmpty: Boolean = false
   }

   这里t1 是一个 var，这意味着它是可变的。而private[scala] 的修饰符表明 t1 只能在 scala 这个包内部被访问。

   ListBuffer 的实现方式确保只有当ListBuffer 被转成List 之后，还需要进一步扩展时，才需要拷贝。实际上这种操作实际很少出现，ListBuffer 的大部分应用是逐个添加元素，然后最后做一次 toList 操作，此时不需要任何拷贝。

8. 列表从“外面”看是纯函数式的，但是它的实现从“里面”看是过程式的。这是 Scala 编程的一个典型策略：通过仔细界定非函数式操作，将纯函数式和效率集合起来。

9. 注意：当我们用 :: 构造列表时，会复用列表的尾部：

   
   xxxxxxxxxx
   val ys = 1 :: xs
   val zs = 2 :: xs

   现在 ys 的尾部和 zs 的尾部是共享的，这是为了效率。因为如果每次添加新元素都拷贝 xs，则会慢很多。

   由于到处都是共享的，因此如果允许改变列表的成员，则很容易出问题：

   
   xxxxxxxxxx
   ys.drop(2).tail = Nil // Scala 中不支持

   这个操作会同时截断 xs 和 zs 。所以 Scala 中不允许这么做。