Lab 5: Using Randomness

Posted on November 11, 2019

Randomness

A common requirement for computer programs is that there should be some randomness in the behaviour of the program. For this you need a random number generator, which can generate an unlimited sequence of random numbers. Typically these numbers are not truly random, but pseudo-random.

A pseudo-random number generator generates a sequence of numbers based on an initial state \(s\) using a function \(f\). The states are \(s_1 = f(s)\), \(s_2 = f(f(s))\), \(s_3 = f(f(f(s)))\), etc. Each random number is then derived from each of these intermediate states (typically by taking a small proportion of the 0’s and 1’s from the state).

The \(f\) function has to be chosen so that subsequent states have no obvious correlation, so for most intents and purposes the numbers generated are random, but the sequence of numbers is in fact entirely determined by the initial state \(s\).

In many programming languages, the random number generator state is hidden from the programmer, but because of the purity of Haskell, the random number generator state must explicitly be passed through your program.

The following ghci session shows how the function random from the System.Random module can be used.

If you only installed Haskell Core Platform, you will need to download the module:

$ cabal install random

Pop into GHCi.

$ ghci
Prelude> import System.Random
Prelude System.Random> :t random
random :: (Random a, RandomGen g) => g -> (a, g)
Prelude System.Random> g <- newStdGen -- create new random number generator
Prelude System.Random> let (x, g') = random g :: (Int, StdGen)

We had to specify the type above so random knows what type to generate.

Prelude System.Random> x
-4940845671478547204
Prelude System.Random> let (x, _) = random g :: (Int, StdGen)
Prelude System.Random> x
-4940845671478547204

Oops, reusing g gives us the same number again!

Prelude System.Random> let (x, g'') = random g' :: (Int, StdGen)
Prelude System.Random> x
-7259815437984538120

Much better! Using g' gives us the next number.

The State Monad Overview

The State Monad is a fairly general monad that lets you maintain state between functions without having to explicitly pass the state from one function to the next.

This is particularly useful when using random numbers in many parts of a Haskell program, as otherwise we would have to explicitly pass the random number generator in and out of every function that needed it.

There is a standard implementation of the State monad in a package called Control.Monad.State. However, for this lab you will be implementing your own version of the State monad (RandState) specialized to pseudo-random number generators.

An instance of the RandState monad is a function of type StdGen -> (a, StdGen), where a is the “real” return type of the function and the generator portion is implicitly passed between functions unless explicitly modified. Like in the general state monad, the functions get and put play a special role, as they allow you to fetch and update the generator.

Note. Recall that the lecture notes call the State monad the “elephant in the room” monad: useful for when something is so pervasive that it’s cleaner to hide it away. So despite their importance, your code in today’s lab will actually only use get and put in a few places (in only one place, in fact). Most of your code will rely on the bind (>>=) function to hide the transmission of state between the parts of your program.

Lab Tasks

Pull your repository (git pull). There are several files. You will need to modify Lab5.hs and RandState.hs.

First you will need to fill in the undefineds in RandState.hs which implement the Monad typeclass for RandState. It is no secret that you can essentially copy and paste definitions from the lecture notes, but it is useful to actually type out these definitions for yourself. When you fill these in, think about how they are interpreted for our setting.

Familiarize yourself with the definition of the function rand in RandState.hs. The function rand generates numbers in a huge range (what is it?).

Once you have filed in the definitions in RandState.hs, you can test this function from ghci by creating a new random number generator, and then using the runRandom function, e.g.,

[~/labRand]$ ghci RandState.hs State.hs
Ok, modules loaded: RandState, State.
*RandState> gen <- newStdGen -- Create new random number generator
*RandState> runRandom rand gen :: Int
1256390094846286344
*RandState> gen <- newStdGen
*RandState> runRandom rand gen :: Double
0.5556050250436191

See RandState.hs to see how runRandom is implemented.

In Lab5.hs implement a new function randR :: Random a => (a, a) -> RandState a that is like rand, but generates numbers in a specified range. Use the function randomR :: RandomGen g => (a, a) -> g -> (a, g) in System.Random. You can copy and paste the body of rand from RandState.hs as a starting point.

Note. This randR function you write is the only place in the lab where you will use get and put!

Roll Two Dice

Now, using randR, implement a function rollTwoDice which generates a random sum of two dice (so between 2 and 12, but be sure to roll the virtual dice separately to get the right distribution such that 7 is the most common number). Choose the appropriate type signature. (Hint: this function takes no arguments—why?)

If you are having trouble, see the Where is the Generator? tutorial below.

Testing your function in GHCi is a little awkward, because the GHCi prompt operates in the IO monad, not the State monad. You can try the incantation below:

newStdGen >>= (\gen -> return (runRandom rollTwoDice gen))

…which creates a new random number generator gen, runs the rollTwoDice computation with that generator as the initial state, and then wraps the Int result in the IO monad with return, whereby GHC displays the integer.

Although this incantation is fine for testing in GHCi, your final solution must not use newStdGen other than at the one place already provided in the starter code.

Shuffling Cards

In this section we will write code to randomly shuffle a standard deck of cards. You should see this in your starter file:

-- Data types to represent playing cards
data CardValue
    = King
    | Queen
    | Jack
    | NumberCard Int  -- From 1 to 10
    deriving (Show, Eq)

data CardSuit
    = Hearts
    | Diamonds
    | Spades
    | Clubs
    deriving (Show, Eq)

data PlayingCard =
    PlayingCard CardValue CardSuit
    deriving (Eq)

type Deck = [PlayingCard]

-- fullCardDeck is a deck of cards, 52 in total, with a King, a Queen,
-- a Jack and NumberCards from 1 to 10 for each suit.
fullCardDeck :: Deck
fullCardDeck =
    [ PlayingCard v s | v <- allVals, s <- allSuits ]
    where
        allVals  = King : Queen : Jack : [ NumberCard i | i <- [1..10] ]
        allSuits = [Hearts, Diamonds, Spades, Clubs]

Implement a function removeCard, which will be monadic. Given a list of PlayingCards, it should pick a random card out of the list, return the card and the list with the card removed (as a tuple potentially). This is a basic function that can help you shuffle a deck. A common interview question is to implement deck shuffling. A deck shuffling function should induce a uniform probability distribution over all permutations: i.e. all orderings of the cards should be equally likely. You will want to write this recursively, handling the base case for an empty deck, and then using an inductive step: using removeCard and then recursing.

Implement a function shuffleDeck which takes a list of playing cards, [PlayingCard]. Test that it returns random permutations. To write this, start by considering the case with one card. Then consider the case with two cards. Then consider the case with three cards. Try to see if you can implement the three card case by using the two card function. Test the uniformity of shuffles by looking at small decks and checking statistics.

Implement a function shuffleADeck which generates and outputs a shuffled full deck of 52 cards. Test that it outputs that many cards.

Putting it together

At the bottom of the starter code you will see a block of commented out code. Uncomment the code and then implement shuffleNTimes and rollTwoDiceNTimes so that your final program can be run from the command line like this:

$ ./Lab5 shuffle 3
[6♠,4♠,7♠,5♣,2♣,K♣,K♦,K♠,Q♥,9♥,5♥,9♣,7♣,4♦,8♣,4♣,6♦,5♠,5♦,10♠,10♦,8♦,10♣,7♥,1♦,J♥,6♣,2♥,J♦,7♦,Q♦,8♠,9♠,3♣,1♥,J♣,9♦,3♥,4♥,2♦,Q♠,1♠,K♥,2♠,Q♣,J♠,3♠,8♥,1♣,10♥,3♦,6♥]
[J♣,1♠,3♦,3♠,6♣,5♣,6♥,1♣,K♥,9♦,J♦,10♦,6♠,J♠,5♦,8♠,J♥,7♠,3♥,9♠,2♥,4♦,8♣,4♠,K♣,1♦,K♠,Q♦,2♠,4♥,10♥,10♠,6♦,9♣,10♣,3♣,Q♠,2♣,7♦,5♠,K♦,7♥,Q♣,1♥,7♣,4♣,9♥,8♦,8♥,5♥,Q♥,2♦]
[Q♦,3♣,2♥,9♠,Q♣,5♦,7♦,5♠,6♠,2♣,5♥,9♥,6♦,6♣,1♠,6♥,10♦,1♦,3♦,2♠,5♣,7♣,3♠,9♣,1♣,4♠,Q♥,8♦,Q♠,7♠,10♠,8♠,4♦,J♥,K♥,8♣,4♣,J♦,J♠,K♠,2♦,9♦,K♦,7♥,10♣,K♣,8♥,1♥,J♣,10♥,3♥,4♥]

$ ./Lab5 rollTwoDice 5
6
6
4
8
7

Make sure your lab behaves this way—it is what you will be graded on. Make sure each deck shuffle list appears on its own line exactly as the above.

Note that each iteration above should start with the random number generator produced from the last iteration. For deck shuffling, each iteration should shuffle an ordered deck (not the deck from the previous iteration).

Constraints on Your Submission

The goal of the lab is to use the RandState monad to “automatically” thread the random number generators through your code. So, pretty much every function that uses random numbers should be part of the RandState monad (i.e. the function returns some kind of RandState). In the State monad, the bind (>>=) function will handling transmitting the state behind the scenes.

To figure out if a function needs to be in the RandState monad, ask yourself, “If I call this function twice in sequence, do I want different results the second time?” If yes, the function needs to be monadic so the generator is properly transmitted from one call to the next.

Also, the function itself should be used in a monadic context so calls to it are properly glued together with bind (>>=).

Thus, most of your code should be in the RandState monad. And it should rely on the monad so you do as little explicit management of the state as possible.

Therefore:

  1. Your lab should only call newStdGen once. (And it’s already in the starter code.)

  2. Your code should only use get and put once each.

  3. Your code should only call runRandState (or runRandom*) twice: once in shuffleNTimes and once in rollTwoDiceNTimes (or once in a helper of each function). These functions are the interface between the IO monad and the RandState monad. Look at the provided RandStateExamples.hs file for a good example of using this interface.

If you find yourself using runRandState or runRandom in every function, or are unpacking the generator in every random function, you are defeating the purpose of the State monad and will lose points. Handling the transmission of state is bind’s job. See the tutorial in the next section.

Hint: in the shuffleNTimes and rollTwoDiceNTimes functions you will probably want runRandState because runRandom discards thethe generator, but you will want both the result and the new generator.

Where is the Generator?

What is the type of the provided rand function?

rand = do
    gen <- get
    let (x, gen') = random gen
    put gen'
    return x

Well, we need to somehow get an initial generator into this function, so maybe one of the parameters is a generator.

But as written, this function has no named arguments. And, if you look at the provided code, the type annotation is essentially:

rand :: RandState Int

This function only returns something? How does a generator get into this function? Why isn’t a generator one of the arguments? What’s going on?

The answer has to do with how Haskell represents state.

You might think that, to represent state, Haskell might have some datatype with some fields that could be modified as the program executed. However, Haskell adheres to the discipline of purity: nothing can change once declared.

Haskell takes a stranger route:

newtype State s a = State {
    runState :: s -> (a,s)
}

Which is essentially:

newtype State s a = State (s -> (a,s))

So State is just a wrapper for an s -> (a,s) function—a function that takes an initial state and returns a value and a new state.

Haskell doesn’t really represent state at all—it represents transformations on state.

Back to our rand function, we said its type signature was essentially

rand :: RandState Int

From RandState.hs we see RandState is the same as state specialized so that the hidden state type is StdGen. So the rand function will return some value that looks like:

RandState (\gen -> ...some code that returns (int, gen') )

Aha, there’s the missing generator! That’s why the generator is not an argument to the function: the rand function isn’t actually doing any computation, it’s just building a state transforming function. rand returns a wrapped function that is waiting for an initial generator.

So how does all this:

rand :: RandState Int
rand = do
    gen <- get
    let (x, gen') = random gen
    put gen'
    return x

return a wrapped s -> (a,s) function?

Remember, do notation is de-sugared to calls to bind (>>=). All monad magic is in bind. You should convince yourself that the State monad’s bind definition is “secretly” handling the state for you, setting up a function that sequences the actions:

ma >>= f = State $ \s ->
    let (a,t) = runState ma s
        mb = f a
        (b,u) = runState mb t
    in (b,u)

and you should notice that, indeed, it returns a value of the form State (s -> (a, s)).

So bind composes our State (s -> (a,s)) actions into more complicated State (s -> (a, s)) actions. The basic returned function is always s -> (a,s), a function waiting for that initial state before it will actually do all the computation.

So how might be use all this? How would we write, say, a function that returns two random numbers in a tuple?

randTwo = ...

The first question is: what is the type signature?

If we write the function in sequence, should it return different values? It’s a random number function, so, yes, it should. This means it needs different generators each time which means it should be monadic. We’ll let the RandState monad hide the transmission of the generators.

randTwo :: ... -> RandState (...)
randTwo = ...

What should be the return value in the monad? Well, just pair of numbers.

randTwo :: ... -> RandState (Int, Int)
randTwo = ...

Do we need to pass any arguments to randTwo? Well, the initial generator maybe, but wait…no. We’re returning RandState (Int, Int) which represents values that look like
RandState (\gen -> ...some code that returns ((Int, Int), gen)).

Our randTwo will return a wrapped function that’s waiting for a generator. We don’t need an explicit generator in our type declaration—it’s part of RandState. We’re just building up a computation to be performed later.

randTwo :: RandState (Int, Int)
randTwo = ...

Okay, what’s next? Well, we’re in the RandState monad because we want our state transformations to “automatically” be composed properly by bind. So this function should be monadic, let’s start by writing do.

randTwo :: RandState (Int, Int)
randTwo = do
    ...

Now let’s get our random numbers.

randTwo :: RandState (Int, Int)
randTwo = do
    let r1 = rand
    let r2 = rand

Hmm. This seems not to work. We want an Int each time but randR is a RandState Int. Maybe we need to use runRandom to actually execute rand’s state transformer.

randTwo :: RandState (Int, Int)
randTwo = do
    let r1 = runRandom rand gen
    let r2 = runRandom rand gen

Oh, now we need a generator. Maybe we can use newStdGen, wait, no, that’s an IO monadic function and we’re in a different kind of monad. Oh, maybe we can pull the generator out of the state!

randTwo :: RandState (Int, Int)
randTwo = do
    gen <- get
    let r1 = runRandom rand gen
    let r2 = runRandom rand gen

Oh shoot. It’s using the same generator both times—we’re going to get the same numbers for r1 and r2…hmmm….

STOP STOP STOP!

Too much work. We’re doing bind’s job. The whole point of the monad was so that bind could take care of sequencing the generators for us. Make the code fully monadic. Let the do notation glue together our actions with bind.

randTwo :: RandState (Int, Int)
randTwo = do
    r1 <- rand
    r2 <- rand

Now, behind the scenes, bind will take care of grabbing the returned generator from the first call and it using as the initial generator for the second call. A good exercise is to de-sugar the do notation here to bind calls and think about how the bind function above does what we want it to.

Last thing we must do is return the pair of random numbers.

randTwo :: RandState (Int, Int)
randTwo = do
    r1 <- rand
    r2 <- rand
    (r1, r2)

Whoops, this doesn’t typecheck. We’re returning (Int, Int) but we need to return RandState (Int, Int). How do we wrap a vanilla value in a monad? The return function:

randTwo :: RandState (Int, Int)
randTwo = do
    r1 <- rand
    r2 <- rand
    return (r1, r2)

There we go.

Most of your code should be similarly simple. You should only explicitly handle generators in randR, shuffleNTimes, and rollTwoDiceNTimes.

To Hand In

Your lab5/ directory should have Lab5.hs and RandState.hs. You may delete RandStateExamples.hs.

You do not need to write tests for this week’s lab.

Grading Breakdown

Extra Credit: Approximating Pi (8%)

We will shift gears a bit in this final part of the lab to show another application of randomness. Randomness can be a powerful tool if we want to work out approximate solutions to problems. There is a general class of computational methods called Monte-Carlo methods that are widely used.

One simple example of a problem that can be solved with a Monte-Carlo method is calculating the approximate value of π.

Consider a circle inscribed in a square. If the circle has radius \(r = 1\), then the side length \(l\) of the square is two, and the the ratio of the area of the circle to area of the square is \(\frac{\pi r^2}{l^2} = \frac{\pi 1^2}{2^2} = \frac{\pi}{4}\). If we then choose points at random in the square (i.e. with x and y values in the interval \([-1, 1]\)), then we can approximate π by checking which proportion fall within the circle. The more points are randomly chosen, the closer the ratio will converge to π/4. You can easily check to see if the point is within the circle—less than 1 unit away from (0,0).

Here is a template for the pi approximation code:

-- Succeed if randomly chosen point from square is inside circumscribed circle
piTrial :: RandState Bool

-- Perform n trials of the RandState function provided as the second argument,
--  and give back the number of successful trials
-- Hint: To perform the n trials, you can either use sequence from
--       Control.Monad, or you can use recursion
bernoulliTrials :: Int -> RandState Bool -> RandState Int

-- Approximate pi using n randomly chosen points
-- Hint: You will probably need to use the fromIntegral function to
--       convert Int into Double.
approxPi :: Int -> RandState Double

Make a new file ApproxPi.hs that runs on the command line, taking the number of iterations as an argument, and outputs an approximation of π.

$ ./ApproxPi 10000
3.1588