CSE341 Section #4 Problems

Recall the code we wrote for a binary tree of ints:

        datatype intTree = Empty | Node of int * intTree * intTree;

        fun insert(n, Empty) = Node(n, Empty, Empty)
        |   insert(n, Node(root, left, right)) =
                  if n <= root then Node(root, insert(n, left), right)
                  else Node(root, left, insert(n, right));

        fun insertAll([]) = Empty
        |   insertAll(x::xs) = insert(x, insertAll(xs));

        fun height(Empty) = 0
        |   height(Node(root, left, right)) = 1 + 
                Int.max(height(left), height(right));

1. Define a function contains that takes a binary search tree of ints and a
   value n as parameters and that returns whether or not the tree contains n
   (true if it does, false if it does not).  The function should take advantage
   of the fact that the tree is a binary search tree (i.e., it should take time
   proportional to the height of the tree).

2. Define a function collapse that takes a binary search tree of ints as a
   parameter and that returns a sorted list containing the same ints.

3. Define a function treeMap that takes a function and a binary tree of ints as
   parameters and that returns the binary tree that results from applying the
   function to every value in the tree.  The resulting function will not be
   polymorphic because it will require a function of the form int->int.

4. We wrote the qsort function in lecture:

     fun qsort(f, []) = []
     |   qsort(f, pivot::rest) =
             let fun split([], ys, zs) = qsort(f, ys) @ [pivot] @ qsort(f, zs)
                 |   split(x::xs, ys, zs) =
                         if f(x, pivot) then split(xs, x::ys, zs)
                         else split(xs, ys, x::zs)
             in split(rest, [], [])
             end;

   This function takes as a parameter a function f that compares two values and
   returns a boolean result indicating a "less than" relationship.  Write a new
   function called qsort2 that takes a comparison function like Int.compare
   that returns a value of type order.  The version of quicksort above keeps
   track of two lists of values: values less than or equal to the pivot and
   values greater than the pivot.  Your version should keep track of a third
   list of values equal to the pivot.