Description
– You **may** consult any course material (lecture notes, assignments, past exams, etc)
– You **may** ask for clarifications on Piazza via a private message to instructors
– You **may not** communicate with other students or ask for anyone’s help
– You **may not** search help forums (StackOverflow) and the Internet for a solution
Overview
The exam is in the files:
– [BHeap.hs](./src/BHeap.hs)
– [tests/Test.hs](./tests/Test.hs)
As before `Test.hs` has some sample tests, and testing code that
you can use to check your solution before submitting.
Testing and Evaluation
Most of the points, will be awarded automatically, by
**evaluating your functions against a given test suite**.
[Tests.hs](./tests/Test.hs) contains a very small suite
of tests which gives you a flavor of of these tests.
When you run
“`shell
$ make test
“`
Your last lines should have
“`
All N tests passed (…)
“`
**or**
“`
K out of N tests failed
“`
**If your output does not have one of the above your code will receive a zero**
If for some problem, you cannot get the code to compile,
leave it as is with the `error …` with your partial
solution enclosed below as a comment.
The other lines will give you a readout for each test.
You are encouraged to try to understand the testing code,
but you will not be graded on this.
Submission Instructions
Submit your code via the `final` assignment on Gradescope.
You must submit a single zip file containing a single directory with your repository inside.
A simple way to create this zip file is:
– Run `git push` to push your local changes to your private fork of the assignment repository
– Navigate to your private fork on github and download source code as a zip
Please *do not* include the `.stack-work` or the `_MACOSX` folder into the submission.
Upon submission to Gradescope, the auto-grader will only test your code on the public test suite,
so you can get no more than 48 points.
After the deadline, we will re-test your code on the private test suite.
Q1: Binary Heaps (50pts)
Recall that as part of the midterm we implemented the `insert` function
that inserts a new key into a binary heap.
While traversing the tree, this function must check for each node and its left child,
whether they are *full*
(i.e. whether all of their levels are completely filled).
For this purpose we used a recursive function `isFull`,
which, again, traverses the whole tree.
This makes our insertion function inefficient.
To eliminate the inefficiency, we will modify the `BHeap` datatype slightly:
in each internal node, we will store a boolean flag
that indicates whether this subtree is full:
“`haskell
data BHeap
= Leaf — ^ Empty tree
| Node Int Bool BHeap BHeap — ^ Node with a value, whether this tree is full,
— ^ and left and right subtree
“`
Now we can implement `isFull` in constant time like so:
“`haskell
— | Is this binary tree full according to the cached value?
isFull :: BHeap -> Bool
isFull Leaf = True
isFull (Node _ full _ _) = full
“`
We can use this version of `isFull` to implement efficient insertion.
But the price to pay is that insertion has to properly adjust the fullness flags
of the nodes it creates.
The [midterm](https://drive.google.com/file/d/18gX__xGuQVKS9JUxYMIBgByhJiN-egAa/view?usp=sharing)
contains definitions of the various properties that define a well-formed binary heap.
1.1. Efficient insertion [15 pts]
Fill in the definition of `insert` that inserts a new key into a binary heap.
You can *assume* that the input heap is valid,
i.e. satisfies the shape property, the value property,
and all of its fullness flags are accurate.
You must *guarantee* that the output heap is also valid.
Your implementation must satisfy the following test cases:
“`haskell
λ> insert 11 Leaf
Node 11 True Leaf Leaf
λ> insert 5 (Node 11 True (Node 3 True Leaf Leaf) (Node 8 True Leaf Leaf))
Node 11 False (Node 5 False (Node 3 True Leaf Leaf) Leaf) (Node 8 True Leaf Leaf)
“`
Feel free to refer to the midterm [master solution](https://drive.google.com/file/d/1taxKiDYZYPL0OxNy9jH7h2rj83PnetXq/view?usp=sharing) for the implementation of `insert` without fullness flags.
1.2. Build with HOF [5 pts]
Fill in the definition of `build` that converts the input `[Int]`
into a `BHeap` by inserting all list elements into an empty heap.
**You may not** use recursion; **you must** use higher-order functions instead.
The order in which you add elements is irrelevant.
Property-based testing
Now we want to use QuickCheck to test whether we implemented `insert` and `build` correctly.
In particular, we want to test the following properties:
1. `prop_full_correct`: if we create a heap with `build`, it has its fullness flag set correctly
2. `prop_is_heap_shape`: if we create a heap with `build`, it satisfies the shape property
3. `prop_is_heap_value`: if we create a heap with `build`, it satisfies the value property
4. `prop_contains_elts`: a heap created with `build xs` contains all the elements of `xs`
We have implemented property 1 for you,
so if you have implemented `insert` and `build` correctly,
you should see the following output in `ghci` after loading `BHeap`:
“`haskell
λ> quickCheck prop_full_correct
+++ OK, passed 100 tests.
“`
The other three properties require you to implement
some helper functions.
Again, the [midterm](https://drive.google.com/file/d/18gX__xGuQVKS9JUxYMIBgByhJiN-egAa/view?usp=sharing)
contains definitions of the various properties that we will validate via QuickCheck.
1.3. Checking the shape property [10 pts]
Fill in the definition of `isHeapShape`
that takes as input a binary tree
and determines whether it satisfies the heap shape property.
(Note that the input tree might not be a valid binary heap,
and in particular, its fullness flags might be invalid.)
Your implementation must satisfy the following test cases:
“`haskell
λ> isHeapShape (Node 11 True (Node 3 True Leaf Leaf) (Node 8 True Leaf Leaf))
True
λ> isHeapShape (Node 11 True Leaf (Node 8 True Leaf Leaf))
False
“`
After this step, you should see the following output:
“`haskell
λ> quickCheck prop_is_heap_shape
+++ OK, passed 100 tests.
“`
1.4. Checking the value property [10 pts]
Fill in the definition of `isHeapValue`
that takes as input a binary tree
and determines whether it satisfies the heap value property.
(Note that the input tree might not be a valid binary heap,
and in particular, its fullness flags might be invalid.)
Your implementation must satisfy the following test cases:
“`haskell
λ> isHeapValue (Node 11 True (Node 3 True Leaf Leaf) (Node 8 True Leaf Leaf))
True
λ> isHeapValue (Node 11 True (Node 15 True Leaf Leaf) (Node 8 True Leaf Leaf))
False
“`
After this step, you should see the following output:
“`haskell
λ> quickCheck prop_is_heap_value
+++ OK, passed 100 tests.
“`
1.5. Checking the elements property with HOF [10 pts]
Fill in the definition of `containsAll`
that takes as input a list and a (valid) binary heap
and determines whether all list elements are present in the heap.
**You may not** use recursion; **you must** use higher-order functions instead.
However, you should use the provided function `contains`
to check the presence of individual values.
Your implementation must satisfy the following test cases:
“`haskell
λ> containsAll [3, 8, 11] (Node 11 True (Node 3 True Leaf Leaf) (Node 8 True Leaf Leaf))
True
λ> containsAll [3, 5, 11] (Node 11 True (Node 3 True Leaf Leaf) (Node 8 True Leaf Leaf))
False
“`
After this step, you should see the following output:
“`haskell
λ> quickCheck prop_contains_elts
+++ OK, passed 100 tests.
“`
