Abstraction and Modularity

In this homework, you'll be working on features for abstraction and modularity. To that end, you'll be working with generic types, as well as implementing modules for sets and lists based on interfaces we've given you.

This is the first homework where you'll be submitting multiple files:

  1. tree.ml
  2. listset.ml
  3. bstset.ml
  4. bstmap.ml
You should do the work in that order! Our tester grades in that order, plus it will be easier for you.

The work in tree.ml should be self-explanatory---it's like the earlier homework. For the other three files, we've defined an interface in the corresponding mli file. Your job is to implement the mli file's interface in the ml file. You can define as many helpers as you want in your implementation, but don't edit the mli file! Our tester relies on the interface we've given you. If you change it, your code may not compile.

We haven't given you any tests for your modules, so you should write your own---to make sure you understand the interface and to make sure your code works.

One final note: listset.mli and bstset.mli are identical on purpose---they're both set implementations! Any test you come up with for the set operations should work on both implementations.

Now download the homework and get started---good luck!