4

(カスタム) 継続を構築することにより、構造体の末尾再帰に対する操作を実行しようとしていますが、コンパイラは私のコードが末尾再帰であることを受け入れません。末尾以外の位置で再帰関数を参照する関数リテラルを宣言しようとするとすぐに、ここで関数を呼び出していなくてもエラーがスローされます。以下は、何がエラーをトリガーするかについての非常に単純化されたダミーの例です。

import scala.annotation.tailrec
object Test extends App {
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

私は得る

could not optimize @tailrec annotated method tailrectest: it contains a recursive call not in tail position

の行を参照していますval x = () => tailrectest(10)

4

2 に答える 2

8

この問題は、（再帰的な）呼び出しを関数変数に埋め込むと、コンパイラーは一般に、それが呼び出されるかどうかを推測できないという事実によって引き起こされると思いますx（この単純なケースでは可能ですが）。したがって、安全のために、関数の本体で発生する再帰呼び出しについて不平を言います。

再帰呼び出しを変数に入れると、その変数は関数から逃げることができます (たとえば、関数によって返されるか、グローバル状態に格納されるなど)。したがって、末尾再帰サイクルとして最適化することはできなくなります。

x具体的な解決策を見つけられるように、使用方法を投稿してください。

于 2012-09-10T17:35:02.917 に答える
5

Petr Pudlákの答えに完全に同意します。しかし、それだけの価値があるため、抜け道があります。ヘルパー メソッドを定義して、ラッパー関数を tailrectest に返します。

import scala.annotation.tailrec
object Test extends App {
  def tailrectest_ = tailrectest _
  @tailrec
  def tailrectest(i: Int): Int = i match {
    case i if i > 0 => {
      val x = () => tailrectest_(10)
      tailrectest(i - 1)
    }
    case 0 => 0
  }
}

これにより、コードに多少のノイズが追加されますが、少なくとも機能します。

しかし、あなたがやろうとしていることがある種の継続を構築することである場合、実際のコードは確実にクロージャ内のローカル コンテキストをキャプチャする必要があり、上記のソリューションを排除します。この場合、簡単な方法がわかりません。

更新(2013 年 3 月 11 日):

Petr Pudlak found a similar but superior solution in another question: http://stackoverflow.com/questions/15334611/how-to-make-a-tail-recusive-method-that-can-also-refer-to-itself-in-a-non-tail-r

By using an inner function, we can actually capture local state, which make it fully usable. Here is his solution, applied to entropyslave's original question:

import scala.annotation.tailrec

object Test extends App {
  def tailrectest(i: Int): Int = {
    @tailrec
    def tailrectestImpl(i: Int): Int = {
      i match {
        case i if i > 0 =>
          val x = () => tailrectest(10)
          tailrectestImpl(i - 1)
        case 0 => 0
      }
    }
    tailrectest( i )
  }
}
于 2012-09-10T19:17:37.097 に答える