Haskell foldl and stack overflow?

Question

I read a posting claims foldl may occur stack overflow easily. And the posting sample code was:

maximum [1..1000000]

The code doesn't overflown in my machine. However it can vary by environment. I increased number like this:

maximum [1..1000000000]

it caused hard disk swapping, so I have to stop evaluation. Sample code is not important. Is it really occur stack overflow? Or just an old days story?

http://www.haskell.org/haskellwiki/Foldr_Foldl_Foldl%27 – Jonno_FTW Feb 12 '11 at 15:40 — Jonno_FTW, Feb 12 '11 at 15:40

score 10 · Accepted Answer · answered Feb 12 '11 at 10:19

10

Some points

Recursive function take stack space in each call, so deeply nested calls will cause overflows
Tail-recursive function can be optimized to iterations and therefore don't overflow
foldr is not tail-recursive
Lazy evaluation can prevent tail-recursive functions from being optimized
foldl is tail-recursive and lazy, so it can overflow
foldl' is tail-recursive and strict, so it's safe

answered Feb 12 '11 at 10:19

Dario

47,396
7
93
126

3

But the bonus with foldr is it can produce partial results as it operates on infinite lists. – Dan Burton Feb 12 '11 at 17:05

score 3 · Answer 2 · answered Feb 13 '11 at 23:43

Data.List.maximum is implemented using the lazy foldl1. There is a rule to use strictMaximum (implemented using the strict foldl1') if the list contains Int or Integer.

So, the following program compiled with optimisations does not cause a stack overflow:

main = print $ maximum [1..1000000000 ]

Haskell foldl and stack overflow?

2 Answers2

Some points

Linked