scala - @tailrec 错误 "recursive call targetting a supertype"

Question

应用@tailrec 我从scala 编译器中得到错误:“无法优化@tailrec 注释方法get:它包含一个递归调用，目标是父类(super class)型case _ => tail.get(n-1)”。有人能解释一下这是为什么吗？

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
  def get(n: Int): T
}

class Cons[T](val head: T, val tail: List[T]) extends List[T]{
  def isEmpty = false
  @tailrec
  final def get(n: Int) =
    n match {
      case 0 => head
      case _ => tail.get(n-1)
    }
}

class Nil[T] extends List[T]{
  def isEmpty = true
  def head = throw new NoSuchElementException("Nil.head")
  def tail = throw new NoSuchElementException("Nil.tail")
  final def get(n: Int): T = throw new IndexOutOfBoundsException
}

object Main extends App{
  println(new Cons(4, new Cons(7, new Cons(13, new Nil))).get(3))
}

Answer 1

试着想象这里发生了什么以及你要求编译器做什么。尾调用优化，粗略地说，将方法调用转换为循环，获取方法的参数并将它们转换为在循环的每次迭代中重新分配的变量。

这里有两个这样的“循环变量”:n以及 get 所在的列表单元格本身方法被调用，实际上是this在方法体中。 n 的下一个值很好:它是 n - 1还有一个 Int .列表单元格的下一个值，即 tail , 是一个问题，但是:this有类型 Cons[T] ，但是 tail只有类型 List[T] .

因此，编译器无法将其转换为循环，因为无法保证 tail是 Cons[T] ——果然，在列表的最后，是Nil .

“修复”它的一种方法是:

case class Cons[T](val head: T, val tail: List[T]) extends List[T] {
  def isEmpty = false
  @tailrec
  final def get(n: Int) =
    n match {
      case 0 => head
      case _ => tail match {
        case c @ Cons(_, _) => c.get(n - 1)
        case nil @ Nil() => nil.get(n - 1)
      }
    }
}

(如果 Cons 和 Nil 都是案例类，则有效——但你可能想让 Nil 成为 case object 和 List[T] 协变 T 。)