12 Homework 7B
Due:
Thursday, 2/22 at 9PM
This assignment is SOLO, and entirely AUTOGRADED.
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW7B assignment on Gradescope. This page has additional information, and allows us to format things nicely.
12.1 Invariants
Heaps are data structures that allow you to maintain elements in such a way to allow fast to access either the minimum, or maximum, element. Like many data structures, the way that they guarantee fast lookup is that they have particular invariants that must be maintained, beyond the mere structure of the underlying data. We’ve seen this idea before, in Homework 5B, where you implemented a predicate that captured the balanced binary tree invariant, but in this set of problems, you will show how you can use data abstraction to ensure such invariants cannot be violated.
12.2 Problem 1
There are many different ways to implement minheaps—
As a result, we’ll choose, as our implementation data structure, a list.
| (define-contract Heap (List Integer)) |
| (: empty-heap Heap) |
| (define empty-heap empty) |
The three operations we want to support are insert, get-min, and remove-min. They should have the following signatures, noting that we have defined a helper signature Maybe to account for the fact that the heap could be empty, so get-min may return #f instead of a number.
| (define-contract (Maybe T) (OneOf T (Constant #f))) |
| (: insert (-> Heap Integer Heap)) |
| (define (insert h n) ...) |
| (: get-min (-> Heap (Maybe Integer))) |
| (define (get-min h) ...) |
| (: remove-min (-> Heap Heap)) |
| (define (remove-min h) ...) |
In this problem, please implement these three functions. It’s important that insert is implemented in such a way that both get-min and remove-min do not have to look past the first element of the list!
12.3 Problem 2
Now, if you provided insert, get-min, and remove-min, as library functions to be used by other code, there is a potential problem. A user could call (insert (insert empty-heap 10) 20) and get back, correctly, the list (list 10 20), but then could, on their own, add 30 to the front, and pass the "heap" (list 30 10 20) to get-min, and be handed back not the minimum, but 30 instead. (Try it: does your code do something different? It shouldn’t!)
What went wrong? Well, despite the fact that we had an (important) data structure invariant in mind, and satisfied it in all of our code, we exposed the underlying data structure and as a result, users/clients of our code are able to violate the invariant.
There is one way could fix this: by defining the invariant that we want of our data structure formally. i.e., rather than just having this in our head:
a Heap should have its first element be the minimum
or maybe more precisely:
a Heap should be sorted in increasing order
We could write a predicate with the following signature:
| (: satisfies-heap-invariant? (-> Heap Boolean)) |
| (define (satisfies-heap-invariant? h) ...) |
(Do this – this is your task for Problem 2)
And then define a CheckedHeap version of the contract that checks this (note: this doesn’t provide a way to generate CheckedHeaps, so you can’t run check-contract!)
| (define-contract CheckedHeap (AllOf Heap satisfies-heap-invariant?)) |
Then you can define wrapped versions of your insert, get-min, and remove-min functions that check that the Heaps that they produce satisfy this invariant:
| (: insert-checked (-> CheckedHeap Integer CheckedHeap)) |
| (define (insert-checked h n) |
| (insert h n)) |
| (: get-min-checked (-> CheckedHeap (Maybe Integer))) |
| (define (get-min-checked h) |
| (get-min h)) |
| (: remove-min-checked (-> CheckedHeap CheckedHeap)) |
| (define (remove-min-checked h) |
| (remove-min h)) |
If, instead of providing insert, get-min, and remove-min, you provided the checked variants, then when the aforementioned (mis)user of your code tried to pass (list 30 10 20) to get-min-checked, they would get a contract error, because that wasn’t a valid CheckedHeap.
12.4 Problem 3
There’s a downside to this approach, however: we are doing a (pretty expensive) check every time we call our functions, and indeed, doing so actually negates the algorithmic guarantees! get-min can no longer just look at the front of the list, since ensuring that the input is actually a proper Heap requires looking through the whole list!
A better solution, in this case, is to restrict access entirely to the data structure, and make it so that clients/users can only interact with it via (unchecked) insert, get-min, and remove-min. Provided those were carefully written to preserve the invariant (and this could be tested using the satisfies-heap-invariant? definition).
To do that, we can provide the three functions, along with the empty-heap, inside a list of length four (so you can use Tuple).
Your task is to write an abstract signature for this, using Exists, such that the implementation type is not leaked.
| ;(: heap-library ...) |
| (define heap-library |
| (list empty-heap |
| insert |
| get-min |
| remove-min)) |