On Sat, Sep 19, 2009 at 6:54 AM, Daniel Fischer 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)