From mboxrd@z Thu Jan  1 00:00:00 1970
Received: by margaux.inria.fr, Fri, 7 May 93 15:35:50 +0200
Received: from concorde.inria.fr by margaux.inria.fr, Fri, 7 May 93 12:29:48 +0200
Received: from dmi.ens.fr by concorde.inria.fr; Fri, 7 May 1993 12:30:12 +0200
Received: from arnica.ens.fr by dmi.ens.fr (5.65c8/ULM-1.0)
Date: Fri, 7 May 93 12:29:44 +0200
From: cousinea@dmi.ens.fr
Message-Id: <9305071029.AA00287@arnica.ens.fr>
Received: by NeXT.Mailer (1.87.1)
Received: by NeXT Mailer (1.87.1)
To: Xavier Leroy <xavier@Theory.Stanford.EDU>
Subject: Re: new library modules
Cc: caml-list@margaux
Sender: weis@margaux



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