Assignment 8 specification

Tue Nov 6

We will begin with the definition of pseudo-random numbers from the notes.

The only difference is that we’re going to use an abbreviation for the type of the rand function, by defining this type synonym:

Using Gen can make it clearer when and where this state-passing pattern is being used. The first argument s is the state type, and the second argument a is the result type. Here is the definition of rand using that type. (The code itself is exactly the same as in the notes.)

Coin flips

Now let’s make a simple enumerated type for representing coin flips. A coin flip can be head or tails:

This is ‘isomorphic’ to a Boolean value – we could just represent heads as True and tails as False (or vice-versa), but for clarity it’s sometimes helpful to declare such things as distinct types.

Next, let’s make a function to convert any integer into a coin flip. You want the coin to be fair (or as close as possible), so use even or odd to determine whether you produce Heads or Tails.

Now create a generator for coin flips. You can call rand and/or coinFromInt within your code.

Iterating a generator

In the notes we defined randomList that would generate a list of specified length, containing random values. To do that, it hard-coded a call to rand. Now we’ll implement a variant of that where the generator is specified as an argument. That way it can generate a list of anything for which a generator is provided. Here is the more general type:

So, given a generator (using state s) of values of type a, and an Int for the length of the list, we can provide a generator of lists of values. The implementation looks a lot like the one in the notes – it has a case for zero, a case for n, and then you thread the state around. The only difference is that you’re passing around the generator gen as an argument, and use it instead of rand.

Below are some usages of iterGen. By providing different values, we can generate lists of different things. The state-threading to make use of pseudo-random numbers stays the same.

ghci> iterGen rand 5 (Seed 99)
([1663893,47762240,1728567349,872658027,1597634426],Seed {unSeed = 1597634426})
ghci> iterGen flipCoin 5 (Seed 99)
([Tails,Heads,Tails,Tails,Heads],Seed {unSeed = 1597634426})

You can even pass a partial application of iterGen itself as the generator for another iterGen. This is a list of lists of random numbers — essentially, a 3×5 matrix! (I added spacing to the output, for clarity.)

ghci> iterGen (iterGen rand 3) 5 (Seed 99)
([[   1663893,   47762240, 1728567349],
  [ 872658027, 1597634426, 1453759341],
  [1411792268,  445832573,  537610028],
  [1148037667, 2075984621,  906712338],
  [ 570305654,  907610217,  628572478]],
 Seed {unSeed = 628572478})

Rainbows

Here is an enumerated datatype representing five different colors.

Create a generator for colors, where each color is chosen with roughly equal probability. You may want to use mod and toEnum. And perhaps you want a separate function colorFromInt that is analogous to coinFromInt.

Some sample usage:

ghci> genColor (Seed 99)
(Green,Seed {unSeed = 1663893})
ghci> iterGen genColor 8 (Seed 99)
([Green,Red,Blue,Yellow,Orange,Orange,Green,Green],Seed {unSeed = 445832573})

Huh, it seemed to pick Green a lot. Is this really a fair choice? Let’s generate many colors and count how many greens. It should be roughly one-fifth:

ghci> length $ filter (== Green) $ fst $ iterGen genColor 1000 (Seed 99)
204

So with this initial seed, 204 out of 1000 were green, which pretty close to 20%. We can try that with a few different seeds and see how much variation there is:

ghci> length $ filter (== Green) $ fst $ iterGen genColor 1000 (Seed 99)
204
ghci> length $ filter (== Green) $ fst $ iterGen genColor 1000 (Seed 29487)
208
ghci> length $ filter (== Green) $ fst $ iterGen genColor 1000 (Seed 474732)
193
ghci> length $ filter (== Green) $ fst $ iterGen genColor 1000 (Seed 59873)
222

The most extreme example was 222, but it’s still hovering around 20%.

Gen is a functor

Finally, I mentioned in class that the state-passing Gen type can be a functor. For now, let’s not mess with making it an actual instance of the Functor type class (I’ll explain why later), but we can still implement a function equivalent to fmap:

To further understand this function, it can be helpful to expand the Gen synonym, which would make it:

Here’s a stub for its definition:

Here it is in action, all with the same seed for comparison.

ghci> fmapGen (0-) rand (Seed 99)
(-1663893,Seed {unSeed = 1663893})
ghci> fmapGen show rand (Seed 99)
("1663893",Seed {unSeed = 1663893})
ghci> iterGen (fmapGen show rand) 5 (Seed 99)
(["1663893","47762240","1728567349","872658027","1597634426"],Seed {unSeed = 1597634426})

Or used to define some other generators:

Simulate rolling a 6-sided die a bunch of times:

ghci> iterGen diceRoll 50 (Seed 99)
([4,3,2,4,3,4,3,6,3,2,6,1,3,4,5,6,4,4,6,1,5,3,6,2,2,
  6,1,3,2,1,4,4,6,6,1,2,2,2,2,4,4,6,5,5,6,3,5,1,5,3],
 Seed {unSeed = 439652522})

Generate a selection of alphabetic passwords!

ghci> iterGen (iterGen alphabetic 12) 10 (Seed 99)
(["xgphyvqruxjm", "whonjjrgumxj",
  "hfyupajxbjgt", "hzdvrdqmdouu",
  "ukeaxhjumkmm", "hdglqrrohydr",
  "mbvtuwstgkob", "yzjjtdtjroqp",
  "yusfsbjlusek", "ghtfbdctvgmq"],
 Seed {unSeed = 1959147024})

Or arbitrary passwords:

ghci> iterGen (iterGen anyChar 14) 10 (Seed 99)
(["TG9Bc*&f&R1%!H", "w$pB1%woPRRlsA",
  "X%TH$f2^3ztBv$", "kI)ckW#cgI^B3M",
  "8ua63x%xupL#HM", "x9KjV@Q&g7sgi^",
  "&3Bttv^pDOY9&(", "CXCrrL%IcQMPPh",
  "jDMz5QMyTs2XRM", "hntf5)exR9owxI"],
 Seed {unSeed = 1528987498})

Ignore

Leave these alone – these are some special-purpose generators used in my test cases.