[Haskell-cafe] Why doesn't laziness save the day here?

Dale Jordan dalej at alum.mit.edu
Mon Jan 4 20:31:20 EST 2010

Kind and Generous Haskellers:

I am ensnared in a briar patch of infinite lists and Random gnerators
trying to use laziness to advantage.  Here's my code:

----------------- 8< --------------------
import Control.Applicative
import Control.Monad
import Control.Monad.Random
import Control.Monad.State
import System.Random.Mersenne.Pure64

-- Specialized iterator for running actions in Rand monad, to thread
-- the generator.  The idea is that the action returns a finite list
-- of random values and iterateR lazily creates an infinite list of
-- values.

iterateR act = do
   gen <- get
   let (as,gen') = runRand act gen
   put $! gen'
   (as ++) <$> iterateR act

-- A simple example of a finite action
something :: (RandomGen g) => Int -> Int -> Rand g [Int]
something n m = sequence . replicate n $ getRandomR (m,m+9)

run1 = evalState (take 10 <$> (iterateR (something 2 0))) $ pureMT 42

run2 = evalState
          (take 10 <$> (iterateR (something 2 0) >> iterateR (something 
3 10)))
          $ pureMT 42

run3 = evalState
          (take 10 <$> (iterateR (something 2 0) >>= iterateR . 
(something 3 . head)))
          $ pureMT 42
------------------- >8 ----------------------

Evaluating run1 works fine (ghci 10.3):
*Main> run1

Evaluating run2 or run3 loops and quickly exhausts the heap.

(Using Control.Monad.State.Strict causes stack overflow, though)

The motivation for iterateR is to be able to have the ultimate
consumer determine how many random values to force, but still have a
single random generator used throughout the computation.

My intuition tells me that since the infinite list is produced in
finite batches, the generator shouldn't be tangled up in an infinite
list such as produced by MonadRandom's getRandoms, but I only have a
pink belt in Haskell-fu.

Can anyone explain why this is looping or point out a better way to
generate an arbitrary-length random list while still being able to
reuse the generator?  (I'd rather not use split since this generator
doesn't support it and its of dubious soundness.)

Dale Jordan

More information about the Haskell-Cafe mailing list