sequence causing stack overflow on pretty small lists

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


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

> On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <mail at nh2.me> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130826/d5c3d1cb/attachment.htm>


More information about the Libraries mailing list