# [Haskell-cafe] sequence causing stack overflow on pretty small lists

Albert Y. C. Lai trebla at vex.net
Tue Aug 27 06:59:10 CEST 2013

```On 13-08-26 04:46 AM, Niklas Hambüchen wrote:
> Effectively, sequence is a partial function.
>
> (Note: We are not trying to obtain a lazy list of random numbers, use
> any kind of streaming or the likes. We want the list in memory and use it.)
>
> We noticed that this problem did not happen if sequence were implemented
> with a difference list.
>
> probably trading off a small performance hit, or accept that idiomatic
> Haskell code can crash at any time?

1. Disputed: "sequence overflows stack, for all monads"
(Bonus: a secret of Control.Monad.State revealed)

long :: Monad m => m [Int]
long = sequence (map return [1..1000000])

infinite :: Monad m => m [()]
infinite = sequence (repeat (return ()))

-- these take constant time
one_a = take 1 (runST long)
one_b = take 1 (evalState long ())
unit_a = take 1 (runST infinite)
unit_b = take 1 (evalState infinite ())

sequence is exactly right for Control.Monad.ST.Lazy and
Control.Monad.State. If you fix sequence, you will cause idiomatic use
of sequence and Control.Monad.State to use too much time (up to
infinite) and too much memory (up to infinite).

see my
http://lpaste.net/41790
http://lpaste.net/63925

As you said, we can combine right recursion (foldM) and difference list
(aka Hughes list). I will dispute its questionable benefit in the next
section, but here it is first.

sequence_hughes ms = do
h <- go id ms
return (h [])
where
go h [] = return h
go h (m:ms) = do
x <- m
go (h . (x :)) ms

equivalently,

sequence_hughes ms = do
h <- foldM op id ms
return (h [])
where
op h m = do
x <- m
return (h . (x :))

However, as I said, sequence_hughes is totally wrong for
dispute of the questionable benefit.

3. Disputed: "stack is limited, heap is unlimited"

sequence_hughes consumes linear heap space in place of linear stack
space. That's all it does. There is no free lunch.

Empirically: on linux i386 32-bit GHC 7.6.3 -O2:

xs <- sequence (replicate 2000000 (return 0 :: IO Int))

8MB stack, 16MB heap

xs <- sequence_hughes (replicate 2000000 (return 0 :: IO Int))

24MB heap

What has sequence_hughes saved?

Since a couple of years ago, GHC RTS has switched to growable stack,
exactly like growable heap. It starts small, then grows and shrinks as
needed. It does not need a cap. The only reason it is still capped is
the petty:

"to stop the program eating up all the available memory in the machine
if it gets into an infinite loop" (GHC User's Guide)

Asymmetrically, the heap is not capped by default to stop the program
eating up all the available memory.

And the default stack cap 8MB is puny, compared to the hundreds of MB
you will no doubt use in the heap. (Therefore, on 64-bit, you have to
change 2000000 to 1000000 in the above.) (Recall: [Int] of length n
entirely in memory takes at least 12n bytes: 4 for pointer to Int, 4 for
the number itself, 4 for pointer to next, and possibly a few more bytes
I forgot, and possibly a few more bytes if the Int is lazy e.g. randomIO
as Bryan said. That's just on 32-bit. Multiply by 2 on 64-bit.)

The correct fix is to raise the stack cap, not to avoid using the stack.

Indeed, ghci raises the stack cap so high I still haven't fathomed where
it is. This is why you haven't seen a stack overflow in ghci for a long
time. See, ghci agrees: the correct thing to do is to raise the stack cap.

```