On Sat, Sep 19, 2009 at 6:54 AM, Daniel Fischer <[email protected]> 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) _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
