<div dir="ltr">On Mon, Aug 26, 2013 at 3:05 PM, Bryan O'Sullivan <span dir="ltr"><<a href="mailto:bos@serpentine.com" target="_blank">bos@serpentine.com</a>></span> wrote:<br><div class="gmail_extra"><div class="gmail_quote">
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="im">On Mon, Aug 26, 2013 at 1:46 AM, Niklas Hambüchen <span dir="ltr"><<a href="mailto:mail@nh2.me" target="_blank">mail@nh2.me</a>></span> wrote:<br>
<div class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div style="overflow:hidden">This is because sequence is implemented as<br>
<br>
sequence (m:ms) = do x <- m<br>
xs <- sequence ms<br>
return (x:xs)<br>
<br>
and uses stack space when used on some [IO a].<br></div></blockquote></div><br></div>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.</div>
</div></blockquote><div><br></div><div style>It doesn't have to do with System.Random.</div><div style><br></div><div style><div>import Control.Monad</div><div><br></div><div>{-# NOINLINE a #-}</div><div>a :: IO Int</div>
<div>a = return 1</div><div><br></div><div>main = do</div><div> list <- replicateM 1000000 a :: IO [Int]</div><div> return ()</div><div><br></div><div style>will produce a stack overflow, regardless of optimization level.</div>
<div style><br></div><div style>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.</div><div style>
<br></div><div style>Regards,</div><div style>Reid Barton</div></div></div></div></div>