Assignment 3: Variants, records, modules, functional data structures
In this assignment, you will be writing a binary-tree-based dictionary library.
File structure and requirements
- Use this zip file as the starting point for your assignment.
- In previous assignments, we gave you an
.mli
and a skeleton of the.ml
to fill in. This time, you are given just the.mli
and only a small bit of starter code in.ml
. Your answers go in these files:src/simpledict.ml
src/simpletree.ml
test/tests.ml
- These are the only coding files you will submit, so your solution must not involve any other file.
- Most of the instructions for this assignment are in the
.mli
files. - You are given some initial tests in
test/dict_tests.ml
andtest/tree_tests.ml
. You must add at least 10 non-redundantassert_equal
statements totest/tests.ml
to cover your implementations ofSimpletree
andSimpledict
. You will be graded on adding these 10 tests.- While we provide a test for each function, what we provide is not exhaustive.
- Just a few examples of tests you might like to add are:
- Nontrivial trees with
is_ordered
andis_balanced
. - Structure preservation of
map
. - All cases of
combine
.
- Nontrivial trees with
- We have given you
dune
files which work out of the box. You may add libraries to them if you would like, but you should not need to.
Resources
Here are a few additional resources to keep in mind during this assignment.
- See the Basic Modules lecture for information on filling in the module signatures (i.e. writing the
.ml
files such that they compile along with the.mli
files). - In particular, see the set-example.zip example.
Submission and Grading
- Follow the same protocol for Gradescope submission as previous assignments.
- do a final
dune clean; dune build
from the main directory and submit the_build/default/assignment3.zip
file.
- do a final
- The submitted files include only the files you are supposed to edit, along with your
dune
files. Notably, you do not submit the provided test files or the provided.mli
files. - We will grade the style of your code. Please consult the FPSE Style Guide.
- You will also be graded on your added tests.
- You will be graded on having the correct time complexity as is written in some function descriptions. You will lose points if you have time complexity worse than is required.