4

应用 @tailrec 我从 scala 编译器收到错误：“无法优化 @tailrec 带注释的方法 get：它包含一个针对超类型 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))
}
4

3 回答 3

6

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

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

因此，编译器无法将其转换为循环，因为无法保证它tail是 a Cons[T]—— 果然，在列表的末尾，它是 a 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。）

于 2012-10-15T20:22:20.323 回答
2

Ben 和 Jean-Phillipe Pellet 已经解释了编译器抱怨的原因。至于如何解决，有一个直截了当的解决方案：将getright 的实现移入List：

trait List[T] {
  def isEmpty: Boolean
  def head: T
  def tail: List[T]
  @tailrec
  final def get(n: Int): T = {
    n match {
      case 0 => head
      case _ => tail.get(n-1)
    }
  }
}

class Cons[T](val head: T, val tail: List[T]) extends List[T]{
  def isEmpty = false
}

class Nil[T] extends List[T]{
  def isEmpty = true
  def head = throw new NoSuchElementException("Nil.head")
  def tail = throw new NoSuchElementException("Nil.tail")
}
于 2012-10-15T21:29:28.897 回答
2

在Cons.get你打电话tail.get作为你的尾电话。但是tail是类型List[T]，不是Cons[T]。因此该调用不一定由 处理Cons.get，并且 Scala 不能应用尾递归优化；优化会将方法调用转换为本地跳转到 的开头Cons.get，但这不一定是调用的去向。

于 2012-10-15T20:23:43.130 回答