3

後で再開するために一時停止できる、長時間実行される計算のメカニズムがあるとします。

sealed trait LongRunning[+R];
case class Result[+R](result: R) extends LongRunning[R];
case class Suspend[+R](cont: () => LongRunning[R]) extends LongRunning[R];

それらを実行する最も簡単な方法は

@annotation.tailrec
def repeat[R](body: LongRunning[R]): R =
  body match {
    case Result(r)   => r
    case Suspend(c)  => {
      // perhaps do some other processing here
      println("Continuing suspended computation");
      repeat(c());
    }
  }

問題は、そのような計算を作成することです。10 サイクルごとに計算を一時停止する末尾再帰階乗を実装したいとします。

@annotation.tailrec
def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
  if (n <= 1)
    Result(acc);
  else if (n % 10 == 0)
    Suspend(() => factorial(n - 1, acc * n))
  else
    factorial(n - 1, acc * n)
}

しかし、これはコンパイルされません:

エラー:@tailrec注釈付きメソッドを最適化できませんでしfactorialた: 末尾位置にない再帰呼び出しが含まれています

Suspend(() => factorial(n - 1, acc * n))

非中断呼び出しで末尾再帰を保持するにはどうすればよいですか?

4

1 に答える 1

4

1つの可能な答えを見つけました。末尾再帰部分を内部関数に移動し、必要に応じて外側の非末尾再帰部分を参照できます。

def factorial(n: Int, acc: BigInt): LongRunning[BigInt] = {
  @annotation.tailrec
  def f(n: Int, acc: BigInt): LongRunning[BigInt] =
    if (n <= 1)
      Result(acc);
    else if (n % 10 == 0)
      Suspend(() => factorial(n - 1, acc * n))
    else
      f(n - 1, acc * n)
  f(n, acc)
}
于 2013-03-11T09:04:45.153 に答える