4

Haskell の学習を始めたばかりで、書籍やチュートリアルを読むことと、Project Euler の問題を解決することを組み合わせています。次のコードを使用すると「C スタック オーバーフロー」エラーが発生するため、問題 27に固執しています。

euler.hs

divisors n = [x | x <- [1..n `div` 2], n `mod` x == 0] ++ [n]
is_prime n = divisors n == [1, n]
f a b = [n^2 + a * n + b | n <- [0..]]
primes_from_zero a b = length(takeWhile is_prime (f a b))

コマンド ウィンドウ

このコマンドは、オイラー係数 1 と 41 (40 個の素数) を返します。

foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [0..10], b <- [0..50]]

これは「Cスタックオーバーフロー」で失敗します（問題の定義にも記載されている係数-79と1601を取得したかった）：

foldr (max) (0, 0, 0) [(primes_from_zero a b, a, b) | a <- [-100..0], b <- [1500..1700]]

エラーが発生する理由と解決方法を教えてください。ありがとうございました！

私はウィンハグを使っています。

4

2 に答える 2

9

「スタック オーバーフロー」エラーは、プログラム内の関数呼び出しのチェーン (エントリ関数から現在実行中の関数まで) が大きくなりすぎたことを意味します。ほとんどのコンパイラとランタイムは、呼び出しチェーンをスタック データ構造として実装します。各要素は、ローカル変数と単一の関数呼び出しのコンテキストを含む "スタック フレーム" であり、サイズは制限されています。

通常、スタック オーバーフローは、再帰関数に問題があることを意味します。たとえば、再帰が終了しない場合、最終的にスタック制限に達して「オーバーフロー」します。再帰が終了しても、呼び出しが多すぎるとオーバーフローする可能性があります。これは非常に大きなリストの場合によくあり、あなたの例にも当てはまるようです。

Haskell (および他の多くの言語) でスタック オーバーフローを回避する 1 つの方法は、末尾再帰関数を記述することです。末尾再帰関数は、唯一の再帰呼び出しが関数の結果である関数です。例えば、

foldl f x (y:ys) = foldl f (f x y) ys

対照的に、foldr末尾再帰ではありません

foldr f x (y:ys) = f y (foldr f x ys)

技術的な理由から、末尾再帰呼び出しは呼び出し元のスタック フレームを再利用できるため、呼び出しスタックが大きくなりません。

(補足:は末尾再帰ではありませんが、リスト全体を評価する必要がない場合があるため、foldrよりも「怠惰」です。これにより、どちらを使用するかを決定できます。)foldl

末尾再帰関数を使用しても、 「スペース リーク」によりメモリが不足する場合があります。たとえば、foldl各再帰呼び出しでは、 の新しいサスペンションが作成され(f x y)ます。foldlは一定のスタック スペースを使用しますが、未評価の への呼び出しには O(n) スペースを使用しfます。厳密さが望ましい場合にこれを回避するには、次を使用できます。foldl'

foldl' f x (y:ys) = (foldl' f $! f x y) ys

ここで、中置演算子$!は厳密な評価を強制します。

于 2008-12-16T14:57:03.247 に答える
3

なぜlitbが彼の回答を回答ではなくコメントに入れたのかわかりません。そのため、人々が見られるようにここにコピーしています。

http://www.haskell.org/haskellwiki/Stack_overflow

正しい答えだと思います。しかし、短いバージョンでは、foldr は末尾再帰ではありません。

この投稿をコミュニティ Wiki としてマークしたので、評判は得られません。

于 2008-12-16T14:08:31.723 に答える