Переполнение стека C в Project Euler 27

Question

Я только начал изучать Haskell и совмещать чтение книг и учебные пособия с решением проблем из Project Euler. Я застрял на Проблема 27 , потому что я получаю ошибку «Переполнение стека C» с помощью этого кода:

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]]

Подскажите, пожалуйста, почему возникает ошибка и как ее устранить? Спасибо!

Я использую WinHugs.

Answer 1

Ошибка «переполнение стека» означает, что цепочка вызовов функций в вашей программе (от функции ввода до выполняемой в данный момент функции) стала слишком большой. Большинство компиляторов и сред выполнения реализуют цепочку вызовов как структуру данных стека - каждый элемент представляет собой «кадр стека», содержащий локальные переменные и контекст одного вызова функции - с ограниченным размером.

Обычно переполнение стека означает, что с рекурсивной функцией что-то не так. Например, если рекурсия никогда не заканчивается, она в конечном итоге достигнет предела стека и «переполнится». Даже если рекурсия заканчивается, она может переполниться, если просто слишком много вызовов. Это часто имеет место с очень большими списками, и, похоже, имеет место с вашим примером.

Один из способов избежать переполнения стека в Haskell (и многих других языках) - написать хвост-рекурсивные функции . Хвосто-рекурсивная функция - это та, в которой единственный рекурсивный вызов является результатом функции. Например,

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

Я не знаю, почему litb поместил свой ответ в комментарий вместо ответа, поэтому я копирую его здесь, чтобы люди его увидели:

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

Я думаю, что это правильный ответ. Но короткая версия заключается в том, что foldr не является хвостовой рекурсией.

Я пометил этот пост как Вики сообщества, поэтому не получу от него никакой репутации.