Search code examples
haskellrecursionstack-overflowfold

Why does foldr applied to a function strict in both arguments not cause a stack overflow?

I wonder why this expression doesn't cause a stack overflow in GHCi:

foldr (+) 0 [1..5000000] -- 12500002500000

Obviously, (+) is strict in both its arguments so the whole list has to be traversed immediately and lazyness doesn't help.

My first thought was that the compiler would recognize (+) as an associative operation and transforms it into tail recursion.

However, the following operation does work as well:

foldr (-) 0 [1..5000000] -- -2500000

What is happening here?

Solution

  • GHC's latest runtime system lets its stack grow dynamically. Try limiting it, and you'll see your stack overflow:

    % ghci +RTS -K512K
GHCi, version 8.2.2: http://www.haskell.org/ghc/  :? for help
Prelude> foldr (+) 0 [1..5000000]
*** Exception: stack overflow