Date: Fri, 7 May 93 12:29:44 +0200
From: cousinea@dmi.ens.fr
Message-Id: <9305071029.AA00287@arnica.ens.fr>
To: Xavier Leroy <xavier@Theory.Stanford.EDU>
Subject: Re: new library modules
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