Homework # 6
due Tuesday, March 9, 4:00 PM

Binary Search Trees for Sets

Do Exercise 11, and 12 (on page 179) with several changes:

1. The function makeBST should accept the comparison function first and then the list. And the tree that you create in makeBST must be as balanced as possible. You will need to sort the elements first; you may copy in the quicksort routine from the solution to Homework #4.

   Hint: write a recursive helper function maketree that takes an integer $n$ and a list and returns a (balanced) tree of the first $n$ elements of the list and the remaining elements of the list.

2. The searchBST function must not require an equality type. Instead it should use the comparison function, and assume that $\neg (x< y) \wedge \neg(y < x)$ means that $x$ and $y$ are equal.

Then use these functions to create ``set'' objects:

type 'a set = ...;
fun makeSET (comp:'a * 'a -> bool) (l:'a list) : 'a set = ...
fun SETcontains (s: 'a set) (x: 'a) : bool = ...

Your set type will need to have functions in it. One should be able to write:

val smallprimes = makeSET (op <) [2,3,5,7,11,13,17,19];
if SETcontains smallprimes 9 then
  "Oh No!"
else
  "Good.";

Hint: The two set functions should be one-liners.

Put all your tree and set definitions in set.sml.

Activation Records

Do Exercises 2, 3 and 7 in Chapter 12 (page 205).

Turn this part in on paper.

Submitting Your Work

You submit your program work by putting it in the homework6 directory in your AFS class volume. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, March 9. In other words, you must be done before lecture starts.

The homework6 directory should include the following:

• set.sml

About this document