21

Haskellの末尾再帰を理解しようとしています。私はそれが何であるか、そしてそれがどのように機能するかを理解していると思いますが、私は物事を台無しにしないことを確認したいと思います。

「標準」の階乗の定義は次のとおりです。

factorial 1 = 1
factorial k = k * factorial (k-1)

たとえば、実行しているときfactorial 3、私の関数はそれ自体を3回呼び出します（与えるか取るか）。スタックオーバーフローが発生する可能性があるため、階乗99999999を計算したい場合、これは問題を引き起こす可能性があります。到達した後factorial 1 = 1、スタックに「戻って」すべての値を乗算する必要があるため、6つの操作があります（関数自体を呼び出すための3つと、値を乗算するための3つ）。

ここで、別の可能な階乗実装を示します。

factorial 1 c = c
factorial k c = factorial (k-1) (c*k)

これも再帰的です。自分自身を3回呼び出します。しかし、関数の引数としてすでに結果を渡しているので、すべての結果の乗算を計算するために「戻ってくる」必要があるという問題はありません。

これは、私が理解していることですが、末尾再帰についてです。今では、最初のものよりも少し良いように見えますが、それでもスタックオーバーフローを簡単に発生させることができます。Haskellのコンパイラは、末尾再帰関数を舞台裏でforループに変換すると聞いています。それが末尾再帰関数を実行することで報われる理由だと思いますか？

それが理由である場合、コンパイラがこの賢いトリックを実行しないのであれば、関数を末尾再帰にしようとする必要はまったくありません-私は正しいですか？たとえば、理論的にはC＃コンパイラは末尾再帰関数を検出してループに変換できますが、現在はそれを行わないことを私は知っています（少なくとも私が聞いたことはそうです）。したがって、関数を末尾再帰にすることには、今日ではまったく意味がありません。それですか？

ありがとう！

4

2 に答える 2

37

ここには2つの問題があります。1つは一般的な末尾再帰であり、もう1つはHaskellが物事を処理する方法です。

末尾再帰に関しては、定義が正しいようです。便利なのは、各再帰呼び出しの最終結果のみが必要なため、以前の呼び出しをスタックに保持する必要がないことです。関数は、「それ自体を呼び出す」代わりに、それ自体を「置き換える」ことに近い何かを実行します。これは、反復ループのように見えます。これは、まともなコンパイラが一般的に提供する非常に簡単な最適化です。

2番目の問題は遅延評価です。Haskellは必要に応じて式を評価するだけなので、デフォルトでは末尾再帰は通常の方法ではうまく機能しません。各呼び出しを途中で置き換える代わりに、「サンク」の巨大なネストされたパイル、つまり、値がまだ要求されていない式を構築します。このサンクパイルが十分に大きくなると、実際にスタックオーバーフローが発生します。

Haskellには、何をする必要があるかに応じて、実際には2つの解決策があります。

  • 結果がネストされたデータコンストラクターで構成されている場合（リストの作成など）、末尾再帰を回避する必要があります。代わりに、コンストラクターフィールドの1つに再帰を入れてください。これにより、結果も遅延し、スタックオーバーフローが発生しなくなります。

  • 結果が単一の値で構成されている場合は、それを厳密に評価して、最終的な値が必要になるとすぐに再帰の各ステップが強制されるようにします。これにより、末尾再帰に期待される通常の疑似反復が得られます。

また、GHCは非常に巧妙であり、最適化を使用してコンパイルすると、評価が厳密である必要がある場所を見つけて、それを処理することがよくあります。ただし、これはGHCiでは機能しません。

于 2010-11-04T00:37:01.260 に答える
9

組み込みのメカニズムを使用する必要があります。そうすれば、関数を末尾再帰にする方法を考える必要がなくなります。

fac 0 = 1
fac n = product [1..n]

または、製品がまだ定義されていない場合：

fac n = foldl' (*) 1 [1..n]

（使用するフォールド...バージョンについては、 http：//www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27を参照してください）

于 2010-11-04T12:06:02.663 に答える