Do Exercise 11, and 12 (on page 179) with several changes (see footnote marks):
Empty. It may be a Node
containing a left subtree, a data item makeBST of type ('a * 'a ->
bool) -> 'a list -> 'a tree that efficiently1organizes the items in the list
into a binary search tree. The tree must be
balanced.2 You
may not assume that no item in the list is repeated.1 Duplicates must be discarded.1
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.1Instead it should use the comparison function,
and assume that
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 include a function type.
One should be able to write:
val smallprimes = makeSET (op <) [2,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.
Do Exercises 2, 3 and 7 in Chapter 12 (page 205).