Scala 类型系统如何知道 cons + Nil 是穷举的？

Question

我刚刚写了这个函数，想知道如果我省略 Nil 大小写会发生什么，并注意到 scalac 给了我一个警告：

def printList[String](list: List[String]) {
    list match {
        case head :: tail => {
            println(head)
            printList(tail)
        }
        //case Nil => println("Done")
    }
}

Warning: match may not be exhaustive. It would fail on the following input: Nil

我无法准确确定这里发生了什么。在你用尽所有案例之前，我对递归数据类型的模式匹配有一个大致的了解，但我不清楚它是如何映射到 Scala 类型系统的。具体来说，我正在查看 Scala 标准库的源代码并想知道：

Scala 在代码中的确切位置获得了需要基本案例来完成列表实例的匹配语句的想法 class？人们当然可以想象一种 "just keeps going" 没有基本情况的代数数据类型。
代码中的确切位置 scala.collection.immutable.Nil 特别指定为列表的基本情况 class?

Answer 1

其实没有你想的那么复杂。 List 是一个 sealed abstract class，正好有两个实现，Nil 和 ::（是的，这就是 class 的名称）。这里的重要部分是 sealed 修饰符。这只是强制执行任何实现 List 的 class 必须 与 List 本身在同一个源文件中。

sealed 的重要性在于，现在编译器肯定知道 List 的每个可能的实现者，因此如果您对列表进行模式匹配，编译器可以确定您的模式匹配是否块详尽无遗。

最后一件事是 :: 有一些语法糖。通常如果你有一些案例 class:

case class Foo(a: String, b: Int)

你会这样匹配它

x match {
  case Foo(a, b) => //...
}

然而当你有一个案例 class 只有两个成员时，你也可以这样写：

x match {
  case a Foo b => //...
}

所以在你的模式匹配语句中，你确实在做：

list match {
        case ::(head, tail) => {

所以实际上您所做的只是检查 list 是否是 :: 的实例。因此，编译器可以看到您从不检查 list 是否是 Nil 的实例并警告您。

Answer 2

您可以查看 List here 的源代码。基本情况没有什么特别的，只是 List 被声明为 sealed，然后只有两个 class 扩展它：

sealed abstract class List[+A] ...
case object Nil extends List[Nothing] { ... }
final case class ::[B](override val head: B, private[scala] var tl: List[B]) extends List[B] { ... }

Scala 编译器可以很容易地确定密封特征或抽象 class 是否完全匹配，因为它可以确定单个文件中可能匹配的范围。 Section 8.4 of the Scala specification 说：

If the selector of a pattern match is an instance of a sealed class, the compilation of pattern matching can emit warnings which diagnose that a given set of patterns is not exhaustive, i.e. that there is a possibility of a MatchError being raised at run-time.

Scala 类型系统如何知道 cons + Nil 是穷举的？

How does the Scala type system know that cons + Nil is exhaustive?

type-systems

scala

algebraic-data-types