SUMMATIVE 2
The questions and marking scheme are designed so that the following holds:
40% third class (pass)
50% lower second, or 2.2
60% upper second, or 2.1
70% first class
– The last two questions are deliberately much harder than the other ones. They are designed to get you a first class mark if you do one, and a comfortable first class mark if you do both.
– The other questions add up to 65%, giving you a solid upper second, which is a very good mark.
Needless to say, the university doesn’t expect the majority of students to get a first class mark or degree. Hence we don’t expect everyone to attempt the hard questions. But, of course, everybody is encouraged to do so after they manage to do the previous ones.
– This module is 100% continuous assessment and there isn’t an exam. Plagiarism will not be tolerated.
Please regard this assignment as an exam.
– This summative assessment counts towards 2/5 of your final mark. The previous summative assessment counts towards 1/5, and the next one to 2/5, with a small amount of marks contributed by the Canvas quizzes.
Requirements
– Copy the file Summative2-Template.hs to a new file called Summative2.hs and write your solutions in Summative2.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 Summative2.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 Summative2
(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 Summative2.hs via Canvas at https://canvas.bham.ac.uk/courses/46061/assignments/252200.
Morse code
International Morse code is composed of five elements:
– short mark, dot or “dit” (·) – one unit long;
– longer mark, dash or “dah” (-) – three units long;
– inter-element gap between the dots and dashes within a character – one unit long;
– short gap (between letters) – three units long;
– medium gap (between words) – seven units long.
Please read this before proceeding further.
We represent a Morse code unit, called “atom” from now on, as either a beep or silence:
data Atom = Beep | Silence deriving (Eq, Show)
Then Morse code can be represented by a list of these atoms:
type Code = [Atom]
Now we can write constants for a short mark “·” (dit), a long mark “-” (dah), a gap between letters (shortGap) and a gap between words (mediumGap):
dit, dah, shortGap, mediumGap :: [Atom]
dit = [Beep, Silence]
dah = [Beep, Beep, Beep, Silence]
shortGap = replicate (3-1) Silence
mediumGap = replicate (7-1) Silence
Note that the length of shortGap and mediumGap are made so that a shortGap has the correct length 3 if following a dit or dah and a mediumGap has length 7 if following a dit or dah.
We can code symbols as follows
morseCode :: Char -> Code
morseCode ‘A’ = dit ++ dah
morseCode ‘B’ = dah ++ dit ++ dit ++ dit
morseCode ‘C’ = dah ++ dit ++ dah ++ dit
morseCode ‘D’ = dah ++ dit ++ dit
morseCode ‘E’ = dit
morseCode ‘F’ = dit ++ dit ++ dah ++ dit
morseCode ‘G’ = dah ++ dah ++ dit
morseCode ‘H’ = dit ++ dit ++ dit ++ dit
morseCode ‘I’ = dit ++ dit
morseCode ‘J’ = dit ++ dah ++ dah ++ dah
morseCode ‘K’ = dah ++ dit ++ dah
morseCode ‘L’ = dit ++ dah ++ dit ++ dit
morseCode ‘M’ = dah ++ dah
morseCode ‘N’ = dah ++ dit
morseCode ‘O’ = dah ++ dah ++ dah
morseCode ‘P’ = dit ++ dah ++ dah ++ dit
morseCode ‘Q’ = dah ++ dah ++ dit ++ dah
morseCode ‘R’ = dit ++ dah ++ dit
morseCode ‘S’ = dit ++ dit ++ dit
morseCode ‘T’ = dah
morseCode ‘U’ = dit ++ dit ++ dah
morseCode ‘V’ = dit ++ dit ++ dit ++ dah
morseCode ‘W’ = dit ++ dah ++ dah
morseCode ‘X’ = dah ++ dit ++ dit ++ dah
morseCode ‘Y’ = dah ++ dit ++ dah ++ dah
morseCode ‘Z’ = dah ++ dah ++ dit ++ dit
morseCode ‘1’ = dit ++ dah ++ dah ++ dah ++ dah
morseCode ‘2’ = dit ++ dit ++ dah ++ dah ++ dah
morseCode ‘3’ = dit ++ dit ++ dit ++ dah ++ dah
morseCode ‘4’ = dit ++ dit ++ dit ++ dit ++ dah
morseCode ‘5’ = dit ++ dit ++ dit ++ dit ++ dit
morseCode ‘6’ = dah ++ dit ++ dit ++ dit ++ dit
morseCode ‘7’ = dah ++ dah ++ dit ++ dit ++ dit
morseCode ‘8’ = dah ++ dah ++ dah ++ dit ++ dit
morseCode ‘9’ = dah ++ dah ++ dah ++ dah ++ dit
morseCode ‘0’ = dah ++ dah ++ dah ++ dah ++ dah
morseCode _ = undefined — Avoid warnings
We can represent the function morseTable by the following lookup table:
type Table = [(Char, Code)]
morseTable :: Table
morseTable = [ (c , morseCode c) | c <- ['A'..'Z']++['0'..'9'] ]
REMARK: We can get the function morseCode from the table using
lookup :: Eq a => a -> [(a, b)] -> Maybe b
from the prelude.
REMARK: The above datatypes, constants, morseCode and morseTable are all available in Types.hs. Do NOT change this file.
Exercises
You may wish to use your own helper functions.
Exercise 0: Getting Started
Copy the file Summative2-Template.hs into a new file Summative2.hs and work in that new file. Don’t modify the header of the file.
Exercise 1: Encode using a table
In the following parts of this exercise, the functions should work with any table, including morseTable but not only morseTable. You can use morseTable for testing your solution for correctness.
1. Write a function
encodeWord :: Table -> String -> Code
that, given _any_ table and a string with a SINGLE word in it, produces the code for that word. THE RESULTING CODE SHOULD HAVE A shortGap AFTER EVERY CHARACTER THAT IS NOT THE LAST.
Note that encodeWord should work for ANY table, not just morseTable.
Examples: hs encodeWord morseTable “” = [] encodeWord morseTable “A” = [Beep,Silence,Beep,Beep,Beep,Silence] encodeWord morseTable “0” = [Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence] encodeWord morseTable “HELLO” = [Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence] encodeWord morseTable “WORLD” = [Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence]
2. Write a function
encodeWords :: Table -> [String] -> Code
that, given _any_ table and a list of strings, encodes each string of the list, puts a mediumGap after every word that is not the last, and concatenates the results.
As above, this function should work for ANY table, not just morseTable.
Examples:
encodeWords morseTable [] = []
encodeWords morseTable [“007”] = [Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence]
encodeWords morseTable [“HI”,”THERE”] = [Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Silence,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence]
3. Write a function
encodeText :: Table -> String -> Code
that, given _any_ table and some string of words separated by spaces, encodes the text. SPACES SHOULD BECOME mediumGapS.
You may assume that the text consists only of single spaces and [‘A’..’Z’]++[‘0’..’9′] otherwise, and that the spaces do not occur at the end.
Examples:
encodeText morseTable “WORD” = [Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Beep,Silence]
encodeText morseTable “HI THERE” = [Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Silence,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence]
encodeText morseTable “THIS IS A TEST” = [Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Silence,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Silence,Silence,Silence,Silence,Beep,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Silence,Silence,Silence,Silence,Beep,Beep,Beep,Silence,Silence,Silence,Beep,Silence,Silence,Silence,Beep,Silence,Beep,Silence,Beep,Silence,Silence,Silence,Beep,Beep,Beep,Silence]
HINT: You may find it useful to define a general function
split :: Eq a => [a] -> [a] -> [[a]]
satisfying the following specification:
split ” ” “ABC DEF” = [“ABC”,”DEF”]
split shortGap (dit ++ shortGap ++ dah) = [dit,dah]
where the first argument of split indicates a word separator, which is ” ” in this example.
Exercise 2: Decode using a table
Write a function
decodeText :: Table -> Code -> String
such that
decodeText t (encodeText t s) = s
for every s :: String and t :: Table. We will only test strings with capital letters, digits and spaces.
For instance, we should have:
decodeText morseTable (encodeText morseTable “THIS IS A TEST”) = “THIS IS A TEST”
HINT: You may find it helpful to use your general function split discussed above.
Exercise 3: Decode using a tree
We can also store tables as trees where a left branch is a dit and a right branch is a dah. For Morse code, we would get the following tree.
[]
Here is the type of such trees.
data Tree = Empty
| Branch (Maybe Char) Tree Tree
deriving (Show , Eq)
Write a function
decodeTextWithTree :: Tree -> Code -> String
that decodes using a tree such as the above.
This function should work with ANY such tree, not just the tree pictured above.
For testing purposes, here is the tree above in Haskell:
let morseTree = Branch Nothing (Branch (Just ‘E’) (Branch (Just ‘I’) (Branch (Just ‘S’) (Branch (Just ‘H’) (Branch (Just ‘5’) Empty Empty) (Branch (Just ‘4’) Empty Empty)) (Branch (Just ‘V’) Empty (Branch (Just ‘3’) Empty Empty))) (Branch (Just ‘U’) (Branch (Just ‘F’) Empty Empty) (Branch Nothing Empty (Branch (Just ‘2’) Empty Empty)))) (Branch (Just ‘A’) (Branch (Just ‘R’) (Branch (Just ‘L’) Empty Empty) Empty) (Branch (Just ‘W’) (Branch (Just ‘P’) Empty Empty) (Branch (Just ‘J’) Empty (Branch (Just ‘1’) Empty Empty))))) (Branch (Just ‘T’) (Branch (Just ‘N’) (Branch (Just ‘D’) (Branch (Just ‘B’) (Branch (Just ‘6’) Empty Empty) Empty) (Branch (Just ‘X’) Empty Empty)) (Branch (Just ‘K’) (Branch (Just ‘C’) Empty Empty) (Branch (Just ‘Y’) Empty Empty))) (Branch (Just ‘M’) (Branch (Just ‘G’) (Branch (Just ‘Z’) (Branch (Just ‘7’) Empty Empty) Empty) (Branch (Just ‘Q’) Empty Empty)) (Branch (Just ‘O’) (Branch Nothing (Branch (Just ‘8’) Empty Empty) Empty) (Branch Nothing (Branch (Just ‘9’) Empty Empty) (Branch (Just ‘0’) Empty Empty)))))
Your function decodeTextWithTree should satisfy for instance:
decodeTextWithTree morseTree (encodeText morseTable “THIS IS ANOTHER TEST”) = “THIS IS ANOTHER TEST”
Exercise 4: Translating a table to a tree
Write a function
ramify :: Table -> Tree
that translates a given Table into a Tree. For example ramify morseTable should give the tree pictured above, i.e.
ramify morseTable = Branch Nothing (Branch (Just ‘E’) (Branch (Just ‘I’) (Branch (Just ‘S’) (Branch (Just ‘H’) (Branch (Just ‘5’) Empty Empty) (Branch (Just ‘4’) Empty Empty)) (Branch (Just ‘V’) Empty (Branch (Just ‘3’) Empty Empty))) (Branch (Just ‘U’) (Branch (Just ‘F’) Empty Empty) (Branch Nothing Empty (Branch (Just ‘2’) Empty Empty)))) (Branch (Just ‘A’) (Branch (Just ‘R’) (Branch (Just ‘L’) Empty Empty) Empty) (Branch (Just ‘W’) (Branch (Just ‘P’) Empty Empty) (Branch (Just ‘J’) Empty (Branch (Just ‘1’) Empty Empty))))) (Branch (Just ‘T’) (Branch (Just ‘N’) (Branch (Just ‘D’) (Branch (Just ‘B’) (Branch (Just ‘6’) Empty Empty) Empty) (Branch (Just ‘X’) Empty Empty)) (Branch (Just ‘K’) (Branch (Just ‘C’) Empty Empty) (Branch (Just ‘Y’) Empty Empty))) (Branch (Just ‘M’) (Branch (Just ‘G’) (Branch (Just ‘Z’) (Branch (Just ‘7’) Empty Empty) Empty) (Branch (Just ‘Q’) Empty Empty)) (Branch (Just ‘O’) (Branch Nothing (Branch (Just ‘8’) Empty Empty) Empty) (Branch Nothing (Branch (Just ‘9’) Empty Empty) (Branch (Just ‘0’) Empty Empty)))))
Exercise 5: Tabulating a tree
Write a function
tabulate :: Tree -> Table
that does the opposite. That is, it should satisfy:
ramify (tabulate t) = t
for every t :: Tree.
(Note that this establishes Tree as a retract of Table. The types are _not_ isomorphic, because, in general, tabulate (ramify t) may be only a _permutation_ of the table t.)
Exercise 6: Well-bracketed strings (hard):
Consider the following type of “bracket trees” with constructors Round :: [Bracket] -> Bracket and Curly :: [Bracket] -> Bracket:
data Bracket = Round [Bracket] | Curly [Bracket] deriving (Show,Eq)
The simplest trees we can construct are Round [] and Curly []. Other examples of such trees are Round [Curly [] , Round []] and Round [Curly [] , Round [] , Curly [ Round [] ]].
We can convert bracket trees to strings:
brackets :: Bracket -> String
brackets (Round ts) = “(” ++ concat [brackets t | t <- ts] ++ ")"
brackets (Curly ts) = "{" ++ concat [brackets t | t <- ts] ++ "}"
Write a partial inverse
tree :: String -> Maybe Bracket
of the function brackets satisfying the following specification.
For any bracket tree t, we should have that
– the equation tree (brackets t) = Just t holds,
and we should have that for any string xs,
– the equation tree xs = Nothing holds precisely when xs is _not_ well-bracketed.
Well-bracketed strings are defined by the following two generating rules:
– Any string starting with ‘(’ followed by zero or more well-bracketed strings and ending with ‘)’ is well bracketed.
– Any string starting with ‘{’ followed by zero or more well-bracketed strings and ending with ‘}’ is well bracketed.
(This is a so-called inductive definition in the sense you learned in your first year at university.)
It is a fact that bracket trees generate only well bracketed strings, using the function brackets, and, moreover, every well-bracketed string arises from some bracket tree in this way.
Examples:
– () is well bracketed
– {} is well bracketed
– ({}) is well bracketed
– {()()} is well bracketed
– “(()(){()()})” is well bracketed
– “(((){}){}(()()))” is well bracketed
– “(()” is not
– “())” is not
– “(()(()()” is not
– “(}” is not
– “({)}” is not
– “(cat)” is not
Then we can use the function tree to check whether an expression is well bracketed:
isWellBracketed :: String -> Bool
isWellBracketed xs = case tree xs of
Nothing -> False
Just _ -> True
You can use this function for testing. You can also test by creating well-bracketed strings xsand checking whether
brackets (fromJust (tree xs)) = xs
where fromJust is in the import Data.Maybe.
Exercise 7: Continued fractions (rather hard)
Introduction
A nice way of representing real numbers is to use _continued fractions_: a possibly infinite arithmetic expression that looks like:
1
a₀ + —————
1
a₁ + ———-
1
a₂ + —–
.
.
.
In this exercise, your goal is to implement a _language of continued fractions_ in Haskell. In the end, your little language will allow you to easily write down well-known real numbers such as e or π!
Arithmetic expressions
Let’s first start by writing down a simple algebraic datatype for a subset of arithmetic _expressions_ we need to express continued fractions.
data Expr = Lit Integer
| OneOver Expr
| Expr :+: Expr
deriving (Show)
First, notice that this is quite similar to various tree types you’ve seen in the lectures. For instance, you could write down the expression
(1 + 2) + (1 / (5 + (1 / 3)))
as an inhabitant of this type as follows:
(+)
/ \
/ \
(+) \
/ \ (/)
/ \ / \
1 2 1 \
(+)
/ \
5 (/)
/ \
1 3
EXERCISE (WARM-UP). Write down this tree as a term exprExample :: Expr.
Simplifying expressions
As you have probably noticed, these expressions start to get complicated very quickly which brings us to the first task of this exercise: simplifying these expressions. First, let’s define the type of fractions in Haskell as:
data Frac = Integer :/: Integer
EXERCISE. Implement the following function
simplify :: Expr -> Frac
Test your function on the example you wrote. simplify exprExample should give you 51 :/: 16.
Expressing continued fractions
The next task is to use this type of arithmetic expressions to implement continued fractions.
EXERCISE. Implement a function cf (standing for Continued Fraction):
cf :: Integer -> [Integer] -> Expr
such that a₀ `cf` [a₁, a₂, …] denotes the fraction
1
a₀ + —————
1
a₁ + ———–
1
a₂ + —–
.
.
.
After you’ve done this, check that your implementation is correct by testing it on some finite lists. For instance, you should be able to represent the fraction 23 :/: 16 as 1 `cf` [2, 3, 2]. Evaluating this should give you:
Lit 1 :+: OneOver (Lit 2 :+: OneOver (Lit 3 :+: OneOver (Lit 2)))
and simplifying should yield 23 :/: 16. Similarly, test that you can represent 13 :/: 9 as 1 `cf` [2, 3, 1].
Infinite continued fractions
We will now look at continued fractions x `cf` xs where the list xs is _infinite_.
EXERCISE. Implement a function
infFrac :: Integer -> [Integer] -> Int -> Expr
such that infFrac n [m₁, m₂, …] k gives you the expression denoting the continued fraction n `cf` [m₁, … mₖ]. _Hint_: this definition should be very easy if you use the right functions from the prelude.
Computing the constant e
The constant e can be written down as the following fraction 2 `cf` eseq where eseq denotes the following sequence of digits
1 : 2 : 1 : 1 : 4 : 1 : 1 : 6 : 1 : · · · : 1 : 2x : 1 : · · ·
EXERCISE. Write down this sequence as a Haskell list:
eseq :: [Integer]
Once you have completed this task, you should be able to write the following function that will compute better and better approximations of e depending on the provided argument
eApproximate :: Int -> Frac
Then map eApproximate [0, 1, 2] should give you 2 :/: 1, 3 :/: 1, and 8 :/: 3. and eApproximate 10 should give you 2721 :/: 1001.
Now, let us look at these as floats:
compute :: Frac -> Double
compute (m :/: n) = (fromIntegral m) / (fromIntegral n)
Running
> map (compute . eApproximate) [0, 1, 2, 10, 50]
in ghci gives
[2.0,3.0,2.6666666666666665,2.7182817182817183,2.718281828459045]
As you can see, we start to get a pretty accurate approximation even after just ten steps.