Scala 参数化类型

如何构造一个效率高的队列呢？也就是 head，tail，enqueue所花费的时间不应当随队列的大小而改变，一个简单的实现可以使用 List 类来实现，但 enqueue 操作的时间和队列的长度成正比，这里给出一个使用两个 List 对象的队列实现，具体算法不解释了（本专题侧重点不在算法本身）可以实现一个高效的队列操作。

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)
}

使用这个实现，进行一些基本的队列操作：

scala> val q = new Queue(List(1,2,3),Nil)
q: Queue[Int] = Queue@24cc40b6

scala> val q1 = q enqueue 4
q1: Queue[Int] = Queue@67825189

scala> q
res0: Queue[Int] = Queue@24cc40b6

scala> val p = q1 head
p: Int = 1

scala> q1
res1: Queue[Int] = Queue@67825189

这个实现满足功能需求，但我们希望可以实现如下的形式：

scala> val q = Queue(1,2,3)
q: Queue[Int] = Queue(1,2,3)

scala> val q1 = q enqueue 4
q1: Queue[Int] = Queue(1,2,3,4)

scala> q
q: Queue[Int] = Queue(1,2,3)

在之后的文章我们逐步的优化这个实现。

2

信息隐藏

上篇的 Queue 的实现在效率上来说还是比较高效的，但是却给类的使用者暴露一些不必要的实现细节，比如 Queue 的构造函数使用了两个 List 对象，其中一个还是个倒序的列表。本篇介绍如何隐藏这些不必要的信息。

在 Java 中，你可以使用私有的构造函数来隐藏构造函数，在 Scala 中的主构造器缺省包含在类定义中，但你还是可以使用private来修改其访问属性。

例如：

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

在类名和参数之间的 private 修饰符表明该构造器是私有的，只能在类或其伙伴对象之中使用。而类本身还是可以公开访问的：

scala> new Queue(List(1,2),List(3))
<console>:9: error: constructor Queue in class Queue cannot be accessed in object $iw
new Queue(List(1,2),List(3))
^

由于主构造器变成私有的，因此我们需要另外的方式来构造 Queue 的实例，一种方法是使用辅助构造器，比如如下的辅助构造函数：

def this() =this(Nil,Nil)

def this(elem: T*) = this (elems.toList,Nil)

注意，参数类 T* 代表的不定长参数类型。

另外一种方法是使用 Factory 方法来构造一个队列。一个比较简洁的方法是使用伙伴对象，并定义 apply 方法，比如：

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

我们使用 apply 定义了构造 Queue 的 factory 方法，因此调用时可以使用 Queue(1,2,3)的形式来构造一个实例。 Queue(1,2,3)实际为 Queue.apply(1,2,3)调用，对调用者来说看起来好像定义了一个可以全局访问的 factory 构造方法。而其实对于 Scala 来说，所有的方法都必须包含着某个类或对象中。

除了使用私有方法来隐含实现细节外，还有一种方法可以实现信息的隐藏。我们可以使用 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]{
private def mirror =
if (leading.isEmpty)
new QueueImpl(trailing.reverse, Nil)
else
this
def head = mirror.leading.head
def tail = {
val q = mirror
new QueueImpl(q.leading.tail, q.trailing)
}
def enqueue(x: T) =
new QueueImpl(leading, x :: trailing)
}
}

这个实现定义一个 Public 的 Trait 方法，而隐藏了所有的实现细节。

3

Variance(类型变体)标识

在上篇例子中定义的 Queue 是一个 Trait，而不是一个类型，这是因为 Queue 需要一个类型参数才能构成一个类型，也就是说你不可以直接创建一个类型为 Queue 的对象：

scala> def doesNotCompile(q:Queue) {}
<console>:8: error: trait Queue takes type parameters
def doesNotCompile(q:Queue) {}
^

实际上，Queue 允许你指明类型参数，比如 Queue[String]，Queue[Int]或 Queue[AnyRef]等，因此 Queue 也可以称为一个类型构造器，因为你可以指明一个参数类型后构造一个新的类型。

Queue 也可以称为一个通用 Trait（包含类型参数的类或 Trait称为“generic”) ，而指明了类型参数之后就不再是通用类型，而是特定的类型了，比如Queue[String]等。

类型参数和派生结合起来之后，就会产生一些有趣的问题，比如 String 是 AnyRef 的子类，那么 Queue[String]和 Queue[AnyRef]之间会不会有什么继承关系呢？

在 Scala 中，可以有三种不同的关系，缺省情况比如 Queue[T]，Queue[String]和 Queue[AnyRef]不存在继承关系。此外 Scala 还支持两种关系： Covariance（协变关系）和 Contravariance(逆变关系），分别以 Queue[+T]和 Queue[-T] 代表。

Covariance（协变关系）是在类型前面使用“+”号，表示如果两个类型 T，S 如果 T 是 S 的子类，那么 Queue[T]也是 Queue[S]的子类

而 Contravariable（逆变关系）则相反，如果如果两个类型 T，S 如果 T 是 S 的子类，反过来，Queue[S]是 Queue[T]的子类。

我们以一个具体的例子来说明一下，比较直观，定义三个类

GrandParent ,Parent, Child ：
class GrandParent
class Parent extends GrandParent
class Child extends Parent

class Box[+A]
class Box2[-A]

def foo(x : Box[Parent]) : Box[Parent] = identity(x)
def bar(x : Box2[Parent]) : Box2[Parent] = identity(x)

那么我使用下面的几种调用方法来看看+A 和-A 的不同之处：

scala> foo(new Box[Child]) // success
res1: Box[Parent] = Box@5da444e4

scala> foo(new Box[GrandParent]) // type error
<console>:12: error: type mismatch;
found : Box[GrandParent]
required: Box[Parent]
foo(new Box[GrandParent]) // type error
^

scala> bar(new Box2[Child]) // type error
<console>:13: error: type mismatch;
found : Box2[Child]
required: Box2[Parent]
bar(new Box2[Child]) // type error
^

scala> bar(new Box2[GrandParent]) // success
res4: Box2[Parent] = Box2@59615389

[T]，[+T]，[-T]为类型参数的三种不同的变体。使用+，-称为类型的变体标识。

在纯函数编程的世界中，很多类型存在非常明显的协变关系，但是一但出现可变的数据时，情况就发生了变化，比如我们看看下面的例子：

class Cell[T](init:T) {
private[this] var current = init
def get = current
def set(x:T) { current = x}
}

如果我们假定我们定义的是 Cell[+T]而不是上面例子中的 Cell[T]（实际上编译器会在使用 Cell[+T]时报错，我们啦看看为什么？假定我们使用的是 Cell[+T]来定义，那么我们可以写如下代码：

val c1 = new Cell[String]("abc")
val c2: Cell[Any] = c1
c2.set(1)
val s:String = c1.get

这四行代码看起来都没有错（假定我们使用的是 Cell[+T]，那么 Cell[String] 是 Cell[AnyRef]的子类，因此 c2 可以使用 c1 赋值）。最后的结果我们是把整数 1 赋值给了这字符串类型，这就造成了类型不匹配，这也是为什么编译器在使用 Cell[+T]会报错：

<console>:10: error: covariant type T occurs in contravariant position in type T of value x
def set(x:T) { current = x}

要注意的是在 Scala 中，Array[T]不是协变关系的，因此 Array[String]不是 Array[Any]的子类。因此不可以直接把 Array[String]类型的变量赋值给 Array[Any]类型的变量，例如：

scala> val a1=Array("abc")
a1: Array[String] = Array(abc)

scala> val a2:Array[Any] = a1
<console>:8: error: type mismatch;
found : Array[String]
required: Array[Any]
Note: String <: Any, but class Array is invariant in type T.
You may wish to investigate a wildcard type such as `_ <: Any`. (SLS 3.2.10)
val a2:Array[Any] = a1

但是有时需要这种赋值，Scala 允许你把特殊类型的数组强制转换成其父类型的数组，例如：

scala> val a2 :Array[Object] = a1.asInstanceOf[Array[Object]]
a2: Array[Object] = Array(abc)

4

类型下界

我们还是使用前面的 Queue 的例子，我们知道，我们不能使用+T（协变关系）来定义 Queue，然而，我们可以通过给 equeue 方法本身提供一个类型参数使之一般化。

class Queue[+T] ( private val leading: List[T],
private val trailing: List[T] {
def enqueue[U >: T ](x: U) =
new Queue[U](leading, x:: trailing)
}

在这个新定义中，使用了一个新的类型参数 U，语法结构 U >: T ，定义 T 为 U 的下界，因此U必须是 T 的一个父类。 enqueue 的返回类型也变成 Queue[U]，而不是之前的 enqueue[T]。

举例来说，比如说一个 Fruit 类定义了两个子类 Apple 和 Orange，使用这个新的 enqueue 定义，可以把一个 Orange 对象添加到一个 Queue[Apple]队列中，其返回结果为一个Queue[Fruit]类型。

5

类型上界

本篇介绍类型上界，我们使用合并排序算法来给人名排序，这里先定义一个 Person 类，它派生于 Ordered Trait，定义如下：

class Person(val firstName:String, val lastName:String)
extends Ordered[Person]{
def compare(that:Person) ={
val lastNameComparison=
lastName.compareToIngnoreCase(that.lastName)
if(lastNameComparison!=0)
lastNameComparison
else
firstName.compareToIngnoreCase(that.firstName)
}
override def toString= firstName + " " + lastName
}

我们先测试一下这个类对象之间的比较关系，注意 Ordered Trait 定义了对象之间的<，>，>=，<=关系。

scala> val robert=new Person("Robert","Jones")
robert: Person = Robert Jones

scala> val sally = new Person("Sally","Smith")
sally: Person = Sally Smith

scala> robert < sally
res1: Boolean = true

scala> james == james1
res2: Boolean = false

我们定义 merge sort 算法如下：

def orderedMergeSort[T <: Ordered[T]] (xs: List[T]):List[T] ={
def merge(xs:List[T],ys:List[T]):List[T] =
(xs ,ys ) match {
case (Nil, _) => ys
case (_,Nil) => xs
case (x:: xs1,y :: ys1 ) =>
if (x < y) x:: merge(xs1,ys)
else y :: merge( xs,ys1)
}
val n = xs.length /2
if(n==0) xs
else {
val (ys, zs)= xs splitAt n
merge(orderedMergeSort(ys),orderedMergeSort(zs))
}
}

这个函数要求输入的参数的类型需要派生于 Ordered trait，此时你需要使用类型上界，类型上界使用 <:，如本例中的 T <: Ordered[T] ，它代表类型 T 的上界是 Ordered[T]，也就是说传入的参数类型必须是类型 Ordered[T]的子类。

我们之前定义的 List[Person] 满足这个条件。比如：

scala> val sortedPeople=orderedMergeSort(people)
sortedPeople: List[Person] = List(Anders Hejlsberg, Alan Kay, Yukihiro Matsumoto, Guido van Rossum, Larry Wall

scala 教程

「喜欢这篇文章，您的关注和赞赏是给作者最好的鼓励」

关注作者

Scala 参数化类型

Table of Contents

适用人群

学习前提

版本信息

1

2

3

4

5

评论