sequence causing stack overflow on pretty small lists

Reid Barton rwbarton at
Mon Aug 26 21:33:35 CEST 2013

On Mon, Aug 26, 2013 at 3:05 PM, Bryan O'Sullivan <bos at>wrote:

> On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <mail at> 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.

Reid Barton
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list