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

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

先做一个简化的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(署名-相同方式共享)协议下发布。
AP SSC Evs Question 说:
Sep 11, 2022 03:55:09 PM

Advised to everyone can contact the class teacher to get important questions for all lessons and topics of EVS. Every Telugu Medium, English Medium and Urdu Medium student of the State Board can download the AP 10th Class EVS Model Paper 2023 Pdf with answers for term-1 & term-2 exams of SA-1, SA-2 and other exams of the board. AP SSC Evs Question Paper Environmental Education is one of the most important subjects and it’s a part of Science. School Education Department and various leading private school teaching staff have designed and suggested the practice question paper for all Part-A, Part-B, Part-C, and Part-D questions of SA-1, SA-2, FA-1, FA-2, FA-3, FA-4 and Assignments.

reese 说:
Nov 28, 2022 08:10:14 PM

In Scala, the List class has generic upper and lower bounds. This means that the List class can be used with any type that is a subtype of the si joint pain upper bound or a supertype of the lower bound. For example, if the upper bound is set to Any, then the List class can be used with any type. If the lower bound is set to Nothing, then the List class can be used with any type that is a supertype of Nothing.


登录 *


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