Re: new library modules

[cousinea@dmi.ens.fr]

As I said, I have also implemented balanced trees and used them
to manipulate what Xavier calls sets and maps .
It is certainly less efficient that Xavier's implementation
since it is a purely functional one
but I have nonetheless used them quite extensively,  building
balanced trees of size over 2^20.

I am not sure my choices have been the right ones
but here is a short description.
My main functions over balanced trees are:

empty: 'a t
add: ('a*'a -> comparison) -> option -> 'a -> 'a t -> 'a t
exists: ('a -> comparison) -> 'a t  -> bool
get: ('a -> comparison) -> 'a t  -> 'a
get_all: ('a -> comparison) -> 'a t  -> 'a list
remove: ('a -> comparison) -> 'a t  -> 'a t
remove_all: ('a -> comparison) -> 'a t  -> 'a t
................

Values of type ('a*'a -> comparison) are supposed to be
total preorders and it is user's responsibality to use
them consistently.
type option = Take_Old | Take_New | Take_Both
 is a type that specifies what should be done
when adding a value to a tree that contains an equivalent one.

Note that functions "get" and "exists" use an argument 

of type ('a -> comparison)
which is similar to giving both an argument "ord" of type
('a*'a -> comparison) and an argument "x" of type 'a as Xavier
does for function "mem". This choice takes into account
the fact that, when using a preorder and not an order,
it is sometimes useful to search for objects that have
a more specific property that just identity or equivalence
to a given object.
This goes against Damien's suggestion to encapsulate the preorder
in the type which I approve for sets and maps  (by the  way,
the proposal by Laufer and Odersky should give a solution
for that).  


Xavier's maps are easily obtained from my balanced trees:
type ('a,'b) map == ('a,'b) t;;
let add_map ord m x y= add ord Take_New (x,y) m;;
let find_map ord m x = snd (get (fun y -> ord x (fst y)) m);;
........

Note that here, the order on type 'a  induces a preorder on type
('a * 'b) which is used for the search.  This is another argument
for the importance of preorders.

  ---Guy