Haskell Random Generation

Question

Could someone describe how the following type constructor and functions work?

type Rand a = State StdGen a  

getRandom :: (Random a) => Rand a
getRandom = get >>= (\r -> let (a,g) = random r in (put g) >> (return a))

runRand :: Int -> Rand a -> a
runRand n r = evalState r $ mkStdGen n

runRandIO :: Rand a -> IO a
runRandIO r = randomIO >>= (\rnd -> return $ runRand rnd r)

getRandoms :: (Random a) => Int -> Rand [a]
getRandoms n = mapM (\_ -> getRandom) [1..n]

Answer 1

Let's start at the beginning:

type Rand a = State StdGen a

This line tells you that Rand a is a type synonym for a State type, whose state is given by StdGen and whose eventual value is of type a. This will be used to store the state of the random number generator between each request for a random number.

The code for getRandom can be converted into do notation:

getRandom :: (Random a) => Rand a
getRandom = do
  r <- get                   -- get the current state of the generator
  let (a,g) = random r in do -- call the function random :: StdGen -> (a, StdGen)
    put g                    -- store the new state of the generator
    return a                 -- return the random number that was generated

The runRand function takes an initial seed n and a value r of type Rand a (which, remember, is just a synonym for State StdGen a). It creates a new generator with mkStdGen n and feeds it to evalState r. The function evalState just evaluates the return value of a State s a type, ignoring the state.

Again, we can convert runRandIO into do notation:

runRandIO :: Rand a -> IO a
runRandIO r = do
  rnd <- randomIO        -- generate a new random number using randomIO
  return (runRand rnd r) -- use that number as the initial seed for runRand

Finally, getRandoms takes a number n representing the number of random values that you want to generate. It builds a list [1..n] and applies getRandom to the list. Note that the actual values in [1..n] aren't used (you can tell because the lambda function starts with \_ -> ...). The list is just there to have something with the correct number of elements. Since getRandom returns a monadic value, we use mapM to map over the list, which causes the state (i.e. StdGen) to be threaded correctly through each of the calls to getRandom.

Answer 2

The basic idea is simple--to create pseudorandom numbers, you need to maintain some state between function calls. So the type Rand a is defined to mean "a along with the state needed for randomness".

The state is stored using the State monad. This provides two main actions--get and put, which do exactly what they sound like. So getRandom just looks up the current state and then calls the random function. This function returns two values: the random value and the new state. Then you just put the new state and wrap the resulting value.

runRand lets you unwrap a "random" value given a seed. evalState lets you execute a stateful computation (that is, a value of type State s a or, in this case, Rand a) given an initial state and then just discards the final state, only giving you the result. So this lets you run a Rand a with a given seed and only returns the resulting value. The value can just have type a, rather than Rand a because it will always give you the same result for the same seed.

runRandomIO just does the same thing except gets the seed based off some global state in IO.

getRandoms just gets you a list of Rand a values by calling getRandom for every element of the [1..n] list (ignoring the actual number).