C stack overflow on Project Euler 27

Question

I just have started to learn Haskell and combine reading books and tutorials with solving problems from Project Euler. I have stuck on Problem 27 because I get "C stack overflow" error using this code:

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

command window

this command gives Euler's coefficients 1 and 41 (40 primes in row)

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

this one fails with "C stack overflow" (I wanted to obtain coefficients -79 and 1601 also mentioned in the problem definition):

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

Would you tell me, please, why does the error arise and how to resolve it? Thank you!

I use WinHugs.

Answer 1

A "stack overflow" error means that the chain of function calls in your program (from the entry function down to the currently executing function) has grown too large. Most compilers and runtimes implement the call chain as a stack data structure—each element is a "stack frame" containing the local variables and context of a single function call—with a limited size.

Usually, a stack overflow means there's something wrong with a recursive function. For example, if a recursion never terminates, it will eventually hit the stack limit and "overflow." Even if a recursion is terminating, it may overflow if there are simply too many calls. This is often the case with very large lists, and seems to be the case with your example.

One way to avoid stack overflows in Haskell (and many other languages) is to write tail-recursive functions. A tail-recursive function is one where the only recursive call is the result of the function. For example,

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

In contrast, foldr is not tail recursive

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

For technical reasons, a tail recursive call can re-use the stack frame of its caller, and thus does not cause the call stack to grow.

(A side note: foldr is not tail recursive but is "lazier" than foldl, because it may not need to evaluate the whole list. This may guide your decision on which to use.)

Even with a tail-recursive function, you may run out of memory due to a "space leak". For example, in foldl each recursive call will build a new suspension for (f x y). foldl uses constant stack space, but O(n) space for unevaluated calls to f. To avoid this in cases where strictness is desirable, you can use foldl'

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

where the infix operator $! forces strict evaluation.