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.
– Run the pre-submit script to check for any (compilation) errors BEFORE submitting by running in the terminal:
$ ./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 and count the number of eyes you got; 1. if the number of eyes 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 the above.
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 ChanceMonads 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.
class Monad m => ChanceMonad m where
toss :: m Coin
roll :: m Die
Here is our first instance, using the [] monad:
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
> 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.
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:
instance ChanceMonad IO where
roll = getStdRandom (random)
toss = getStdRandom (random)
You can test this in ghci by running
> roll :: IO Die
D5
or (since ghci defaults to the IO monad) just
> 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):
headsOrTails :: ChanceMonad m => m Outcome
headsOrTails = do
c <- toss
if c == H then return Win else return Lose
Exercise 1.1.
Write a function
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.
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.
> 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
> experiments headsOrTails 5
REMARK: The order of the elements of the output of experiments (headsOrTails :: IO Outcome) n does not matter. So your output should be a _permutation_ of the above output.
Exercise 1.2.
Write a function
gameAnnotated :: ChanceMonad m => m ([Coin],Die,Outcome)
that implements the game _Six-tosses-and-a-roll_ described at the top.
Running it with the IO monad should give you some random tosses, a random roll and the corresponding outcome.
> gameAnnotated :: IO ([Coin],Die,Outcome)
([H,T,T,T,T,T],D5,Win)
> gameAnnotated — the IO monad is the default in ghci, so we may omit the type annotation
([H,T,T,H,T,H],D2,Lose)
> gameAnnotated
([T,H,H,T,T,H],D3,Win)
Running it with the [] monad should give you all possible tosses and rolls with their corresponding outcome:
gameAnnotated :: [([Coin],Die,Outcome)]
[([H,H,H,H,H,H],D1,Lose),([H,H,H,H,H,H],D2,Lose),([H,H,H,H,H,H],D3,Lose),([H,H,H,H,H,H],D4,Lose),([H,H,H,H,H,H],D5,Lose),([H,H,H,H,H,H],D6,Win),([T,H,H,H,H,H],D1,Lose),([T,H,H,H,H,H],D2,Lose),([T,H,H,H,H,H],D3,Lose),([T,H,H,H,H,H],D4,Lose),([T,H,H,H,H,H],D5,Win),([T,H,H,H,H,H],D6,Win),([H,T,H,H,H,H],D1,Lose),([H,T,H,H,H,H],D2,Lose),([H,T,H,H,H,H],D3,Lose),([H,T,H,H,H,H],D4,Lose),([H,T,H,H,H,H],D5,Win),([H,T,H,H,H,H],D6,Win),([T,T,H,H,H,H],D1,Lose),([T,T,H,H,H,H],D2,Lose),([T,T,H,H,H,H],D3,Lose),([T,T,H,H,H,H],D4,Win),([T,T,H,H,H,H],D5,Win),([T,T,H,H,H,H],D6,Win),([H,H,T,H,H,H],D1,Lose),([H,H,T,H,H,H],D2,Lose),([H,H,T,H,H,H],D3,Lose),([H,H,T,H,H,H],D4,Lose),([H,H,T,H,H,H],D5,Win),([H,H,T,H,H,H],D6,Win),([T,H,T,H,H,H],D1,Lose),([T,H,T,H,H,H],D2,Lose),([T,H,T,H,H,H],D3,Lose),([T,H,T,H,H,H],D4,Win),([T,H,T,H,H,H],D5,Win),([T,H,T,H,H,H],D6,Win),([H,T,T,H,H,H],D1,Lose),([H,T,T,H,H,H],D2,Lose),([H,T,T,H,H,H],D3,Lose),([H,T,T,H,H,H],D4,Win),([H,T,T,H,H,H],D5,Win),([H,T,T,H,H,H],D6,Win),([T,T,T,H,H,H],D1,Lose),([T,T,T,H,H,H],D2,Lose),([T,T,T,H,H,H],D3,Win),([T,T,T,H,H,H],D4,Win),([T,T,T,H,H,H],D5,Win),([T,T,T,H,H,H],D6,Win),([H,H,H,T,H,H],D1,Lose),([H,H,H,T,H,H],D2,Lose),([H,H,H,T,H,H],D3,Lose),([H,H,H,T,H,H],D4,Lose),([H,H,H,T,H,H],D5,Win),([H,H,H,T,H,H],D6,Win),([T,H,H,T,H,H],D1,Lose),([T,H,H,T,H,H],D2,Lose),([T,H,H,T,H,H],D3,Lose),([T,H,H,T,H,H],D4,Win),([T,H,H,T,H,H],D5,Win),([T,H,H,T,H,H],D6,Win),([H,T,H,T,H,H],D1,Lose),([H,T,H,T,H,H],D2,Lose),([H,T,H,T,H,H],D3,Lose),([H,T,H,T,H,H],D4,Win),([H,T,H,T,H,H],D5,Win),([H,T,H,T,H,H],D6,Win),([T,T,H,T,H,H],D1,Lose),([T,T,H,T,H,H],D2,Lose),([T,T,H,T,H,H],D3,Win),([T,T,H,T,H,H],D4,Win),([T,T,H,T,H,H],D5,Win),([T,T,H,T,H,H],D6,Win),([H,H,T,T,H,H],D1,Lose),([H,H,T,T,H,H],D2,Lose),([H,H,T,T,H,H],D3,Lose),([H,H,T,T,H,H],D4,Win),([H,H,T,T,H,H],D5,Win),([H,H,T,T,H,H],D6,Win),([T,H,T,T,H,H],D1,Lose),([T,H,T,T,H,H],D2,Lose),([T,H,T,T,H,H],D3,Win),([T,H,T,T,H,H],D4,Win),([T,H,T,T,H,H],D5,Win),([T,H,T,T,H,H],D6,Win),([H,T,T,T,H,H],D1,Lose),([H,T,T,T,H,H],D2,Lose),([H,T,T,T,H,H],D3,Win),([H,T,T,T,H,H],D4,Win),([H,T,T,T,H,H],D5,Win),([H,T,T,T,H,H],D6,Win),([T,T,T,T,H,H],D1,Lose),([T,T,T,T,H,H],D2,Win),([T,T,T,T,H,H],D3,Win),([T,T,T,T,H,H],D4,Win),([T,T,T,T,H,H],D5,Win),([T,T,T,T,H,H],D6,Win),([H,H,H,H,T,H],D1,Lose),([H,H,H,H,T,H],D2,Lose),([H,H,H,H,T,H],D3,Lose),([H,H,H,H,T,H],D4,Lose),([H,H,H,H,T,H],D5,Win),([H,H,H,H,T,H],D6,Win),([T,H,H,H,T,H],D1,Lose),([T,H,H,H,T,H],D2,Lose),([T,H,H,H,T,H],D3,Lose),([T,H,H,H,T,H],D4,Win),([T,H,H,H,T,H],D5,Win),([T,H,H,H,T,H],D6,Win),([H,T,H,H,T,H],D1,Lose),([H,T,H,H,T,H],D2,Lose),([H,T,H,H,T,H],D3,Lose),([H,T,H,H,T,H],D4,Win),([H,T,H,H,T,H],D5,Win),([H,T,H,H,T,H],D6,Win),([T,T,H,H,T,H],D1,Lose),([T,T,H,H,T,H],D2,Lose),([T,T,H,H,T,H],D3,Win),([T,T,H,H,T,H],D4,Win),([T,T,H,H,T,H],D5,Win),([T,T,H,H,T,H],D6,Win),([H,H,T,H,T,H],D1,Lose),([H,H,T,H,T,H],D2,Lose),([H,H,T,H,T,H],D3,Lose),([H,H,T,H,T,H],D4,Win),([H,H,T,H,T,H],D5,Win),([H,H,T,H,T,H],D6,Win),([T,H,T,H,T,H],D1,Lose),([T,H,T,H,T,H],D2,Lose),([T,H,T,H,T,H],D3,Win),([T,H,T,H,T,H],D4,Win),([T,H,T,H,T,H],D5,Win),([T,H,T,H,T,H],D6,Win),([H,T,T,H,T,H],D1,Lose),([H,T,T,H,T,H],D2,Lose),([H,T,T,H,T,H],D3,Win),([H,T,T,H,T,H],D4,Win),([H,T,T,H,T,H],D5,Win),([H,T,T,H,T,H],D6,Win),([T,T,T,H,T,H],D1,Lose),([T,T,T,H,T,H],D2,Win),([T,T,T,H,T,H],D3,Win),([T,T,T,H,T,H],D4,Win),([T,T,T,H,T,H],D5,Win),([T,T,T,H,T,H],D6,Win),([H,H,H,T,T,H],D1,Lose),([H,H,H,T,T,H],D2,Lose),([H,H,H,T,T,H],D3,Lose),([H,H,H,T,T,H],D4,Win),([H,H,H,T,T,H],D5,Win),([H,H,H,T,T,H],D6,Win),([T,H,H,T,T,H],D1,Lose),([T,H,H,T,T,H],D2,Lose),([T,H,H,T,T,H],D3,Win),([T,H,H,T,T,H],D4,Win),([T,H,H,T,T,H],D5,Win),([T,H,H,T,T,H],D6,Win),([H,T,H,T,T,H],D1,Lose),([H,T,H,T,T,H],D2,Lose),([H,T,H,T,T,H],D3,Win),([H,T,H,T,T,H],D4,Win),([H,T,H,T,T,H],D5,Win),([H,T,H,T,T,H],D6,Win),([T,T,H,T,T,H],D1,Lose),([T,T,H,T,T,H],D2,Win),([T,T,H,T,T,H],D3,Win),([T,T,H,T,T,H],D4,Win),([T,T,H,T,T,H],D5,Win),([T,T,H,T,T,H],D6,Win),([H,H,T,T,T,H],D1,Lose),([H,H,T,T,T,H],D2,Lose),([H,H,T,T,T,H],D3,Win),([H,H,T,T,T,H],D4,Win),([H,H,T,T,T,H],D5,Win),([H,H,T,T,T,H],D6,Win),([T,H,T,T,T,H],D1,Lose),([T,H,T,T,T,H],D2,Win),([T,H,T,T,T,H],D3,Win),([T,H,T,T,T,H],D4,Win),([T,H,T,T,T,H],D5,Win),([T,H,T,T,T,H],D6,Win),([H,T,T,T,T,H],D1,Lose),([H,T,T,T,T,H],D2,Win),([H,T,T,T,T,H],D3,Win),([H,T,T,T,T,H],D4,Win),([H,T,T,T,T,H],D5,Win),([H,T,T,T,T,H],D6,Win),([T,T,T,T,T,H],D1,Win),([T,T,T,T,T,H],D2,Win),([T,T,T,T,T,H],D3,Win),([T,T,T,T,T,H],D4,Win),([T,T,T,T,T,H],D5,Win),([T,T,T,T,T,H],D6,Win),([H,H,H,H,H,T],D1,Lose),([H,H,H,H,H,T],D2,Lose),([H,H,H,H,H,T],D3,Lose),([H,H,H,H,H,T],D4,Lose),([H,H,H,H,H,T],D5,Win),([H,H,H,H,H,T],D6,Win),([T,H,H,H,H,T],D1,Lose),([T,H,H,H,H,T],D2,Lose),([T,H,H,H,H,T],D3,Lose),([T,H,H,H,H,T],D4,Win),([T,H,H,H,H,T],D5,Win),([T,H,H,H,H,T],D6,Win),([H,T,H,H,H,T],D1,Lose),([H,T,H,H,H,T],D2,Lose),([H,T,H,H,H,T],D3,Lose),([H,T,H,H,H,T],D4,Win),([H,T,H,H,H,T],D5,Win),([H,T,H,H,H,T],D6,Win),([T,T,H,H,H,T],D1,Lose),([T,T,H,H,H,T],D2,Lose),([T,T,H,H,H,T],D3,Win),([T,T,H,H,H,T],D4,Win),([T,T,H,H,H,T],D5,Win),([T,T,H,H,H,T],D6,Win),([H,H,T,H,H,T],D1,Lose),([H,H,T,H,H,T],D2,Lose),([H,H,T,H,H,T],D3,Lose),([H,H,T,H,H,T],D4,Win),([H,H,T,H,H,T],D5,Win),([H,H,T,H,H,T],D6,Win),([T,H,T,H,H,T],D1,Lose),([T,H,T,H,H,T],D2,Lose),([T,H,T,H,H,T],D3,Win),([T,H,T,H,H,T],D4,Win),([T,H,T,H,H,T],D5,Win),([T,H,T,H,H,T],D6,Win),([H,T,T,H,H,T],D1,Lose),([H,T,T,H,H,T],D2,Lose),([H,T,T,H,H,T],D3,Win),([H,T,T,H,H,T],D4,Win),([H,T,T,H,H,T],D5,Win),([H,T,T,H,H,T],D6,Win),([T,T,T,H,H,T],D1,Lose),([T,T,T,H,H,T],D2,Win),([T,T,T,H,H,T],D3,Win),([T,T,T,H,H,T],D4,Win),([T,T,T,H,H,T],D5,Win),([T,T,T,H,H,T],D6,Win),([H,H,H,T,H,T],D1,Lose),([H,H,H,T,H,T],D2,Lose),([H,H,H,T,H,T],D3,Lose),([H,H,H,T,H,T],D4,Win),([H,H,H,T,H,T],D5,Win),([H,H,H,T,H,T],D6,Win),([T,H,H,T,H,T],D1,Lose),([T,H,H,T,H,T],D2,Lose),([T,H,H,T,H,T],D3,Win),([T,H,H,T,H,T],D4,Win),([T,H,H,T,H,T],D5,Win),([T,H,H,T,H,T],D6,Win),([H,T,H,T,H,T],D1,Lose),([H,T,H,T,H,T],D2,Lose),([H,T,H,T,H,T],D3,Win),([H,T,H,T,H,T],D4,Win),([H,T,H,T,H,T],D5,Win),([H,T,H,T,H,T],D6,Win),([T,T,H,T,H,T],D1,Lose),([T,T,H,T,H,T],D2,Win),([T,T,H,T,H,T],D3,Win),([T,T,H,T,H,T],D4,Win),([T,T,H,T,H,T],D5,Win),([T,T,H,T,H,T],D6,Win),([H,H,T,T,H,T],D1,Lose),([H,H,T,T,H,T],D2,Lose),([H,H,T,T,H,T],D3,Win),([H,H,T,T,H,T],D4,Win),([H,H,T,T,H,T],D5,Win),([H,H,T,T,H,T],D6,Win),([T,H,T,T,H,T],D1,Lose),([T,H,T,T,H,T],D2,Win),([T,H,T,T,H,T],D3,Win),([T,H,T,T,H,T],D4,Win),([T,H,T,T,H,T],D5,Win),([T,H,T,T,H,T],D6,Win),([H,T,T,T,H,T],D1,Lose),([H,T,T,T,H,T],D2,Win),([H,T,T,T,H,T],D3,Win),([H,T,T,T,H,T],D4,Win),([H,T,T,T,H,T],D5,Win),([H,T,T,T,H,T],D6,Win),([T,T,T,T,H,T],D1,Win),([T,T,T,T,H,T],D2,Win),([T,T,T,T,H,T],D3,Win),([T,T,T,T,H,T],D4,Win),([T,T,T,T,H,T],D5,Win),([T,T,T,T,H,T],D6,Win),([H,H,H,H,T,T],D1,Lose),([H,H,H,H,T,T],D2,Lose),([H,H,H,H,T,T],D3,Lose),([H,H,H,H,T,T],D4,Win),([H,H,H,H,T,T],D5,Win),([H,H,H,H,T,T],D6,Win),([T,H,H,H,T,T],D1,Lose),([T,H,H,H,T,T],D2,Lose),([T,H,H,H,T,T],D3,Win),([T,H,H,H,T,T],D4,Win),([T,H,H,H,T,T],D5,Win),([T,H,H,H,T,T],D6,Win),([H,T,H,H,T,T],D1,Lose),([H,T,H,H,T,T],D2,Lose),([H,T,H,H,T,T],D3,Win),([H,T,H,H,T,T],D4,Win),([H,T,H,H,T,T],D5,Win),([H,T,H,H,T,T],D6,Win),([T,T,H,H,T,T],D1,Lose),([T,T,H,H,T,T],D2,Win),([T,T,H,H,T,T],D3,Win),([T,T,H,H,T,T],D4,Win),([T,T,H,H,T,T],D5,Win),([T,T,H,H,T,T],D6,Win),([H,H,T,H,T,T],D1,Lose),([H,H,T,H,T,T],D2,Lose),([H,H,T,H,T,T],D3,Win),([H,H,T,H,T,T],D4,Win),([H,H,T,H,T,T],D5,Win),([H,H,T,H,T,T],D6,Win),([T,H,T,H,T,T],D1,Lose),([T,H,T,H,T,T],D2,Win),([T,H,T,H,T,T],D3,Win),([T,H,T,H,T,T],D4,Win),([T,H,T,H,T,T],D5,Win),([T,H,T,H,T,T],D6,Win),([H,T,T,H,T,T],D1,Lose),([H,T,T,H,T,T],D2,Win),([H,T,T,H,T,T],D3,Win),([H,T,T,H,T,T],D4,Win),([H,T,T,H,T,T],D5,Win),([H,T,T,H,T,T],D6,Win),([T,T,T,H,T,T],D1,Win),([T,T,T,H,T,T],D2,Win),([T,T,T,H,T,T],D3,Win),([T,T,T,H,T,T],D4,Win),([T,T,T,H,T,T],D5,Win),([T,T,T,H,T,T],D6,Win),([H,H,H,T,T,T],D1,Lose),([H,H,H,T,T,T],D2,Lose),([H,H,H,T,T,T],D3,Win),([H,H,H,T,T,T],D4,Win),([H,H,H,T,T,T],D5,Win),([H,H,H,T,T,T],D6,Win),([T,H,H,T,T,T],D1,Lose),([T,H,H,T,T,T],D2,Win),([T,H,H,T,T,T],D3,Win),([T,H,H,T,T,T],D4,Win),([T,H,H,T,T,T],D5,Win),([T,H,H,T,T,T],D6,Win),([H,T,H,T,T,T],D1,Lose),([H,T,H,T,T,T],D2,Win),([H,T,H,T,T,T],D3,Win),([H,T,H,T,T,T],D4,Win),([H,T,H,T,T,T],D5,Win),([H,T,H,T,T,T],D6,Win),([T,T,H,T,T,T],D1,Win),([T,T,H,T,T,T],D2,Win),([T,T,H,T,T,T],D3,Win),([T,T,H,T,T,T],D4,Win),([T,T,H,T,T,T],D5,Win),([T,T,H,T,T,T],D6,Win),([H,H,T,T,T,T],D1,Lose),([H,H,T,T,T,T],D2,Win),([H,H,T,T,T,T],D3,Win),([H,H,T,T,T,T],D4,Win),([H,H,T,T,T,T],D5,Win),([H,H,T,T,T,T],D6,Win),([T,H,T,T,T,T],D1,Win),([T,H,T,T,T,T],D2,Win),([T,H,T,T,T,T],D3,Win),([T,H,T,T,T,T],D4,Win),([T,H,T,T,T,T],D5,Win),([T,H,T,T,T,T],D6,Win),([H,T,T,T,T,T],D1,Win),([H,T,T,T,T,T],D2,Win),([H,T,T,T,T,T],D3,Win),([H,T,T,T,T,T],D4,Win),([H,T,T,T,T,T],D5,Win),([H,T,T,T,T,T],D6,Win),([T,T,T,T,T,T],D1,Win),([T,T,T,T,T,T],D2,Win),([T,T,T,T,T,T],D3,Win),([T,T,T,T,T,T],D4,Win),([T,T,T,T,T,T],D5,Win),([T,T,T,T,T,T],D6,Win)]
REMARK: As in Exercise 1.1, the order of the elements given by the output of gameAnnotated does not matter. So your output should be a _permutation_ of the above output.
The fact that the tosses and rolls are included in the output of gameAnnotated should make it easier to debug your code.
Exercise 1.3.
Write a function
game :: ChanceMonad m => m Outcome
implementing _Six-tosses-and-a-roll_ as above, but just giving the outcome now.
REMARK: As in Exercise 1.2, the order of the elements given by the output of game does not matter.
Exercise 1.4.
Write a function
odds :: [Outcome] -> Float
that given a game of chance computes the odds of winning it. For example,
odds headsOrTails = 0.5
odds game = 0.6640625
Testing your code: approximating odds by trials
You could write a function
trials :: IO Outcome -> Integer -> IO Float
that given a game of chance and a number n (where we assume that n > 0), plays the game n times and returns the percentage of games won. For example,
> trials headsOrTails 100
0.43
> trials headsOrTails 1000
0.507
> trials headsOrTails 10000
0.4944
> trials game 100
0.62
> trials game 10000
0.6685
> trials game 100
0.649
For large n, the result of trials g n should be close to odds g.
Further testing your code
You can further test your code by coming up with some more games and checking whether odds and trialsagree with what you would expect.
2. Parsing English
Your task in this question is to write a parser for a small subset of English given by the following grammar. The abbreviations NP, VP and PP stand for “noun phrase”, “verb phrase” and “preposition phrase”, respectively. So, according to this grammar, a sentence is a noun phrase followed by a verb phrase.
Sentence ::= NP VP
NP ::= Pronoun | ProperNoun | Determiner Nominal
VP ::= Verb | Verb NP | Verb NP PP | Verb PP
PP ::= Preposition NP
Nominal ::= Noun | Noun Nominal
Noun ::= “flight” | “breeze” | “trip” | “morning”
Verb ::= “is” | “prefer” | “like” | “need” | “want” | “fly”
Pronoun ::= “me” | “I” | “you” | “it”
Determiner ::= “the” | “a” | “an” | “this” | “these” | “that”
Preposition ::= “from” | “to” | “on” | “near”
ProperNoun ::= “Alaska” | “Baltimore” | “Los Angeles” | “Chicago”
For example: this grammar recognizes
I like you
I prefer a morning trip
Alaska is Alaska
as valid sentences, but
Chicago is near to Baltimore
I prefer this
I love you
I you
I want something
are not valid according to the grammar (carefully check this yourself!).
To represent the parse trees generated by this grammar, you will use some types that we provide. The first of these is Sort, the type of syntactic sorts:
data Sort = Sentence
| NP
| VP
| PP
| Noun
| Verb
| Pronoun
| ProperNoun
| Nominal
| Determiner
| Preposition
deriving (Eq, Show)
The sort Sentence is the sort of well-formed sentences.
The next type you will need is the type of parse trees (or syntax trees) that we define as follows:
data Tree = Branch Sort [Tree]
| Leaf Sort String deriving (Eq, Show)
The leaves of this tree are lexical items (i.e. words) and the branches are applications of productions from the grammar. The idea is that the noun “morning” should be parsed as a leaf of type Noun i.e.
Leaf Noun “morning”
which is a singleton nominal
Branch Nominal [Leaf Noun “morning”]
By using the production of NP that says a Determiner followed by a Nominal is an example of NP, we can parse “a morning” as
Branch NP [Leaf Determiner “a”, Branch Nominal [Leaf Determiner “morning”]]
We have also included the following constants (in Types.hs) for your convenience:
nouns :: [String]
nouns = [“flight”, “breeze”, “trip”, “morning”]
verbs :: [String]
verbs = [“is”, “prefer”, “like”, “need”, “want”, “fly”]
pronouns :: [String]
pronouns = [“me”, “I”, “you”, “it”]
determiners :: [String]
determiners = [“these”, “the” , “an”, “a”, “this”, “that”]
prepositions :: [String]
prepositions = [“from”, “to”, “on”, “near”]
properNouns :: [String]
properNouns = [“Alaska”, “Baltimore”, “Los Angeles”, “Chicago”, “United”, “American”]
Warning on spaces
In all of the below, strings with more than one consecutive spaces should be treated as strings with single spaces, i.e. there should be no difference between parsing
a morning flight
and
a morning flight
However,
a morning flight
is (of course) different from
amorningflight
and
a morningflight
Exercise 2.1.
Write a function
oneOf :: [String] -> Parser String
such that oneOf [s₁,s₂,…,sₙ] successfully parses a string starting with _one of_ the strings s₁, s₂,…, or sₙ. For example:
parse (oneOf nouns) “flight” = [(“flight”,””)]
parse (oneOf nouns) “something” = []
parse (oneOf nouns) “morning something” = [(“morning”,” something”)]
parse (oneOf nouns) “something morning” = []
parse (oneOf nouns) “morning trip” = [(“morning”,” trip”)]
parse (oneOf nouns) “morning breeze trip” = [(“morning”,” breeze trip”)]
Exercise 2.2.
Write parsers for nouns, verbs, pronouns, proper nouns, determiners and prepositions:
noun :: Parser Tree
verb :: Parser Tree
pronoun :: Parser Tree
properNoun :: Parser Tree
determiner :: Parser Tree
preposition :: Parser Tree
For example:
parse noun “flight” = [(Leaf Noun “flight”,””)]
parse noun “something” = []
parse noun “morning trip” = [(Leaf Noun “morning”,” trip”)]
parse verb “want something” = [(Leaf Verb “want”,” something”)]
parse determiner “the” = [(Leaf Determiner “the”,””)]
parse determiner “these” = [(Leaf Determiner “these”,””)]
parse determiner “a” = [(Leaf Determiner “a”,””)]
parse determiner “an” = [(Leaf Determiner “an”,””)]
and so on.
Exercise 2.3.
Write a parser for nominals:
nominal :: Parser Tree
For example:
parse nominal “morning flight” = [(Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “flight”]],””)]
parse nominal “morningflight” = [(Branch Nominal [Leaf Noun “morning”],”flight”)]
parse nominal “morning trip flight” = [(Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “trip”,Branch Nominal [Leaf Noun “flight”]]],””)]
parse nominal “morning something” = [(Branch Nominal [Leaf Noun “morning”],” something”)]
Exercise 2.4.
Write a parser for noun phrases (NPs):
np :: Parser Tree
For example:
parse np “a morning flight” = [(Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “flight”]]],””)]
parse np “I” = [(Branch NP [Leaf Pronoun “I”],””)]
parse np “Los Angeles” = [(Branch NP [Leaf ProperNoun “Los Angeles”],””)]
REMARK: You may find it useful to define a general function
branch :: Sort -> [Parser Tree] -> Parser Tree
to help you with this (and the coming exercises). This is NOT mandatory, however. You are free to solve the exercises in a different way.
REMARK: You may like to use the following function (provided in the template), which is a modification of space in Parsing.hs:
space’ :: Parser ()
space’ = do some (sat isSpace)
return ()
The difference between space’ and space is that space’ parses _one_ or more spaces, whereas space parses _zero_ or more spaces.
Exercise 2.5.
Write a parser for verb phrases (VPs):
vp :: Parser Tree
For example:
parse vp “like” = [(Branch VP [Leaf Verb “like”],””)]
parse vp “need a flight” = [(Branch VP [Leaf Verb “need”,Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf Noun “flight”]]],””)]
parse vp “want a morning trip” = [(Branch VP [Leaf Verb “want”,Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “trip”]]]],””)]
parse vp “fly from Los Angeles” = [(Branch VP [Leaf Verb “fly”,Branch PP [Leaf Preposition “from”,Branch NP [Leaf ProperNoun “Los Angeles”]]],””)]
Exercise 2.6.
Write a parser for preposition phrases (PPs):
pp :: Parser Tree
For example:
parse pp “from Baltimore” = [(Branch PP [Leaf Preposition “from”,Branch NP [Leaf ProperNoun “Baltimore”]],””)]
parse pp “near me” = [(Branch PP [Leaf Preposition “near”,Branch NP [Leaf Pronoun “me”]],””)]
Exercise 2.7.
Write a parser for sentences:
sent :: Parser Tree
For example:
parse sent “you like a morning breeze” = [(Branch Sentence [Branch NP [Leaf Pronoun “you”],Branch VP [Leaf Verb “like”,Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “breeze”]]]]],””)]
parse sent “I like you” = [(Branch Sentence [Branch NP [Leaf Pronoun “I”],Branch VP [Leaf Verb “like”,Branch NP [Leaf Pronoun “you”]]],””)]
parse sent “I love you” = []
parse sent “I you” = []
You can use the following function to test.
parseSentence :: String -> Maybe Tree
parseSentence s = case (parse sent s) of
[(t,””)] -> Just t
_ -> Nothing
Note that parseSentence s returns Nothing precisely when s is not a sentence according to the above grammar. If s is a sentence according to the above grammar, then parseSentence s should return Just t where t is the syntax tree representing s. For example:
parseSentence “I like you” = Just (Branch Sentence [Branch NP [Leaf Pronoun “I”],Branch VP [Leaf Verb “like”,Branch NP [Leaf Pronoun “you”]]])
parseSentence “I love you” = Nothing
parseSentence “I like you a lot” = Nothing