(* join -- joins two binary trees *) local exception f_Impossible; (* can never happen *) fun f tempty = raise f_Impossible | f (Tree(tempty,y,z)) = (y,z) | f (Tree(x,y,z)) = let val (n,t) = f x in (n,Tree(t,y,z)) end in fun join tempty tempty = tempty | join l tempty = l | join tempty r = r | join l r = let val (x,y) = f r in Tree(l,x,y) end end; (* delete -- delete an element in a binary tree that has been built with predicate p *) fun delete p x tempty = tempty | delete p x (Tree(l,a,r)) = if x = a then join l r else if p x a then Tree(delete p x l,a,r) else Tree(l,a,delete p x r); (* What is this function? *) exception cant_happen; fun what tempty = raise cant_happen |what (Tree(tempty,a,r)) = (a,r) |what (Tree(l,a,r)) = let val (a_what,tree_what) = what l in (a_what,Tree(tree_what,a,r)) end;