Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
Re: new library modules
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 1993-05-07 (10:29)
From: cousinea@d...
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.