Description
The work we’ll do for this lab is based on material we’ve seen in
Chris Okasaki’s book “Purely Functional Data Structures” – referred to
as PFDS below. Some material also comes from the S8.1 slides we’ve
been using in class.
Our goal is to implement binomial heaps following the examples in
PFDS, but in OCaml instead of Standard ML. This work will set us up
for the last homework assignment, Homework 8.
## Getting Started
Create a “Lab_13“ directory in your GitHub repository and in that
create a file named “binomialheap.ml“.
## Ordered values
In binomial heaps, and other data structures, we need to compare
values in various ways. This idea is captures in PFDS at the top of
Figure 2.9. This is similar to the “Comparable“ signature we
developed in the interval examples from our discussion on modules.
Write a signature named “OrderedSig“ that has a type “t“ and the
three functions in Figure 2.9.
The functions in Fig 2.9 are not curried – that is, they take an
ordered pair as input. We would like ours to be curried so that the
type is “t -> t -> bool“ instead.
## Integers as ordered values
Implement a module named “Int“ that conforms to this “OrderedSig“
signature. You may need to use some of the constructs we learned in
versions 6 and 7 of the interval examples for this to work with the
functor we will define below.
## A signature for heaps
Figure 3.1 of PFDS provides a samples signature for heaps. To make
testing and experimenting with modules that satisfy this signature we
will extend it and give it the name “BinomialHeapSig“ instead of
“Heap“.
We will not make the type of the heap abstract and will will also
provide a type for the binomial trees in binomial heaps.
We will also not include a structure “Elem“ as done in Figure 3.1.
Instead we will simply have an abstract type “elem“ in the
signature.
Thus, the beginning of your “BinomialHeapSig“ signature should be
the following:
“`
module type BinomialHeapSig = sig
type elem
type tree = Node of int * elem * tree list
type t = tree list
“`
After this, provide the types for the functions Figure 3.1. Again,
our functions should be curried. So the types of “insert“ and
“merge“ should not take a pair but should instead take their
arguments one at a time. This is the same thing we did with the
functions in “OrderedSig“.
## A functor for binomial heaps
Figure 3.4 in PFDS provides a functor for binomial heaps. We will
write a similar functor, but it will match our modified signatures,
“BinomialHeapSig“, from above.
Our functor, named “BinomialHeap“ should take a module matching
signature “OrderedSig“ as it argument.
It will set “elem“ to the type defined in the argument module and
implement the “t“ and “tree“ types as in the “BinomialHeapSig“
as above.
Again, we may need to use what we learned in versions 6 or 7 of the
interval examples from our discussion of modules.
The remainder of the body of the functor should implement those
functions in Figure 3.4.
Again, these are all in Standard ML and thus need to be translated
into OCaml.
## Putting the pieces together.
Construct a module “BHI“ – for Binomial Heap of Integers – as
follows:
“`
module BHI = BinomialHeap(Int)
“`
Next, add the following to your file:
“`
let h1 = BHI.empty
let h2 = BHI.insert 20 h1
let h3 = BHI.insert 30 h2
let h4 = BHI.insert 10 h3
let h5 = BHI.insert 40 h4
let m1 = BHI.findMin h5
let h6 = BHI.deleteMin h5
let m2 = BHI.findMin h6
“`
These replay the example we did in lecture of adding the values 20,
30, 10, and 40 in succession, starting with the empty heap.
Your solution should see “m1“ evaluate to 10 and “m2“ evaluate to
20.
## What to turn in.
Commit and push your “binomialheap.ml“ file and check for the
results from the feedback tests in your GitHut repo.
