compiler-ml/chapter1/exercises.sml

type key = string
datatype tree = LEAF | TREE of tree * key * tree

val empty = LEAF

fun insert (key, LEAF) = TREE(LEAF, key, LEAF)
  | insert (key, TREE(l,k,r)) =
      if key < k
        then TREE(insert(key,l),k,r)
      else if key > k
        then TREE(l,k,insert(key,r))
      else TREE(l,key,r)


fun member key LEAF = false
  | member key (TREE(l,k,r)) =
    if key = k
    then true
    else (member key l) orelse (member key r)

(* This is not exhaustive, and will fail if the tree 
   was not created using `insert` *)
fun fastermember key LEAF = false
  | fastermember key (TREE(l,k,r)) =
    if key = k
    then true
    else if key < k
    then fastermember key l
    else fastermember key r