Data Structures and Functional Programming CS 3110, Fall 2013 Version: 6
Problem Set 4 Due at 11:59 PM, Thursday, October 17 Last Modiﬁed: October 22, 2013
All code you submit must compile. Programs that do not compile will be heavily penalized. If your submission does not compile, we will notify you immediately. You will have 48 hours after the submission date to supply us with a patch. If you do not submit a patch, or if your patched code does not compile, you will receive an automatic zero.
We will be using an automatic grading script, so it is crucial that you name your functions and order their arguments according to the problem set ...view middle of the document...
The GUI for this problem set requires some additional OCaml libraries; the ﬁle README.txt in the release contains instructions for compiling and running the project. 1
In many applications, users want to rearrange a collection of geometric shapes while keeping them from overlapping with each other. For example, users like to rearrange windows on their desktops while keeping each window entirely visible. Without an automated way to keep them from overlapping, users must carefully adjust the boundaries of the windows if they want to avoid large gaps between the windows. The same user interface feature is useful in other applications, such as computer aided design, graphics applications, and games. In this assignment, you will be building a library that allows users to drag and drop shapes while keeping them from intersecting each other. You will use the library to build a simple “tangrams” game. The correctness of geometric algorithms depends on the properties of the numbers used to represent the coordinates of the shapes. You will implement a variety of number types to investigate the tradeoffs of various representations. Finally, this assignment contains a small problem related to mutability.
Part One: Numbers
For this portion of the assignment, you will implement a variety of modules, each deﬁning a representation of a set of numbers and the operations available for those numbers. Your number modules will each implement one of the following interfaces (we have provided these signatures in numbers.ml): • A Quotient represents a set of elements, which we will refer to as numbers. The only operation provided by Quotient is the (===) function, which deﬁnes the notion of equality for the set of numbers. • Just as Quotient deﬁnes a notion of equality between numbers, Group deﬁnes a notion of addition. In addition to the (+) operation, Group requires a number called zero, and for each number x, an additive inverse -x . Note that OCaml writes the negation operation as (~-). That is, (~-) x is the same as -x. • Ring extends Group by adding a notion of multiplication. It also requires a multiplicative identity called one. • A Field is a ring where every number x has a multiplicative inverse x −1 . This allows us to deﬁne division: x/y is just x y −1 . • OrderedRing and OrderedField add a notion of ordering to rings and ﬁelds respectively. We only require implementors to provide a function that determines if a number is negative, but comparison operations like () can be deﬁned in terms of is_non_neg (you will do this in exercise 2 below). • NiceRing and NiceField require additional useful functions: the ability to convert a number to an OCaml float, and a function for printing a number onto the console. You can 2
register these formatting functions with the OCaml toplevel using the #install_printer command; this will cause the toplevel to use that function to print out values of your number type. See the toplevel documentation...