CODEWITHSUNDEEP
haskellrecursionstack-overflowfold
user6445533
user6445533

Reputation:

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?

Upvotes: 2

Views: 129

Answers (1)

Daniel Wagner
Daniel Wagner

Reputation: 153172

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

Upvotes: 4

Related Questions