Haskell foldl and stack overflow?

问题:

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?

回答1:

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

回答2:

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 ]