Browse thread
[Caml-list] Map efficiency?
[
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: | 2003-11-07 (08:41) |
From: | Jean-Christophe Filliatre <Jean-Christophe.Filliatre@l...> |
Subject: | Re: [Caml-list] Map efficiency? |
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