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
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.