On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen wrote:

This is because sequence is implemented as

sequence (m:ms) = do x <- m xs <- sequence ms return (x:xs)

and uses stack space when used on some [IO a].

This problem is not due to sequence, which doesn't need to add any strictness here. It occurs because the functions in System.Random are excessively lazy. In particular, randomIO returns an unevaluated thunk.

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.

What do you think about this? Should we "fix" functions like this, 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 demo of Control.Monad.ST.Lazy) (Bonus: a secret of Control.Monad.State revealed) import Control.Monad.ST.Lazy(runST) import Control.Monad.State(evalState) 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). Note: Control.Monad.State = Control.Monad.State.Lazy For more demos of Control.Monad.ST.Lazy and Control.Monad.State(.Lazy), see my http://lpaste.net/41790 http://lpaste.net/63925 2. What to do for IO, Control.Monad.ST, Control.Monad.State.Strict, etc 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 Control.Monad.State and Control.Monad.ST.Lazy. And this is not even my 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)) print (head xs) 8MB stack, 16MB heap xs <- sequence_hughes (replicate 2000000 (return 0 :: IO Int)) print (head xs) 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.

On Mon, Aug 26, 2013 at 4:46 AM, Niklas Hambüchen wrote:

On #haskell we recently had a discussion about the following:

import System.Random

list <- replicateM 1000000 randomIO :: IO [Int]

I would think that this gives us a list of a million random Ints. In fact, this is what happens in ghci. But with ghc we get:

Stack space overflow: current size 8388608 bytes. Use `+RTS -Ksize -RTS' to increase it.

You can use ContT to force the function to use heap instead of stack space, e.g. runContT (replicateM 1000000 (lift randomIO)) return

As an addendum to the recent discussion, can anyone explain why main crashes quickly with a stack overflow, whereas main' is happy to print "Hi" for ages (eventually crashing due to an out of memory condition)? bignum = 100 * 1000 * 1000 main = replicateM bignum (return ()) main' = replicateM bignum (putStrLn "Hi") Tom