Final (Pt 1) [50 points]

- 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.
```