Key to CSE341 Section #4 Problems

1. One possible solution appears below.

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

2. One possible solution appears below.

        fun collapse(Empty) = []
        |   collapse(Node(data, left, right)) =
                collapse(left) @ data::collapse(right);

3. One possible solution appears below.

        fun treeMap(f, Empty) = Empty
        |   treeMap(f, Node(data, left, right)) = 
                Node(f(data), treeMap(f, left), treeMap(f, right));

4. One possible solution appears below.

     fun qsort2(f, []) = []
     |   qsort2(f, pivot::rest) =
             let fun split([], ys, zs, ps) = qsort2(f, ys) @ ps @ qsort2(f, zs)
                 |   split(x::xs, ys, zs, ps) =
                         let fun process(LESS) = split(xs, x::ys, zs, ps)
                             |   process(EQUAL) = split(xs, ys, zs, x::ps)
                             |   process(GREATER) = split(xs, ys, x::zs, ps)
                         in process(f(x, pivot))
                         end
             in split(rest, [], [], [pivot])
             end;