Skip to content

DETAILS.md

Latest commit

 

History

History
349 lines (279 loc) · 16.3 KB

DETAILS.md

File metadata and controls

349 lines (279 loc) · 16.3 KB

Assignment 2

Marking & Solutions

Assignment 2 solutions have now been released, which you can find here. As usual, you are encouraged to look at the solutions to see how they work.

We have also provided the marking scripts for you to see where your marks have come from and to get feedback on each function. To run the marking, you should do the following:

  • Do a git pull from the terminal in the fp-learning-2025 folder on vLab - this will update your repo on vLab to have the updated files.
  • Navigate to the Assignment 2 folder - this is where the marking script should be run.
  • Here, you should have your assignment file; ensure this file is called Assignment2.hs.
  • In the same folder, in the terminal (not in ghci), run the following command: echo 'main' | stack repl; this will download the dependencies and run the marking automatically for you.
  • The marking scripts print out the tests individually, accompanied with whether your attempt passes/failed the test, and if you pass, how many marks you get. After all the tests have been run, it then tells you your overall score for this assignment.

Assignment 2

To solve the assignment, please copy the file Assignment2-Template.hs to a new file called Assignment2.hs and write your solutions in Assignment2.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.

Run the pre-submit script to check for any (compilation) errors before submitting by running in the vLab terminal:

$ ./presubmit.sh Assignment2

If this fails, you are not ready to submit, and any submission that doesn't pass the presubmit test on vLab is not eligible for marking.

Submit your file Assignment2.hs via Canvas.

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.

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 :: Code
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. This is because dit and dah each end in a Silence by definition.

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 1: Encode using a table (18 marks)

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:

    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 (16 marks)

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 (16 marks)

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 (16 marks)

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 (16 marks)

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) (18 marks)

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.

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
  • "" 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.