Do stack overflow errors occur in Haskell?

Question

As a pure functional programming language, Haskell intensively uses recursion. Do stack overflow errors occur in Haskell, like in Java? Why, or why not?

Answer 1

Haskell uses the stack differently from Java, due to laziness.

In Java, a stack frame is created when a method is called, and freed when the method returns. So if f() is a recursive method, each recursive call to f() generates a stack frame, and these frames are strictly nested. You can get a stack overflow when you have a deep chain of recursive calls, like f() -> f() -> f() -> ….

Whereas in Haskell, a thunk is created when a function is called. A stack frame is created when a thunk is forced using pattern-matching (e.g. case), and freed when evaluation of the thunk is complete enough to return a value (which may contain more unevaluated thunks).

So if f is a recursive function, each call to f generates a thunk, and case on the result of this generates a stack frame, but these frames are only nested when there’s a dependency between thunks. And in fact, that’s what the seq primitive does: a `seq` b means “evaluate a before b, returning b”, but you can also think of it as adding a dependency of b on a, so when b is evaluated, a is also forced.

You can get a stack overflow when you have a deep chain of thunks to evaluate, for example in the excessively lazy foldl function:

foldl (+) 0 [1..5]
==
foldl (+) 0 (1 : 2 : 3 : 4 : 5 : [])
==
((((0 + 1) + 2) + 3) + 4) + 5

This generates a chain of thunks like so:

((+)
    ((+)
        ((+)
            ((+)
                ((+)
                    0
                    1)
                2)
            3)
        4)
    5)

When we force the result (for example, by printing it) we need to descend all the way down this chain in order to be able to start evaluating it, at the (+) 0 1 thunk.

So foldl often produces stack overflows for large inputs, which is why most of the time you should use foldl' (which is strict) when you want a left-associative fold. Instead of building a chain of nested thunks, foldl' evaluates the intermediate results immediately (0+1 = 1, 1+2 = 3, 3+3 = 6, …).