Re: [Caml-list] Map efficiency?

[Jean-Christophe Filliatre <Jean-Christophe.Filliatre@lri.fr>]

Alex Baretta writes:
 > > Map depends on keys to be ordered. This in turn requires to allow for a
 > > user-defined order: assume sets as keys that are implemented by
 > > unordered lists. Different lists can represent the same set. Hence, it
 > > must be possible to provide a user-defined order that would treat those
 > > lists as equal. The functor argument of Map contains the compare() which
 > > does just that.
 > 
 > The order function could just as easily be passed as a parameter to all
 > functions working on the map. 

This is not a good idea,  because elements could be inserted using one
ordering function  and looked for  using a different one,  with tragic
consequences.

A slightly better  approach would be to pass  the ordering function to
Map.empty only, which  would store it inside the  data structure. This
is  exactly what was  done in  Caml Light,  when Caml  did not  have a
module system yet. 
(see http://camlcvs.inria.fr/cgi-bin/cvsweb.cgi/camllight/src/lib/map.mli?rev=1.3&content-type=text/x-cvsweb-markup)

(But the functorial interface is definitely the best, of course.)

-- 
Jean-Christophe Filliâtre

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners