20

私が正しく理解していれば、scala.util.control.TailCallsを使用して、トランポリンを使用することにより、非末尾再帰関数のスタックオーバーフローを回避できます。APIで与えられた例は簡単です：

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
   if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

ただし、より興味深いケースは、recursve呼び出しの後にいくつかの操作を実行する場合です。私はどういうわけかによって実行されている「ナイーブな」階乗の実装を得ました

def fac(n:Long): TailRec[Long] = 
    if (n == 0) done(1) else done(n * tailcall(fac(n - 1)).result)

しかし、これはひどいように見え、これが意図された使用法であるとは思えません。だから私の質問は、TailCallsを使用して階乗関数またはフィボナッチ関数を正しく作成する方法です（はい、アキュムレータを使用して末尾再帰を取得する方法を知っています）？または、TailCallsはこの種の問題には適していませんか？

4

2 に答える 2

28

はい、素朴な階乗は末尾再帰ではなく、引数の値に線形のスタック空間を使用します。scala.util.control.TailCallsの目的は、非末尾再帰アルゴリズムを魔法のように末尾再帰アルゴリズムに変換することではありません。目的は、相互にテールコールされる関数のサイクルを一定のスタックスペースで実行できるようにすることです。

Scalaコンパイラーは、末尾位置で自分自身を呼び出すメソッドの末尾再帰最適化を実装し、呼び出し元のメソッドのスタックフレームを呼び出し元が使用できるようにします。これは基本的に、裏で証明可能な末尾再帰呼び出しをwhileループに変換することによって行われます。ただし、JVMの制限により、末尾呼び出しの最適化を実装する方法はありません。これにより、末尾位置のメソッド呼び出しで呼び出し元のスタックフレームを再利用できます。これは、テール位置で相互に呼び出す2つ以上のメソッドがある場合、最適化は行われず、スタックオーバーフローのリスクがあることを意味します。scala.util.control.TailCallsは、この問題を回避できるハックです。

ところで、scala.util.control.TailCallsのソースを見る価値は十分にあります。「結果」呼び出しは、すべての興味深い作業が行われる場所であり、基本的には内部のwhileループです。

于 2010-12-13T12:55:09.967 に答える
5

この質問は6年以上前のものですが、受け入れられた回答は質問に回答していないようです。

だから私の質問は、TailCallsを使用して階乗関数またはフィボナッチ関数を正しく作成する方法です（はい、アキュムレータを使用して末尾再帰を取得する方法を知っています）？

だから、ここにあります：

object Factorial {

  /**
    * Returns the nth factorial
    */
  def apply(n: Long): BigInt = {
    if (n < 0)
      throw new IllegalArgumentException("Can't factorial to an index less than 0")
    else {
      import scala.util.control.TailCalls._
      def step(current: Long): TailRec[BigInt] = {
        if (current <= 0)
          done(1)
        else
          tailcall {
            for {
              next <- step(current - 1)
            } yield current * next
          }
      }
      step(n).result
    }
  }

}

assert(Factorial(0) == 1)
assert(Factorial(7) == 5040)
assert(Factorial(10) == 3628800)

TailCallsを使用するための大きなユースケースの1つは、右折りのようなことを行うことです。

于 2016-08-28T15:21:47.550 に答える