DOT演算中的列表编码

Question

我正在阅读 The Essence of Dependent Object Types 并发现了以下列表编码：

为什么要写：

nil: sci.List ∧ {A = ⊥}

特别是，为什么我们给A型底部？类型不应该像 cons 那样是多态的吗？

Answer 1

Nothing 是 Scala 的底层类型——它是一种没有成员的类型，所以你可以毫不费力地说它的每个成员都是其他类型的成员。

就其自身而言 Nothing（作为 return 类型）用于表示函数从不 returns 值，这通常意味着它会抛出异常。如果你有任何 container/wrapper/factory/however 调用 if of Nothing，这意味着它不能包含 contains/produces 值的 wrapper/whatever 版本：

List[Nothing] - 是一个没有任何值的列表，
Future[Nothing] - 是一个循环运行或以异常结束的 Future
Option[Nothing] - 是选项，不能包含值

当涉及到 List 时，如果您决定使用 Cons+Nil 作为编码，假设您希望在没有任何奇怪的事情的情况下进行编码：

sealed trait List[A]
case class Cons[A](a: head, tail: List[A]) extends List[A]
case class Nil[A]() extends List[A]

你不能简单地使用对象 Nil ，因为你必须在任何地方定义它的类型。所以不幸的是你不能有一个 Nil，但你需要为每种类型单独的 Nil。

Cons(1, Cons(2, Cons(3, Cons(4, Nil[Int]))))

但是，如果你使 List[A] 协变，那么如果 A 是 B 的子类型，那么 List[A] 将是 List[B].[=36 的子类型=]

sealed trait List[+A] // notice + before A
case class Cons[+A](a: head, tail: List[A]) extends List[A]
case class Nil[+A]() extends List[A]

然后我们可以利用 Nothing 作为所有其他类型的子类型：

val nil = Nil[Nothing]
Cons(1, Cons(2, Cons(3, Cons(4, nil))))
Cons("a", Cons("b", Cons("c", Cons("d", nil))))

此时为了我们自己的方便（例如模式匹配），我们可以使 Nil 成为一个对象：

sealed trait List[+A]
case class Cons[+A](a: head, tail: List[A]) extends List[A]
case object Nil extends List[Nothing]

多亏了这一点，我们只需要一个 Nil 而不是每个类型都需要一个。

这就是它在当前 Scala (2) 中的工作方式，并且在 Dotty 中没有改变。您示例中的 DOT 演算显示了这如何转化为形式主义：您使用的不是 Nothing ⊥，其他所有内容基本相同，但符号不同。

DOT演算中的列表编码

List encoding in the DOT calculus

scala

types

dependent-type

dotty

scala-3