Re: new library modules
 cousinea@d...
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
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. Guy