I’m working on solutions to the latest Programming Praxis puzzles—the first on implementing the minimal standard random number generator and the second on implementing a shuffle box to go with either that one or a different pseudorandom number generator. Implementing the math is pretty straightforward. The tricky bit for me is figuring out how to put the pieces together properly.

Conceptually, a pseudorandom number generator is a function `stepRandom :: s -> (s, a)`

where `s`

is the type of the internal state of the generator and `a`

is the type of randomly chosen object produced. For a linear congruential PRNG, we could have `s = a = Int64`

, for example, or perhaps `s = Int64`

and `a = Double`

. This post on PSE does a pretty good job of showing how to use a monad to thread the PRNG state through a random computation, and finish things off with `runRandom`

to run a computation with a certain initial state (seed).

Conceptually, a shuffle box is a function `shuffle :: box -> a -> (box, a)`

along with a function to initialize a new box of the desired size with values from a PRNG. In practice, however, the representation of this box is a bit trickier. For efficiency, it should be represented as a mutable array, which forces it into `ST`

or `IO`

. Something vaguely like this:

mkShuffle :: (Integral i, Ix i, MArray a e m) => i -> m e -> m (a i e) mkShuffle size getRandom = do thelist <- replicateM (fromInteger.fromIntegral $ size) getRandom newListArray (0,size-1) thelist shuffle :: (Integral b, Ix b, MArray a b m) => a b b -> b -> m b shuffle box n = do (start,end) <- getBounds box let index = start + n `quot` (end-start+1) value <- readArray box index writeArray box index n return value

What I really want to do, however, is *attach* an (initialized?) shuffle box to a PRNG, so as to “pipe” the output from the PRNG into the shuffle box. I don’t understand how to set up that plumbing properly.

## Leave a Reply