4

@tailrecを適用すると、scalaコンパイラからエラーが発生します：「@ tailrec注釈付きメソッドgetを最適化できませんでした：スーパータイプのケース_ => 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

ここで何が起こっているのか、コンパイラに何を求めているのかを想像してみてください。末尾呼び出しの最適化は、大まかに言って、メソッド呼び出しをループに変換し、メソッドの引数を取得して、ループの各反復で再割り当てされる変数に変換します。

ここでは、そのような「ループ変数」が2つあります。1つはメソッドが呼び出されるnリストセル自体で、get実際thisにはメソッド本体にあります。の次の値nは問題ありません。それはn - 1またIntです。リストセルの次の値であるtail、は問題です。ただし、タイプはですthisがCons[T]、tailタイプは。のみList[T]です。

したがって、コンパイラがそれをループに変える方法はありません。これは、であるという保証がないためtailですCons[T]—そして確かに、リストの最後では、それはNilです。

それを「修正」する1つの方法は次のとおりです。

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 objectList[T]T

于 2012-10-15T20:22:20.323 に答える
2

BenとJean-PhillipePelletは、コンパイラが文句を言う理由をすでに説明しています。それを修正する方法に関しては、簡単な解決策があります：get右の実装を：に移動し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 に答える