本章主要讲Scala中的类型参数化。本章主要分成三个部分，第一部分实现一个函数式队列的数据结构，第二部分实现该结构的内部细节，最后一个部分解释其中的关键知识点。接下来的实例中将该函数式队列命名为Queue。

一、函数式队列

　　函数式队列是一种具有以下三种操作方法的数据结构，并且这些操作都必须在常量时间内完成：

• head，返回该队列中的第一个元素
• tail，返回除第一个元素之外的所有元素组成的新队列

• enqueue，将新元素加入原有队列从而得到一个新队列

  　　函数式队列不同于可变队列(mutable queue)。从上面三种操作可以看出，函数式队列对象的内容不可变，新增一个元素时得到的是一个新的队列对象。
  
  我们期望Queue具有的功能是，执行下面两句代码后，

val q = Queue(1, 2, 3)

val q1 = q enqueue 4

　　q的元素仍然是1, 2, 3，而q1的元素则为1, 2, 3, 4。

1、基于List类型的Queue实现

　　由于Queue类型是不可变的，那么在实现上面三个方法时也不能基于可变的数据结构来设计。由于List类型也是非可变的，并且也支持直接操作头尾元素。下面基于List来实现第一版Queue类型。

class SlowAppendQueue[T](elems: List[T]) {

  def head = elems.head

  def tail = new SlowAppendQueue(elems.tail)

  def enqueue(x: T) = new SlowAppendQueue(elems ::: List(x))

}

　　对Queue的操作都可以转换到对List的操作上。但是，对于enqueuq操作，时间复杂度会线性相关于当前Queue对象中的元素个数，不是我们要求的常量时间复杂度。

　　如果将enqueue操作改造成常量时间复杂度的话，将传入的List对象进行reverse后调用以下函数，对于head和tail的操作时间复杂度又不是常量的了，如下所示，

class SlowHeadQueue[T](smele: List[T]) {

  def head = smele.last

  def tail = new SlowHeadQueue(smele.init)

  def enqueue(x: T) = new SlowHeadQueue(x :: smele)

}

　　考虑一下，如果将以上两个函数进行合并，就可以实现三个操作都是常量时间复杂度的Queue了。在最终的Queue类型中维持两个List对象，一个是leading，该对象中保存了Queue对象前半段的元素，另一个对象trailing包含了Queue对象后半段元素的反序列。那么Queue对象最终的元素为leading ::: trailing.reverse。

class Queue[T](private val leading: List[T], private val trailing: List[T]) {

  private def mirror =

    if (leading.isEmpty)

      new Queue(trailing.reverse, Nil)

    else

      this

  def head = mirror.leading.head

  def tail = {

    val q = mirror

    new Queue(q.leading.tail, q.trailing)

  }

  def enqueue(x: T) =

    new Queue(leading, x :: trailing)

}

二、信息隐藏

　　第一节中最后已经实现了最开始我们需要的Queue，但是从实现上看并不完美，因为它将实现细节暴露了出来。即可以在Queue类型的主构造函数中看到该类中有两个List对象。并且，这个Queue对象并不是我们从直观上所理解的那样，因为构造它时居然需要两个List对象，而不是我们直观上想的那样只需要传入一个List对象。

　　接下来从多方面对Queue作进一步的改造，隐藏一些不必要以及对用户不友好的信息。

1、私有构造器和工厂方法

　　我们知道，在Java中可以将一个构造器定义为私有的，从而不对外暴露该类的构造方法。在Scala中一个类的主构造函数由类定义时由类参数以及类的实现间接的定义了。然而，还是可以将Scala的主构造函数使用private关键字进行隐藏，private关键字写在类名和类参数之间，如下所示

class Queue[T] private (

  private val leading: List[T],

  private val trailing: List[T]

)

　　Scala的私有构造方法只能被该类本身，以及该类的伴生对象访问。此时直接使用Queue类的主构造函数生成一个Queue对象，会报以下错误，

　　

　　不能调用主构造函数生成新的Queue对象，就需要提供新的方法了。最先想到的办法就是，新建一个辅助构造函数，通过辅助构造函数来生成Queue对象。比如

def this() = this(Nil, Nil)     // 生成空的Queue

def this(elems: T*) = this(eles.toList, Nil)     // 使用T*，传入多个参数

　　除了辅助构造函数外，我们还可以定义一个外部可以访问的工厂方法来生成新的Queue对象。下面在Queue类文件中新建一个伴生对象Queue，并实现一个apply方法，

object Queue {

  def apply[T](xs: T*) = new Queue[T](xs.toList, Nil)

}

　　由于在伴生对象中定义的工厂方法名为apply，所以在调用该方法时的使用Queue(1, 2, 3)很像直接调用Queue类的构造函数。但是注意，这里实质上是直接调用了伴生对象Queue的apply方法。

2、可选方案：私有对象

　　私有构造器和私有变量是隐藏类信息的一个方法，另一个更加严苛的隐藏方法是直接将该类定义为私有的，再提供给外界一个只包含公有方法的trait。如下所示

trait Queue[T] {

  def head: T

  def tail: Queue[T]

  def enqueue(x: T): Queue[T]

}

object Queue {

  def apply[T](xs: T*): Queue[T] = new QueueImpl[T](xs.toList, Nil)

  private class QueueImpl[T](

    private val leading: List[T],

    private val trailing: List[T]

  ) extends Queue[T] {

    def mirror =

      if (leading.isEmpty)

        new QueueImpl(trailing.reverse, Nil)

      else

        this

    def head: T = mirror.leading.head

    def tail: QueueImpl[T] = {

      val q = mirror

      new QueueImpl(q.leading.tail, q.trailing)

    }

    def enqueue(x: T) = new QueueImpl(leading, x :: trailing)

  }

}

三、协变和逆变

　　这里主要讲到协变和逆变的概念。

　　上面代码中的Queue是trait，而不是一个类型，并且Queue需要接收一个类型参数T。在不指定T的情况下，无法定义Queue类型的对象。比如下面这行代码就会报错，

def doesNotCompile(q: Queue) {}

　　报错如下，

　　

　　因为代码在编译时是不知道T的具体类型是什么的。但是如果为Queue指定一个特殊的类型参数，例如Queue[String], Queue[Int], Queue[AnyRef]，程序就能正常编译，如下所示，

def doesCompile(q: Queue[AnyRef]) {}

　　运行结果如下，

　　

　　Queue在是这里一个泛型trait，而Queue[String]是一个类型。带泛型参数的trait是泛型trait，带泛型参数的类是泛型类。Queue[Int], Queue[String]都是泛型trait Queue[T] 的特定实现形式。

1、协变

　　那么，假设类型S是类型T的子类，Queue[S]是否是Queue[T]的子类呢？如果是的话，那么就可以称Queue对于其类型参数T是协变的。对于这种只有一个类型参数的泛型，可以直接成Queue是协变的。泛型类Queue是协变的，意味着在上面的doesCompile方法中，传入一个Queue[String]类型的参数时程序也能够正常执行，因为这里可以接收的参数类型是Queue[AnyRef]，并且String是AnyRef的子类。

　　

　　虽然从直观理解上，Queue[String]类型是Queue[AnyRef]类型的子类，但是一般情况下，在Scala中泛型类都是非协变的。即在前面的Queue泛型trait代码中，Queue[String]并不是Queue[AnyRef]的子类。

　　如果需要指定泛型类对某个类型参数具有协变性，需要在泛型类定义时最前面那个类型参数前加+符号，指定该泛型类对该指定参数具有协变性。对泛型trait Queue进行协变改造，将其第一行改成如下形式。

trait Queue[+T] {...}

2、逆变

　　有没有想过，在上面的改造代码中，将+换成-，即下面这种情况，是什么情况？

trait Queue[-T] {...}

　　如果你往这方面进行思考了，那么恭喜你，你已经开始尝试逆变的写法了。

　　在这种写法下，如果类型T是类型S的子类，那么Queue[S]是Queue[T]的子类。正好与协变是相反的！

　　

3、可变数据无协变

　　在函数式编程世界里，许多类型天然就具有协变特性。然而，当引入可变数据时(mutable data)，情况就不是这样的了。即经常使用可变数据时，大多数类都不具备协变特性。这是为什么呢？看一下下面这段代码，

class Cell[T](init: T) {

  private[this] var current = init

  def get = current

  def set(x: T) { current = x }

}

　　这段代码中的Cell类既不是协变，也不是逆变的，而是不变的。这段代码可以正常执行，

　　

　　假如我们将Cell定义成Cell[+T]类型，再看一下运行结果，运行报出一个Error信息，

　　

　　为什么会报错？我们暂时性忽略上面的这个报错，假设其可以正常执行。那么继续执行下面这几行代码，

val c1 = new Cell[String]("abc")

val c2: Cell[Any] = c1

c2.set(1)

val s: String = c1.get

　　首先定义一个Cell[String]类型的变量c1，由于具有协变性，接下来将c1赋值给Cell[Any]类型变量c2。由于是引用型变量，实际上c1和c2执行的是同一个具体对象。此时通过c2的set方法，将current变量的值变更成Int型的1，这是不会报错的。接下来再通过c1的get方法，获取current的值。对于c1来说，current是String类型的，但是已经通过c2将其改成了Int类型。这时候c1获取current变量时就会类型不匹配而报错了。

四、下界和上界

1、下界

　　下界使用符合>:表示，比如下面这段代码中表示类型U是类型T的父类，即此处的类型U最少为T，不能比T的类型更低。

def enqueue[U >: T](x: U) = new Queue[U](leading, x :: trailing)

2、上界

　　上界使用符合<:表示，比如T <: U表示需要类型T是类型U的子类，类型T不能比U的类型更高。