TailCallsの使い方は？

Question

私が正しく理解していれば、scala.util.control.TailCallsを使用して、トランポリンを使用して非末尾再帰関数のスタックオーバーフローを回避できます。 APIに与えられた例は単純です：あなたは recursve呼び出しの後にいくつかの操作を行いたい場合

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 

しかし、より興味深いケースです。私は何とか

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

によって実行されている「ナイーブ」階乗の実装を得たが、これは恐ろしい見て、私はこれが意図された使用であることを疑います。だから私の質問は、TailCallsを使用して階乗またはフィボナッチ関数を正しく書く方法です（はい、私はそれらをテール再帰的に得るためにアキュムレータを使う方法を知っています）？またはTailCallsはこの種の問題には適していませんか？

Answer 1

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

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

ところで、scala.util.control.TailCallsのソースを調べる価値があります。 "結果"呼び出しは、興味深い作業がすべて完了したところです。基本的にはちょっとループです。

Answer 2

この質問は以上6歳ですが、受け入れられた答えは質問に答えるようには見えません。

だから私の質問は、はい（正しくTailCallsを使って階乗やフィボナッチ機能を記述する方法です、私はそれらをテール再帰的に得るためにアキュムレータを使用する方法を知っていますか？

だから、ここにある：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) 

一つは、右の倍のような何かを行うことです。