1

Haskell のすべての関数は末尾再帰であるべきだと思いました。

非末尾再帰関数として実装された階乗関数:

fact 0 = 1
fact n = n * fact (n - 1)

すべての演算子も関数なので、これは次と同等です

fact 0 = 1
fact n = (*) n (fact (n - 1))

しかし、これは明らかに私にとってテールコールです。すべての呼び出しがヒープに新しいサンクを作成するだけなのに、なぜこのコードがスタック オーバーフローを引き起こすのか疑問に思います。ヒープ オーバーフローは発生しませんか?

4

1 に答える 1

2

コード内

fact 0 = 1
fact n = (*) n (fact (n - 1))

あなたが観察したように、最後(*) ...はテールコールです。ただし、最後の引数fact (n-1)は、 によってすぐに要求されるサンクを作成し(*)ます。これにより、 への非末尾呼び出しが発生しfactます。再帰的に、これはスタックを消費します。

TL;DR: 投稿されたコードはテール コールを実行しますが、実行(*)しません。

(また、Haskell の「スタック」は、厳密な言語ほど明確な概念ではありません。Haskell の一部の実装では、それよりも複雑なものを使用しています。詳細が必要な場合は、「プッシュ/入力 vs 評価/適用」戦略を検索できます。 .)

于 2015-03-30T08:16:24.790 に答える