[Haskell-cafe] Why the stack overflow?

[Derek Elkins]

On Sat, Sep 19, 2009 at 6:54 AM, Daniel Fischer
<daniel.is.fischer at web.de> wrote:
> Am Samstag 19 September 2009 12:37:41 schrieb staafmeister:
>> Hi haskell-cafe,
>>
>> Why does rlist 100000 [] gives stack overflow in ghci?
>>
>> rlist 0 l = return l
>> rlist n l = do {x <- randomRIO (1,maxBound::Int); let nl = x:l in nl `seq`
>> rlist (n-1) nl}
>>
>> I first uses replicateM then foldM and finally an explicit function. But
>> they give all stack overflow
>> I don't know why 100000 is not absurd and it is tail recursive. Or is it
>> not, due to the monad structure?
>
> Prelude System.Random> :set -XBangPatterns
> Prelude System.Random> let rlist2 0 l = return l; rlist2 n l = do { !x <- randomRIO
> (1,maxBound :: Int); let {nl = x:l}; nl `seq` rlist2 (n-1) nl }
> Prelude System.Random> rlist2 10 [] >>= \l -> print (take 3 l) >> print (last l)
> [800589677,541186119,1521221143]
> 1279766979
> Prelude System.Random> rlist2 1000 [] >>= \l -> print (take 3 l) >> print (last l)
> [655069099,324945664,2137996923]
> 1108985638
> Prelude System.Random> rlist2 10000 [] >>= \l -> print (take 3 l) >> print (last l)
> [286279491,666663955,2118785404]
> 315689721
> Prelude System.Random> rlist2 100000 [] >>= \l -> print (take 3 l) >> print (last l)
> [862262999,947331403,790576391]
> 1250271938
> Prelude System.Random> rlist2 1000000 [] >>= \l -> print (take 3 l) >> print (last l)
> [681201080,627349875,484483111]
> 1048225698
> Prelude System.Random> rlist2 10000000 [] >>= \l -> print (take 3 l) >> print (last l)
> [1247387053,690485134,1924757191]
> 1637122415
>
> The problem is that randomRIO doesn't evaluate its result, so you build a long chain of
> calls to randomR, which isn't evaluated until the count reaches 0, hence the stack
> overflow. Forcing x prevents the long chain from being built.

Incidentally, nl is already in head normal form so seq nl does
nothing.  Leading to:
rlist 0 l = return l
rlist n l = do !x <- randomRIO (1, maxBound :: Int); rlist (n-1) (x:l)