Topics in Advanced Computing Lesson 14: Randomness

  1. Administrative
  2. Random
  3. Coin type
    1. Attempt 1
    2. Attempt 2
    3. n times
    4. replicateM
  4. Some stateful functions

Administrative

Random

Might need to run stack ghci --package random. Then import System.Random will work.

Coin type

Suppose we wanted to create a Coin type. We might do something like:

data Coin = HEADS | TAILS deriving (Eq, Show)

intToCoin :: Int -> Coin
intToCoin 0 = HEADS
intToCoin _ = TAILS -- not very fair

Goal: use randomness to generate a random sequence of HEADS/TAILS. (We might play around with bias / non-bias.)

Attempt 1

To get a random number generator, we need to import System.Random, and we need to use the mkStdGen function, which creates a random number generator (an object of type StdGen).

Given such an RNG, we can use the randomR function:

randomR :: (Random a, RandomGen g) => (a, a) -> g -> (a, g)

That is, you provide a “range” of values as a tuple and an RNG, and this outputs a tuple (a, g), where a is the randomly generated element nad g is the next RNG!

flipTwice :: (Coin, Coin)
flipTwice =
  let g1 = mkStdGen 1000
      (c1, g2) = randomR (0, 1) g1
      (c2, _) = randomR (0, 1) g2
  in (intToCoin c1, intToCoin c2)

Ideally we’d like to be able to pass a parameter n and flip the coin n times. But this does the trick for now. Notice of course, though, that the randomR function fits exactly the kind of pattern we talked about last time: if we want some kind of “mutability”, instead of mutating an object in-place, we provide a function s -> (a, s), where a is the value and s is the state. This is precisely what the State type is: a State s a is just a function of this type s -> (a, s).

Attempt 2

Now let’s try to just flip a coin once, using an RNG:

flipCoin :: State StdGen Coin
flipCoin = state $ do
  (n, s) <- randomR (0, 1)
  return (intToCoin n, s)

The state function here is the function takes a function that behaves like a state and wraps it in the State monad. It turns out there’s a cleaner way to do this:

flipCoin :: State StdGen Coin
flipCoin = intToCoin <$> state (randomR (0, 1))

What does <$> mean here? Remember <$> is fmap, so this is fmap intToCoin (state (randomR (0, 1))).

instance Functor (State s) where
  fmap f (State g) = State $ \s0 -> 
    let (a, s1) = g s0
    in (f a, s1)

ie, take the function g -> (a, g) and an RNG g, get the number and the next RNG as (a, s1), pass a to the function f, and take that answer, along with the new state s1, and wrap that as the state.

How do we check the value of this? Use evalState flipCoin (mkStdGen 0) (or some other number besides 0).

n times

First let’s try three times:

import Control.Applicative (liftA3)

flipThrice = liftA3 (,,) flipCoin flipCoin flipCoin

Now try evalState flipThrice (mkStdGen 10)

That easy! What about n times? Or infinitely many times? Can we try the repeat function? repeat <$> flipCoin? Will this work? Try:

ghci> r = repeat <$> flipCoin
ghci> take 10 $ evalState r (mkStdGen 10)

What happens? Explanation?

replicateM

We need kind of a feedback mechanism:

This is exactly what the replicateM does.

flipN :: Int -> State StdGen [Coin]
flipN n = replicateM n flipCoin

And to check:

ghci> evalState (flipN 10) (mkStdGen 10)

Some stateful functions