[Haskell-beginners] Stack space overflow with foldl'
Ryan Prichard
ryan.prichard at gmail.com
Fri Sep 10 05:29:56 EDT 2010
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
More information about the Beginners
mailing list