English version
Accueil     À propos     Téléchargement     Ressources     Contactez-nous    

Ce site est rarement mis à jour. Pour les informations les plus récentes, rendez-vous sur le nouveau site OCaml à l'adresse ocaml.org.

Browse thread
[Caml-list] Map efficiency?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ 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

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