Project Euler 27 での C スタック オーバーフロー

Question

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

オイラー.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]]

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

WinHugsを使っています。

Answer 1

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

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

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

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

Answer 2

理由がわからない リトブ 彼の答えを答えではなくコメントに入れて、人々が見ることができるようにここにコピーします。

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

それは正しい答えだと思います。しかし、簡単に言えば、foldr は末尾再帰的ではないということです。

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