scala - 递归函数中的多态 scala 返回类型

Question

我有一个树结构:

sealed trait Tree
case class Node(l: Tree, r: Tree) extends Tree
case class Leaf(n: Int) extends Tree

还有一个修改树的函数:

def scale(n: Int, tree: Tree): Tree = tree match {
  case l: Leaf => Leaf(l.n * n)
  case Node(l, r) => Node(scale(n, l), scale(n, r))
}

上面方法的签名应该是什么才能返回 Tree 的适当子类型，并使以下行编译？

scale(100, Leaf(1)).n // DOES NOT COMPILE

到目前为止我找到的最接近的答案是 here并谈论 F-Bounded Quantification .但是我找不到将其应用于递归结构(例如树)的方法!有任何想法吗？

Answer 1

在 scala 中，通常有两个选项可以为类型定义函数。一个功能更强大(像您一样使用模式匹配)，另一个更面向对象。

不幸的是，我没有使用模式匹配的版本的解决方案(尽管我会对一个感兴趣)。但是我有一个更面向对象的版本的解决方案，如果这是你的一个选择:

sealed trait Tree {
  def scale(n: Int): Tree
}
case class Node(l: Tree, r: Tree) extends Tree {
  def scale(n: Int): Node = Node(l.scale(n), r.scale(n))
}
case class Leaf(n: Int) extends Tree {
  def scale(m: Int): Leaf = Leaf(n * m) 
}

Leaf(1).scale(100).n // does compile.

这个解决方案是基于一个方法的返回类型是协变的，所以 scale的实现中的返回类型在 Node和 Leaf可以是抽象方法返回类型的子类型 scale在 Tree .