Re: sequence causing stack overflow on pretty small lists

26 Aug 2013

      On Mon, Aug 26, 2013 at 3:05 PM, Bryan O'Sullivan wrote:
...
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.
It doesn't have to do with System.Random.

import Control.Monad

{-# NOINLINE a #-}
a :: IO Int
a = return 1

main = do
  list <- replicateM 1000000 a :: IO [Int]
  return ()

will produce a stack overflow, regardless of optimization level.

sequence tends to be tail-recursive for monads like Reader and (lazy)
State, but not for monads like Maybe or IO where (>>=) must pattern-match
on its first argument.

Regards,
Reid Barton