# Summative 3
## Requirements
- All questions are worth 35 marks, except for the last question, which is worth
30 marks.
- The first part is on monads and a game of chance.
The second part is about parsing English.
- Copy the file `Summative3-Template.hs` to a new file called `Summative3.hs`
and write your solutions in `Summative3.hs`.
**Don't change the header of this
file, _including the module declaration_, and, moreover, _don't_ change the
type signature of any of the given functions for you to complete.**
- Solve the exercises below in the file `Summative3.hs`.
- In this assignment you are allowed to use Haskell library functions that are
available in CoCalc. Look them up at [Hoogle](https://hoogle.haskell.org/).
- Run the pre-submit script to check for any (compilation) errors **before**
submitting by running in the terminal:
```bash
$ ./presubmit.sh Summative3
```
(If you get an error saying "permission denied", try: `$ chmod +x
presubmit.sh`.)
If this fails, you are not ready to submit, and any submission that doesn't
pass the presubmit test is not eligible for marking.
- Submit your file `Summative3.hs` via Canvas at https://canvas.bham.ac.uk/courses/46061/assignments/252202 .
## 1. Monads and a game of chance
We are going to consider the following game of chance.
#### Six-tosses-and-a-roll
1. toss a coin six times and count the number of heads you got;
1. roll a die once;
1. if the number on the die is greater than or equal to the number of heads,
then you win, else you lose.
What are the odds of winning this game? There are (at least) two ways of trying
to answer this question:
1. Compute all possibilities and see how many end up in wins.
1. We could implement random coin tosses and die rolls and run a lot of random
trials keeping track of the number of wins.
With monads we can do both, pretty much at the same time!
### Modelling the game
We first define some data types and instances (in `Types.hs`) that allow us to
model the game above.
```haskell
import System.Random
data Coin = H | T
deriving (Show, Eq, Enum, Bounded)
data Die = D1 | D2 | D3 | D4 | D5 | D6
deriving (Show, Eq, Enum, Bounded)
data Outcome = Win | Lose
deriving (Show, Eq)
```
Next we introduce the class of `ChanceMonad`s with some instances.
Note that for a monad `m`, `toss` gives you a "monadic coin" of type `m Coin`.
The instances given below should make it easier to understand this interface.
```haskell
class Monad m => ChanceMonad m where
toss :: m Coin
roll :: m Die
```
Here is our first instance, using the `[]` monad:
```haskell
instance ChanceMonad [] where
toss = [H,T]
roll = [D1 .. D6]
```
Note that `roll` simply gives us a list of all possible die roll
outcomes. Similarly, `toss` returns a list of all possible coin toss outcomes.
You can test this in `ghci` by running
```hs
> roll :: [Die]
[D1,D2,D3,D4,D5,D6]
> toss :: [Coin]
[H,T]
```
As we're taking `m` to be the `[]` monad in our test, we need to tell Haskell
that the type of `roll` should be `[Die]`.
Getting random coin tosses and die rolls is a little bit more involved. Given
two integers `lo` and `hi`, Haskell can generate random integers `x` with `lo <=
x <= hi`. Using that `Coin` and `Die` derive `Enum` and `Bounded`, we can use
this to create generators for `Coin` and `Die`.
```haskell
instance Random Coin where
randomR (lo,hi) g = (toEnum i , g')
where
(i,g') = randomR (fromEnum lo , fromEnum hi) g
random g = randomR (minBound,maxBound) g
instance Random Die where
randomR (lo,hi) g = (toEnum i , g')
where
(i,g') = randomR (fromEnum lo , fromEnum hi) g
random g = randomR (minBound,maxBound) g
```
The random number generator runs in the `IO` monad, because it needs a _seed_, which
is initialised automatically by using the time of day or Linux's kernel random
number generator. Now we can get random coin tosses and die rolls by:
```haskell
instance ChanceMonad IO where
roll = getStdRandom (random)
toss = getStdRandom (random)
```
You can test this in `ghci` by running
```hs
> roll :: IO Die
D5
```
or (since `ghci` defaults to the `IO` monad) just
```hs
> roll
D2
> roll
D3
> roll
D3
> toss
H
> toss
H
> toss
T
```
Finally, here is an example of playing a very simple game of chance (using
`do`-notation):
```haskell
headsOrTails :: ChanceMonad m => m Outcome
headsOrTails = do
c <- toss
if c == H then return Win else return Lose
```
### Exercise 1.1.
Write a function
```haskell
experiments :: ChanceMonad m => m a -> Integer -> m [a]
```
such that `experiments (headsOrTails :: [Outcome]) n` returns all possible
outcomes when playing the `headsOrTails` game `n` times, e.g.
```hs
experiments (headsOrTails :: [Outcome]) 2 = [[Win,Win],[Lose,Win],[Win,Lose],[Lose,Lose]]
```
and ```experiments headsOrTails 5``` returns the results of 5 random
`headsOrTails` games, e.g.
```hs
> experiments (headsOrTails :: IO Outcome) 5
[Win,Win,Win,Lose,Win]
> experiments (headsOrTails :: IO Outcome) 5
[Win,Lose,Win,Lose,Win]
```
Because `ghci` defaults to the `IO` monad, the above may also be written as
```hs
> experiments headsOrTails 5
```