F＃/SCALAで相互再帰を最適化する標準的な方法は何ですか？

StackOverflow https://stackoverflow.com/questions/2798831

質問

これらの言語は相互に再帰的な機能の最適化「ネイティブに」をサポートしていないので、トランポリンでなければならないと思います。

更新：私はfsharpについて嘘をついていたようですが、グーグル中に相互のテールコールの例を見ていませんでした

役に立ちましたか？

解決

まず第一に、F＃は相互に再帰的な機能をネイティブにサポートしています。 tailcall .NET ILで利用可能な命令（MSDN）。ただし、これは少し注意が必要であり、.NETの代替実装（コンパクトフレームワークなど）には機能しない可能性があるため、手作業で対処する必要がある場合があります。

一般的に、私はそれに対処する方法がいくつかあります：

  • トランポリン - 再帰の深さが高すぎるときに例外を投げ、例外を処理するトップレベルのループを実装します（例外は通話を再開するために情報を運びます）。例外の代わりに、関数を再度呼び出す必要があることを指定する値を単純に返すこともできます。

  • タイマーを使用してリラックスします - 再帰の深さが高すぎると、タイマーを作成し、非常に短い時間の後にタイマーによって呼び出されるコールバックを与えます（タイマーは再帰を継続しますが、使用済みスタックはドロップされます）。

    同じことを、必要な作業を保存するグローバルスタックを使用して実行できます。タイマーをスケジュールする代わりに、スタックに関数を追加します。トップレベルでは、プログラムはスタックから関数を選択して実行します。

最初の手法の具体的な例を示すために、F＃でこれを書くことができます。

type Result<´T> =
  | Done of ´T
  | Call of (unit -> ´T)

let rec factorial acc n = 
  if n = 0 then Done acc
  else Call(fun () -> factorial (acc * n) (n + 1))

これは、相互に再帰的な機能にも使用できます。命令的なループは単に呼び出します f で保存されている関数 Call(f) それが生成されるまで Done 最終結果で。これはおそらくこれを実装する最もクリーンな方法だと思います。

この問題に対処するための他の洗練されたテクニックがあると確信していますが、それらは私が知っている（そして私が使用した）2つです。

他のヒント

Scala 2.8で、 scala.util.control.TailCalls:

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

F＃相互再帰のためにビングするときにコードを手元に置くためだけに：

let rec isOdd x =
    if x = 1 then true else isEven (x-1)
and isEven x = 
    if x = 0 then true else isOdd (x-1)

printfn "%A" (isEven 10000000)

これは、テールコールなしでコンパイルするとStackOverFlow（デフォルトのデフォルトで、スタックをデバッグしやすくします）が、テールコール（デフォルトの「リリース」モード）でコンパイルされたときに正常に実行されます。コンパイラはデフォルトでテールコールを行います（ -TailCallsオプション）、およびほとんどのプラットフォームでの.NET実装はそれを尊重します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top