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

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

先做一个简化的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（署名-相同方式共享）协议下发布。
Small_feed 评论 (6)
1
[回复]
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.

2
[回复]
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.

3
[回复]
charlly 说:
Jan 18, 2023 12:17:42 PM

There are many reasons why you might want to order a custom essay. Maybe you're struggling with the material and need a little extra help. Maybe you're a great student but just don't have the time to write an essay. Maybe you need a specific type of essay that isn't available anywhere else. Whatever the reason, what are the different cuts of diamonds there are many places you can go to order a custom essay.

4
[回复]
WiFi Names 说:
Feb 03, 2023 06:35:53 PM

Are you getting yourself a new WiFi router, then you might be happy because now you are able to set up your best WiFi names to your liking which is a funny act but a please to do indeed. WiFi Names Well as you already know that the reason why people be objective about finding the best WiFi names for their new connections or routers is that they want some cool or funny names that make them feel nice and at the same time when your friends, family.

6
[回复]
BSEB 10th Blueprint 说:
Jul 14, 2023 03:55:42 PM

BSEB 10th Blueprint 2024 Bihar School Examination Board (BSEB) is a Statutory body under Government of Bihar Devised to Conduct Examinations at Secondary Standard in both Government and Private Schools Belonging to State of Bihar, Bihar Board Every Year Conducted 10th Class Final Exam beginning of the Month of February. BSEB 10th Class Public Exam are Expected to be Conducted in Two Shifts. The First BSEB 10th Blueprint 2024 Shift is from 9:30 AM to 12:30PM in the Morning. While the Second Shift is from 1:45 PM to 4:30 PM at Noon. Students can Download the Bihar Board 10th Blueprint 2024 From the Official Website, Bihar Board are also equally Responsible to Set the Bihar Board 10th Exam Pattern which will Determine the Type of Marks Distribution, We have Provide BSEB Matric Blueprint 2024 for Official Language Hindi, English Medium All Subjects.


登录 *


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