Update: I've rewritten my solution above to be as close as possible to the original Arc code. All the function interfaces should be the same. Equality is determined with (=), which is the closest thing OCaml has to Arc's is.
I've also created a separate version that's closer to how I would prefer to implement it:
1. The comparison function is specified using a functor. This allows the user to specify it only once instead of in every call to insert, find, and so on. (I'd like to see something like ML's functors in Lisp someday.)
2. The comparison function handles equality as well as order.
3. edge is replaced by min_elt and max_elt.
4. rem-edge is gone.
5. The output of to_list (aka elts) isn't backwards.
Maybe I'm not understanding your code (it's kind of cryptic...) but it does seem the same to me. When bst-rem removes a node with one child, it just grabs the other child. This is the same thing bst-rem-edge does.
Your 'bubble' function calls bst-edge to find the left/rightmost node and then calls bst-rem-edge to remove it. You could just as well call bst-edge and then bst-rem on the result; either way you traverse the tree twice. I can't imagine a situation where you'd just want bst-rem-edge by itself.
Come to think of it, I don't know why you need bst-edge either. It's simpler to just have min and max functions that return an element, as in the Haskell solution.
