如果 A 的通用子类型被声明为 return 参数，为什么我不能 return A 的具体子类型？

Question

abstract class IntTree
object Empty extends IntTree
case class NonEmpty(elem: Int, left: IntTree, right: IntTree) extends IntTree

def assertNonNegative[S <: IntTree](t: S): S = {
  t match {
    case Empty => Empty  // type mismatch, required: S, found: Empty.type
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegatve(left), assertNonNegative(right)) // req: S, fd: NonEmpty.type
  }
}

这是我尝试实现带有签名 def assertNonNegative[S <: IntTree](t: S): S 的函数的失败尝试。除了将签名更改为 def assertNonNegative(t: IntTree): IntTree，我找不到实现它的方法。

例子的相关性：
在课程 "Functional Programming Principles in Scala" 中有关子类型化和泛型 (4.4) 的视频中，Martin Odersky 使用了几乎相同的示例（IntSet 而不是 IntTree）并表示此签名可用于表示该函数将 Empty 转换为 Empty 并且非空到非空。他说其他签名在大多数情况下都很好，但如果需要，带有上限 S 的签名可能是更精确的选择。但是，他没有显示该功能的实现。

我在这里错过了什么？

Answer 1

方法右侧（模式匹配）

t match {
  case Empty => Empty 
  case NonEmpty(elem, left, right) =>
    if (elem < 0) throw new Exception
    else NonEmpty(elem, assertNonNegatve(left), assertNonNegative(right)) 
}

表示在运行时检查t是否是class的实例Empty$（对象Empty）然后选择第一个分支否则是否t是class的实例NonEmpty然后选择第二个分支

签名

def assertNonNegative[S <: IntTree](t: S): S

意味着在编译时检查每个类型 S，它是类型 IntTree 的子类型，如果方法接受类型 S 的参数 t然后方法 returns 一个 S.

类型的值

代码未编译，因为方法的定义与其签名不对应。 IntTree 的子class 是NonEmpty 和Empty（对象）。如果 IntTree 未密封，您可以创建不同于 Empty 和 NonEmpty 的子 class，您甚至可以在运行时动态创建它们。但是我们甚至假设 IntTree 是密封的并且 Empty 和 NonEmpty 是它唯一的子class。

问题是 IntTree 有很多子类型（classes 和类型是 different）：IntTree、Empty.type、 NonEmpty, Nothing, Null, Empty.type with NonEmpty, NonEmpty with SomeType, Empty.type with SomeType, IntTree with SomeType, T (type T <: IntTree), x.type (val x: IntTree = ???) 等，并且对于所有这些，必须满足条件 (t: S): S。

显然这不是真的。例如我们可以取t = Empty.asInstanceOf[Empty.type with Serializable]。它的类型为 Empty.type with Serializable。在运行时它匹配 class Empty （对象）所以第一个分支被选中。但是在编译时我们还不知道这一点，你怎么能在编译时保证返回的 Empty 和 NonEmpty 的类型都是 Empty.type with Serializable?

修复assertNonNegative的一种方法是编写诚实的单态

def assertNonNegative(t: IntTree): IntTree = {
  t match {
    case Empty => Empty
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }
}

另一种是假装多态签名是正确的

def assertNonNegative[S <: IntTree](t: S): S = {
  (t match {
    case Empty => Empty
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }).asInstanceOf[S]
}

第三种是使用类型标签

def assertNonNegative[S <: IntTree : TypeTag](t: S): S = {
  t match {
    case Empty if typeOf[S] == typeOf[Empty.type] => Empty.asInstanceOf[S]
    case NonEmpty(elem, left, right) if typeOf[S] == typeOf[NonEmpty] =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right)).asInstanceOf[S]
    case _ => ???
  }
}

第四是让ADT更加类型化

sealed trait IntTree
object Empty extends IntTree
case class NonEmpty[L <: IntTree, R <: IntTree](elem: Int, left: L, right: R) extends IntTree

并定义类型 class

def assertNonNegative[S <: IntTree](t: S)(implicit ann: AssertNonNegative[S]): S = ann(t)

trait AssertNonNegative[S <: IntTree] {
  def apply(t: S): S
}
object AssertNonNegative {
  implicit val empty: AssertNonNegative[Empty.type] = { case Empty => Empty }
  implicit def nonEmpty[L <: IntTree : AssertNonNegative, 
                        R <: IntTree : AssertNonNegative]: AssertNonNegative[NonEmpty[L, R]] = {
    case NonEmpty(elem, left, right) =>
      if (elem < 0) throw new Exception
      else NonEmpty(elem, assertNonNegative(left), assertNonNegative(right))
  }
}

Soundness 类型系统意味着有时我们在编译时拒绝某些程序，而它们在运行时不会出错。例如

val x: Int = if (true) 1 else "a"

如果 A 的通用子类型被声明为 return 参数，为什么我不能 return A 的具体子类型？

Why can't I return a concrete subtype of A if a generic subtype of A is declared as return parameter?

generics

tree

scala

pattern-matching

type-bounds