Assessed Assignment 2
Marking table
The exercises are defined so that it is hard to get a first-class mark.
1st class – 70 marks and above.
upper 2nd – 60-69 marks.
lower 2nd – 50-59 marks.
third class – 40-49 marks.
fail – 0-39 marks.
Question Difficulty
All questions have equal weight, but they are designed to increase in difficulty. We have
indicated an approximate difficulty level with the symbols according to the following
scheme:
• – Normal
• – Challenging
• – Very challenging
In particular, note that Exercises 4 and 5 are meant to be quite challenging, and that this has
been done on purpose in view of the marking table described above.
Preparation
• Do not modify the files Types.hs and Assessed2-Template.hs.
• Copy the file Assessed2-Template.hs to a new file called Assessed2.hs and write
your solutions in Assessed2.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.
If you do make changes, then we will not be able to mark your submission and
hence it will receive zero marks!
• Solve the exercises below in the file Assessed2.hs.
Submissions should compile and run correctly on Jupyter
Notebook
If your submission doesn’t compile or run correctly on Jupyter Notebook, it will get zero
marks.
Submission procedure
• Run the presubmit script to be provided to you on your submission from Jupyter by
running ./presubmit.sh Assessed2 in the terminal (in the same folder as your
submission).
• This will check that your submission is in the correct format.
• If it is, submit on Canvas.
• Otherwise fix and repeat the presubmission procedure.
Plagiarism
Plagiarism will not be tolerated. Copying and contract cheating has led to full loss of marks,
and even module or degree failure, in the past.
You will need to sign a declaration on Canvas, before submission, that you understand the
rules and are abiding by them, in order for your submission to qualify.
Background material
• Each question has some Background Material, an Implementation Task and some
Examples.
• Read this material first, then implement the requested function.
• The corresponding type appears in the file Assessed2Template.hs (to be copied by
you).
• Replace the default function implementation of undefined with your own function.
Exercise 1 – Applying Functions to Trees
Background Material
There are many possible variants of the type of binary trees introduced in the Lecture Notes.
For example, consider the following definition:
data Tree a b = Leaf b | Fork (Tree a b) a (Tree a b)
deriving (Eq, Show)
Notice how now, the tree stores two different types of data: an element of type a at each fork
and an element of type b at each leaf.
Implementation Task
Your task is to write a higher-order function applyfuns that takes two functions f :: a ->
c and g :: b -> d, as well as an element of type Tree a b as input and applies the first
function to the values found at the forks, and the second function to the values found at the
leaves. That is, implement the function:
applyfuns :: (a -> c) -> (b -> d) -> Tree a b -> Tree c d
applyfuns = undefined
Examples
file://///mhe/fp-learning-2021-2022/-/blob/main/plagiarism
Lets consider the following two functions:
str2int :: String -> Int
str2int xs = length xs
int2bool :: Int -> Bool
int2bool n = n /= 0
and the following binary tree:
“John”
/ \
/ \
“Oliver” “Benjamin”
/ \ / \
/ \ / \
2 4 0 6
Then the expression applyfuns str2int int2bool should return the tree
4
/ \
/ \
6 8
/ \ / \
/ \ / \
True True False True
*Main> applyfuns str2int int2bool (Fork (Fork (Leaf 2) “Oliver” (Leaf 4))
“John” (Fork (Leaf 0) “Benjamin” (Leaf 6)))
Fork (Fork (Leaf True) 6 (Leaf True)) 4 (Fork (Leaf False) 8 (Leaf True))
As a second example, the tree
“New York”
/ \
/ \
“Paris” “Dubai”
/ \ / \
/ \ / \
“London” 14 5 “Shanghai”
/ \ / \
/ \ / \
0 10 0 21
is transformed into the tree
8
/ \
/ \
5 5
/ \ / \
/ \ / \
6 True True 8
/ \ / \
/ \ / \
False True False True
*Main> applyfuns str2int int2bool (Fork (Fork (Fork (Leaf 0) “London” (Leaf
10)) “Paris” (Leaf 14)) “New York” (Fork (Leaf 5) “Dubai” (Fork (Leaf 0)
“Shanghai” (Leaf 21))))
Fork (Fork (Fork (Leaf False) 6 (Leaf True)) 5 (Leaf True)) 8 (Fork (Leaf
True) 5 (Fork (Leaf False) 8 (Leaf True)))
Exercise 2 – Updating Nodes Along a Route
Background Material
In this exercise, we return to a version of binary trees which stores data only at the nodes. We
will use the following definition:
data BinTree a = Empty | Node (BinTree a) a (BinTree a)
deriving (Eq, Show)
Next, we define a type Route which will describe the “route” one must take to arrive at a
particular node in one of our trees.
data Direction = GoLeft | GoRight
deriving (Eq, Show, Bounded, Enum)
type Route = [Direction]
So a route is a list of directions, which tell you whether to go left or right, starting from the
root of the binary tree. For example,
1. The route to the root of any binary tree is [] :: Route.
2. In the tree Node (Node Empty ‘b’ Empty) ‘a’ (Node (Node Empty ‘d’ Empty)
‘c’ (Node Empty ‘e’ Empty)), pictured below, the route [GoLeft] takes you to
the node with value ‘b’, while the routes to the nodes with values ‘d’ and ‘e’ are
[GoRight,GoLeft] and [GoRight,GoRight] respectively.
3. ‘a’
4. / \
5. / \
6. ‘b’ ‘c’
7. / \
8. / \
‘d’ ‘e’
Implementation Task
Your task is to implement the function
updateNodes :: Route -> (a -> a) -> BinTree a -> BinTree a
updateNodes = undefined
such that updateNodes r f t applies f to the values of all nodes along the route r in the
tree t.
NB:
1. If you run out of directions before hitting a leaf, e.g. if running updateNodes on the
route [GoRight] in the tree above, then you stop and do not modify the remainder of
the tree (the values ‘d’ and ‘e’ in the example).
2. If the route is too long, e.g. if running updateNodes on the route [GoLeft,GoLeft]
in the tree above, then you discard the remainder of the route (so in the example, you
would only update the values ‘a’ and ‘b’ and then stop).
The examples given below should also help to clarify these points.
Examples
For the following binary tree:
1
/ \
2 \
/ \ 99
/ \ \
3 4 \
100
*Main> let t = Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 1
(Node Empty 99 (Node Empty 100 Empty))
*Main> updateNodes [] (*8) t
Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 8 (Node Empty 99
(Node Empty 100 Empty))
*Main> updateNodes [GoRight] (*8) t
Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 8 (Node Empty 792
(Node Empty 100 Empty))
*Main> updateNodes [GoRight,GoLeft] (*8) t
Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 8 (Node Empty 792
(Node Empty 100 Empty))
*Main> updateNodes [GoRight,GoRight] (*8) t
Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 8 (Node Empty 792
(Node Empty 800 Empty))
*Main> updateNodes [GoRight,GoRight,GoLeft] (*8) t
Node (Node (Node Empty 3 Empty) 2 (Node Empty 4 Empty)) 8 (Node Empty 792
(Node Empty 800 Empty))
*Main> updateNodes [GoLeft,GoLeft,GoLeft] (*15) t
Node (Node (Node Empty 45 Empty) 30 (Node Empty 4 Empty)) 15 (Node Empty 99
(Node Empty 100 Empty))
NB: Remember that we are not storing the results of running updateNodes above, so all
examples above are run on the same tree t = Node (Node (Node Empty 3 Empty) 2
(Node Empty 4 Empty)) 1 (Node Empty 99 (Node Empty 100 Empty)).
Exercise 3 – Grafting Subtrees
Background Material
The type of rose trees is defined as
data Rose = Br [ Rose ] deriving (Show, Eq)
Compared with the binary trees we have seen before, that main difference is that each branch
point may now store an arbitray number of child branches. Moreover, there is no need for a
base case since a leaf of the tree can be represented by a branch with an empty list of
descendants: Br [].
Implementation Task
Write a function
graft :: Rose -> [ Rose ] -> (Rose , [ Rose ])
graft = undefined
which takes a “parent” tree and a list of “child” trees and grafts each of the children to the
leaves of the parent as we move from left to right.
Notice how the function returns two pieces of data: the grafted tree as well as a list. This
second value can be used if the length of the list of children does not match the number of
leaves of the parent. For example, if there are not enough child trees in the list, your function
should simply continue without modifying the remaining leaves and and return the grafted
tree as well as the empty list. Conversely, if there are more children than there are leaves of
the parent, then your function should return the grafted tree as well as the list of child trees
which are left over.
Examples
If this is the parent tree
and the children are given by the list of four trees
then your function should return the following grafted tree
as well as the list of remaining trees. In this case, since the parent tree has 3 leaves and 4
children were provided, there is a single tree left over. So the second return value is a list of
length one containing the last child:
In code, this examples looks as follows:
*Main> parent
Br [Br [Br [],Br []],Br [Br []]]
*Main> children
file:///mhe/fp-learning-2021-2022/-/raw/main/Assignments/2/assets/tree1.svg
file:///mhe/fp-learning-2021-2022/-/raw/main/Assignments/2/assets/tree_args.svg
file:///mhe/fp-learning-2021-2022/-/raw/main/Assignments/2/assets/tree_result.svg
file:///mhe/fp-learning-2021-2022/-/raw/main/Assignments/2/assets/tree_rem.svg
[Br [Br [],Br []],Br [],Br [Br [Br []]],Br [Br [],Br [],Br []]]
*Main> graft parent children
(Br [Br [Br [Br [],Br []],Br []],Br [Br [Br [Br []]]]],[Br [Br [],Br [],Br
[]]])
Exercise 4 – Conjunctive Normal Form
Background Material
One common use of data types in Haskell is to model the expressions in a formal language.
For example, the following data type captures the syntax of logical expression:
data Expr = Var String — Variable
| Not Expr — Logical negation
| Conj Expr Expr — Conjunction
| Disj Expr Expr — Disjunction
| Implies Expr Expr — Implication
deriving (Eq, Show)
Using this type, we can write, for example, the logical law ((p ∨ q) → r) → ((p → r) ∧
(q → r)) as
example0 :: Expr
example0 =
((p `Disj` q) `Implies` r) `Implies` ((p `Implies` r) `Conj` (q `Implies`
r))
where
p, q, r :: Expr
p = Var “p”
q = Var “q”
r = Var “r”
In this exercise we will work on rewriting such expressions so that they are in conjunctive
normal form. Informally, a logical expression is said to be in conjunctive normal form if it is
a conjunction of disjunctions of literals, where a literal is either a variable or the negation of a
variable. Now, let us express this formally:
• A formula is a literal if it is either a variable or the negation of a variable.
• A formula is a clause if it is either a literal or is the disjunction of two clauses.
• Finally, a formula is in CNF if it is either a clause or is the conjunction of two CNF
expressions.
We could also express this as a context-free grammar:
x ::= “p” | “q” | “r” | ···
Literal ::= x | ¬ x
Clause ::= Literal | Clause ∨ Clause
CNF ::= Clause | CNF ∧ CNF
Note also that this definition of CNF means implication should not occur in a CNF formula.
Implementation Tasks
https://en.wikipedia.org/wiki/Conjunctive_normal_form
https://en.wikipedia.org/wiki/Conjunctive_normal_form
Your goal in this exercise is to implement a Haskell function
toCNF :: Expr -> Expr
toCNF = undefined
which takes an arbitrary expression and returns an equivalent expression which is in
conjunctive normal form. We’ll separate this task into several steps.
Task 1. As a first step, write a function elimImplications which removes all occurrences
of an implication p ⇒ q in a logical expression and replaces it with the equivalent expression
¬p ∨ q.
elimImplications :: Expr -> Expr
elimImplications = undefined
Task 2. To make things a bit easier later on, the next task will be to implement a function
which checks whether a given expression is in CNF. To this end, write a function
isInCNF :: Expr -> Bool
isInCNF = undefined
such that isInCNF e is True if and only if e is a CNF formula as specified by the context-
free grammar above.
Test your function with various expressions to make sure that it is working correctly. Once
you’ve got this right, it should make it easy for you to check that your toCNF implementation
is correct.
Task 3. Finally, implement toCNF such that toCNF e returns an expression which is
equivalent to e but is in CNF. You will have to apply three transformations:
1. Getting rid of implications (implemented in Task 1),
2. Simplifying multiple negations (that is, rewriting ¬ (¬ p) to p)
3. Using the de Morgan laws to push negations towards the leaves (that is, rewriting ¬
(A ∨ B) to ¬ A ∧ ¬ B and ¬ (A ∧ B) to ¬ A ∨ ¬ B)
4. Using the distributivity of disjunction over conjunction to push disjunctions inside
conjunctions (that is, rewriting A ∨ (B ∧ C) to (A ∨ B) ∧ (A ∨ C) and (A ∧ B) ∨
C to (A ∨ C) ∧ (B ∨ C))
How you break up the problem into these steps is up to you. However, we suggest
implementing a function for each transformation and testing each one separately.
Examples
Let us define the following expressions:
— ¬ (B ∨ C)
example1 :: Expr
example1 = Not (Disj (Var “B”) (Var “C”))
— (A ∧ B) ∨ C
example2 :: Expr
example2 = Disj (Conj (Var “A”) (Var “B”)) (Var “C”)
— A ∧ (B ∨ (D ∧ E))
example3 :: Expr
example3 = Conj (Var “A”) (Disj (Var “B”) (Conj (Var “D”) (Var “E”)))
— ¬ (A ⇒ B) ∨ C
example4 :: Expr
example4 = Disj (Not (Implies (Var “A”) (Var “B”))) (Var “C”)
These give the following results when passed to our algorithm:
*Main> toCNF example1
Conj (Not (Var “B”)) (Not (Var “C”))
*Main> toCNF example2
Conj (Disj (Var “A”) (Var “C”)) (Disj (Var “B”) (Var “C”))
*Main> toCNF example3
Conj (Var “A”) (Conj (Disj (Var “B”) (Var “D”)) (Disj (Var “B”) (Var “E”)))
*Main> toCNF example4
Conj (Disj (Var “A”) (Var “C”)) (Disj (Not (Var “B”)) (Var “C”))
Exercise 5 – An Isomorphism of Tree Types
Background Material
We have now seen two seemingly very different kinds of trees: binary trees in which each
branch has exactly two descendants, and rose trees in which each Branch can have an
arbitrary number. In this exercise, we will work with simplified versions of each of these
types which do not carry any data at all. The relevant definitions are:
data Rose = Br [ Rose ]
deriving (Eq, Show)
data Bin = Root | Branch Bin Bin
deriving (Eq, Show)
But in fact, it turns out that these two types are actually isomorphic!
Implementation Task
Write functions
binToRose :: Bin -> Rose
binToRose = undefined
and
roseToBin :: Rose -> Bin
roseToBin = undefined
which implement an isomorphism between these two different types of trees. Recall that this
means that for all r :: Rose and b :: Bin, these functions should satisfy the equations
binToRose (roseToBin r) == r
roseToBin (binToRose b) == b
Examples
There is not a unique solution to this problem: there are in principle many isomorphisms
between these two types, though some will be easier to implement than others. Consequently
there is not any reasonable way to provide examples.
Instead, let us say a couple more words about what you are being asked to do. In order to
implement such an isomorphism, you need to figure out a way to encode every binary tree as
a rose tree (this is the job of the binToRose function). Moreover, this encoding should be
such that the tree can late be decoded (by the roseToBin function) back to the original binary
tree you started with.
Assessed Assignment 2
Marking table
Question Difficulty
Preparation
Submissions should compile and run correctly on Jupyter Notebook
Submission procedure
Plagiarism
Background material
🌶 Exercise 1 – Applying Functions to Trees
Background Material
Implementation Task
Examples
🌶 Exercise 2 – Updating Nodes Along a Route
Background Material
Implementation Task
Examples
🌶🌶 Exercise 3 – Grafting Subtrees
Background Material
Implementation Task
Examples
🌶🌶🌶 Exercise 4 – Conjunctive Normal Form
Background Material
Implementation Tasks
Examples
🌶🌶🌶 Exercise 5 – An Isomorphism of Tree Types
Background Material
Implementation Task
Examples