Scala List的协变特性——泛型上界与下界

deltamaster posted @ Jun 19, 2014 09:36:57 PM in Scala with tags scala 函数 泛型 Functional Programming Liskov 协变 逆变 , 2680 阅读

先做一个简化的List定义,List对象由head(第一个元素)和tail(除了第一个元素以外所有后续元素组成的List)组成。Nil是空List对象,由于不论List的泛型类型是什么,空List的含义和行为都没有区别,因此全局只需要存在一个空List对象即Nil。

trait List[+T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
}

class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
}

object Nil extends List[Nothing] {
  def isEmpty: Boolean = true
  def head: Nothing = throw new NoSuchElementException("Nil.head")
  def tail: Nothing = throw new NoSuchElementException("Nil.tail")
}

这样就完成了List的定义。我们可以通过下面的方式来定义List对象了。

  val x: List[String] = Nil
  val ages: List[Int] = new Cons(16, new Cons(22, Nil))

首先让我们注意一下Nil的定义,Nil这个单例对象所属的类,继承自List[Nothing],为什么可以将List[String]类型的x定义为这个对象?因为泛型类型T是协变的,而Nothing在Scala中是所有其他类的子类。所以List[Nothing]就是List[String]的子类,根据Liskov替换原则,这样的定义是合法的。

下面,我们要像List类增加一个prepend方法,用来生成一个新List,这个新List是在原List头部新增一个元素:

trait List[+T] {
  // omit other methods
  def prepend(elem: T): List[T] = new Cons(elem, this)
}

但是这样的做法是无法通过编译的。为什么?正如上一篇博客所解释的,协变类型不能作为方法的参数类型。而这样的prepend操作看似是非常符合常理的,那么是Scala的这个规则设定不合理吗?

我们再回想一下Liskov替换原则。如果Bird是Animal的子类,那么List[Bird]就是List[Animal]的子类,那么如果List[Animal]可以prepend一个Animal类型的实例,List[Bird]也可以prepend一个Animal类型的实例,可惜按照上面的定义是不可能的,因此违反了Liskov替换原则,这样的定义是错误的。

为了解决这个问题,我们需要引入泛型类型的下界的概念。

trait List[+T] {
  // omit other methods
  def prepend[U >: T](elem: U): List[U] = new Cons(elem, this)
}

这个定义的含义是,prepend方法接受一个类型为U的参数,U必须是T或T的父类(“>:”表示泛型类型的下界,而“<:”则相应地表示上界),返回类型则是List[U]。拿Animal和Bird的例子,再假设Chicken是Bird的子类,那么根据这种定义,List[Bird]可以prepend一个Animal的实例,返回List[Animal],而prepend一个Chicken的实例并非不允许,而是U类型不会是Chicken,必须将U类型至少提升至Bird,所以prepend一个Chicken的实例,结果是返回List[Bird]。这样的定义满足Liskov替换原则,所有可以对List[Animal]进行的操作,都可以对List[Bird]进行。

接下来再举一个例子,假设BaldEagle和CrownEagle都是Aeroplane的子类,而BaldEagle和CrownEagle没有关系。那么List[BaldEagle]如果prepend一个CrownEagle的实例会是什么结果呢?类型U不能是CrownEagle,而必须被向上提升直到U是BaldEagle或者BaldEagle的父类,因此U将被提升到Aeroplane,所以结果将是返回List[Aeroplane]。

这样,可以容易地推断出Scala对于泛型上下界的规定。

  • 协变类型可以作为泛型类型的下界
  • 逆变类型可以作为泛型类型的上界
* 本文在CC BY-SA(署名-相同方式共享)协议下发布。

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter