[Haskell-cafe] Why the stack overflow?

[Daniel Fischer]

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.

But better don't use randomRIO, make it a pure function with the PRNG as an argument.

>
> greetings
> Gerben