[Haskell-beginners] Stack space overflow with foldl'

[Ryan Prichard]

Hi,

I see a stack overflow with this code, but I don't understand why.

Test.hs
--------------

main :: IO ()
main = do
  let list = ([1..3*1000*1000] :: [Int])
  let !x = foldl'2 (flip seq) () list
  return x

-- foldl'2 is just the __GLASGOW_HASKELL__ version of Data.List.foldl'.
-- http://www.haskell.org/ghc/docs/6.12.2/html/libraries/base-4.2.0.1/
-- src/Data-List.html
-- The test case behaves the same if I call foldl' instead of foldl'2.
foldl'2 :: (a -> b -> a) -> a -> [b] -> a
foldl'2 f z0 xs0 = lgo z0 xs0
    where lgo z []     = z
          lgo z (x:xs) = let z' = f z x in z' `seq` (lgo z' xs)

$ ghc Test.hs -o Test
$ time ./Test

real	0m0.087s
user	0m0.084s
sys	0m0.000s

$ ghc Test.hs -o Test -O
$ time ./Test
Stack space overflow: current size 8388608 bytes.
Use `+RTS -Ksize -RTS' to increase it.

real	0m1.780s
user	0m1.764s
sys	0m0.004s

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 6.12.3

I looked at the Core output with ghc-core, with or without
optimizations, and I see a $wlgo recursive function that doesn't appear
to end in a tail call.  I don't see any let expressions in the
folding code, so I assume no thunks are being created.  I can make a
tail call appear by doing either of two things:

1. Replace "lgo z []" with "lgo !z []".  This suggestion came from an
email on haskell-beginners that I can't find right now.  It was a few
months ago.

2. Instead of using the __GLASGOW_HASKELL__ version of foldl', use the
other version:

foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x in a' `seq` foldl' f a' xs

My test case is contrived.  Originally, I had a program that read
lines from a file as Data.ByteString values, and I was trying to debug
a stack overflow.  I added the foldl' call to force the evaluation of
the ByteString lines, but the foldl' call itself overflowed the
stack.

I might have fixed my original stack overflow problem.  I was applying
sum to a large list of integers, and sum is lazy.  I don't think I have
any real code anymore that overflows the stack, but I'm uncomfortable
because I don't know why my test case doesn't work.

Is the foldl' call in my test case allowed to have linear stack usage?

Thanks,
-Ryan