Homework # 6
due Thursday, April 12, 2:00 PM

Binary Search Trees for Sets

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

11.

A binary search tree is a binary tree with special properties. It may be Empty. It may be a Node containing a left subtree, a data item $x$, and a right subtree. In this case, all the data items in the left subtree are smaller than $x$ and all the elements in the right subtree are larger than $x$, and the left and right subtrees are also binary search trees. Write a function makeBST of type ('a * 'a -> bool) -> 'a list -> 'a tree that organizes the items in the list into a binary search tree. The tree need not be balanced. You may assume that no item in the list is repeated.

12.

Write a function searchBST of type ('a * 'a -> bool) -> 'a tree -> 'a -> bool that searches for a given data element. You should not search every node in the tree, but only those nodes that, according to the definition, might contain the element you are looking for. 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 ``sets'':

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.

Activation Records

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

2.

Consider a block-structured language implemented using nesting links. Suppose a function nested $n$ levels deep makes a legitimate reference to a local variable of a function nested $m$ levels deep. Describe exactly how to find the variable at run-time. Hint: you do not have to worry about the cases where $m > n$; be sure you explain why not.

3.

Consider a block-structured language implemented using nesting links. Suppose a function nested $n$ levels deep makes a legal call to one nested $m$ levels deep. How should the new activation record's nesting link be initialized? Describe exactly how to find the correct nesting link for all cases--$m < N$, $m=n$ and $m > n$. Hint: You do not have to worry about the cases where $m > n+1$, but be sure you explain why not.

7.

For each of the following ML functions, supposing nested functions are implemented in the technique from the Chapter 12 slides, could the activation record for the function be deallocated as soon as the function returns? Explain why or why not.

1. fun f x = x + 1;
2. fun f x = fn y => x + y;
3. fun f x = fn y => y + 1;
4. fun f x = map  x;
5. fun f (x,l) = map (fn y => x + y) l;
6. fun f x = map (fn y => x + y);

About this document