Projects Groups More
Search or jump to…
F
ahrensb
fp-learning-2020-2021 Repository
master
Name
! fp-learning-2020-2021 / Assignments / Summative3 /
History
Find file
Web IDE
Clone
aab786b2
Last update
3 days ago 17 hours ago 2 days ago 22 hours ago 3 days ago
Fixed minor typo
Rob Hallam authored 17 hours ago
..
Last commit
Parsing.hs
README.md Summative3-Template.hs Types.hs
presubmit.sh
Summative 3
Fixed minor typo
Typo fixes, clarification on parsing and template update Remove ‘United’ and ‘American’
Summative 3
README.md
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;
2. roll a die once;
3. 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.
2. 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. import System.Random
dataCoin =H|T
deriving (Show, Eq, Enum, Bounded)
dataDie =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.
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 :: [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 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 trials agree 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|VerbNP|VerbNPPP|VerbPP
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 Noun “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”]
Warning on spaces
In all of the below, strings with more than one consecutive space between two words should be treated the same as strings with single spaces, i.e. there should be no difference between parsing
a morning flight
and
a morning flight
That is, both these strings are represented by the syntax tree
Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “flight”]]] However,
a morning flight
is (of course) different from
amorningflight
and
a morningflight
Examples/Clarification (regarding spaces at the start and end):
parseSentence “I like you ” = Nothing
parseSentence ” I like you” = Nothing
parseSentence “I likeyou” = Nothing
parseSentence “I like you” = Just (Branch Sentence [Branch NP [Leaf Pronoun “I”],Branch VP [Leaf Verb “like”,Bran parseSentence “I like you” = Just (Branch Sentence [Branch NP [Leaf Pronoun “I”],Branch VP [Leaf Verb “like”,Bran
Variations in parsing
In parsing, you will have some freedom in writing your implementation.
In the examples below, we highlight our implementation, so that you may use it to guide you. However, you are free to deviate from this,
provided that your parser agrees with ours when run using the function parseTest (which is also available in the template) below:
parseTest :: Parser Tree -> String -> Maybe Tree parseTest p s = case (parse p s) of
[(t,””)] -> Just t _ -> Nothing
So for example in Exercise 2.3, if you have
parse nominal “morningflight” = [] instead of our
parse nominal “morningflight” = [(Branch Nominal [Leaf Noun “morning”],”flight”)]
then that’s OK, because when running this with parseTest both will return Nothing .
Exercise 2.1.
Write a function
oneOf :: [String] -> Parser String
such that oneOf [s1,s2,…,s ] successfully parses a string that is one of the strings s1 , s2 ,…, or s . For example:
parse (oneOf nouns) “flight”
parse (oneOf nouns) “something”
parse (oneOf nouns) “morning something”
parse (oneOf nouns) “something morning”
parse (oneOf nouns) “morning trip”
parse (oneOf nouns) “morning breeze trip” = [(“morning”,” breeze trip”)] parse (oneOf nouns) ” flight” = []
parse (oneOf nouns) “flight ” = [(“flight”,” “)]
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
parse noun
parse noun
parse verb
parse determiner “the”
parse determiner “these”
parse determiner “a”
parse determiner “an”
and so on.
Exercise 2.3.
Write a parser for nominals:
nominal :: Parser Tree For example:
= [(“flight”,””)]
= []
= [(“morning”,” something”)] = []
= [(“morning”,” trip”)]
= [(Leaf Noun “flight”,””)]
=[]
= [(Leaf Noun “morning”,” trip”)]
“flight”
“something”
“morning trip”
“want something” = [(Leaf Verb “want”,” something”)]
= [(Leaf Determiner “the”,””)]
= [(Leaf Determiner “these”,””)] = [(Leaf Determiner “a”,””)]
= [(Leaf Determiner “an”,””)]
= [(Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “flight”]], = [(Branch Nominal [Leaf Noun “morning”],”flight”)]
parse nominal “morning flight”
parse nominal “morningflight”
parse nominal “morning trip flight” = [(Branch Nominal [Leaf Noun “morning”,Branch Nominal [Leaf Noun “trip”,Branch parse nominal “morning something” = [(Branch Nominal [Leaf Noun “morning”],” something”)]
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.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 parse np “I” = [(Branch NP [Leaf Pronoun “I”],””)]
parse np “Los Angeles” = [(Branch NP [Leaf ProperNoun “Los Angeles”],””)]
parse np “Los Angeles” = []
Exercise 2.5.
Write a parser for verb phrases (VPs):
vp :: Parser Tree For example:
= [(Branch VP [Leaf Verb “like”],””)]
= [(Branch VP [Leaf Verb “need”,Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf
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 “lik
parse vp “like”
parse vp “need a flight”
parse vp “want a morning trip” = [(Branch VP [Leaf Verb “want”,Branch NP [Leaf Determiner “a”,Branch Nominal [Leaf parse vp “fly from Los Angeles” = [(Branch VP [Leaf Verb “fly”,Branch PP [Leaf Preposition “from”,Branch NP [Leaf
Exercise 2.6.
parse sent “I like you”
parse sent “I love you”
parse sent “I you”
You can use the following function to test.
parseSentence :: String -> Maybe Tree parseSentence = parseTest sent
= [(Branch Sentence [Branch NP [Leaf Pronoun “I”],Branch VP [Leaf Verb “like” =[]
=[]
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” parseSentence “I love you” = Nothing
parseSentence “I like you a lot” = Nothing
ch ch
e”