# Assignment 8 specification

Tue Nov 6

module A08Sol where

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

data Seed = Seed { unSeed :: Int }
deriving (Eq, Show)

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

type Gen s a = s -> (a, s)

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

rand :: Gen Seed Int
rand (Seed s) = (s', Seed s')
where
s' = (s * 16807) mod 0x7FFFFFFF

# Coin flips

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

data CoinFlip = Heads | Tails
deriving (Eq, Show, Bounded, Enum)

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.

coinFromInt :: Int -> CoinFlip

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

flipCoin :: Gen Seed CoinFlip

# 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:

iterGen :: Gen s a -> Int -> Gen s [a]

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.

iterGen gen 0 s0 = error "TODO"
iterGen gen n s0 = error "TODO"

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.

data Color = Red | Orange | Yellow | Green | Blue
deriving (Eq, Show, Enum, Bounded)

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.

genColor :: Gen Seed Color

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: fmapGen :: (a -> b) -> Gen s a -> Gen s b To further understand this function, it can be helpful to expand the Gen synonym, which would make it: fmapGen :: (a -> b) -> (s -> (a,s)) -> s -> (b,s) Here’s a stub for its definition: fmapGen f gen s0 = error "TODO" 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: randMod :: Int -> Gen Seed Int randMod k = fmapGen (mod k) rand diceRoll :: Gen Seed Int diceRoll = fmapGen succ (randMod 6) alphabetic :: Gen Seed Char alphabetic = fmapGen (['a'..'z'] !!) (randMod 26) eligibleChars = ['a'..'z'] ++ ['A'..'Z'] ++ ['0'..'9'] ++ "!@#$%^&*()"
anyChar :: Gen Seed Char
anyChar = fmapGen (eligibleChars !!) (randMod (length eligibleChars))

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})

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.

always :: a -> Gen s a
always a s = (a,s)
makeGen :: (s -> s) -> Gen s s
makeGen f s = (s, f s)
successive :: Enum s => Gen s s
successive = makeGen succ
main :: IO ()
main = return ()