From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id JAA23170; Fri, 7 Nov 2003 09:41:32 +0100 (MET) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id JAA23213 for ; Fri, 7 Nov 2003 09:41:31 +0100 (MET) Received: from lri.lri.fr (lri.lri.fr [129.175.15.1]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id hA78fU116517 for ; Fri, 7 Nov 2003 09:41:30 +0100 (MET) Received: from pc8-123 (pc8-123 [129.175.8.123]) by lri.lri.fr (8.12.10/jtpda-5.4) with ESMTP id hA78RJUV017740 ; Fri, 7 Nov 2003 09:27:25 +0100 (MET) Received: from filliatr by pc8-123 with local (Exim 3.35 #1 (Debian)) id 1AI1xf-0006pb-00; Fri, 07 Nov 2003 09:27:19 +0100 From: Jean-Christophe Filliatre MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Message-ID: <16299.22375.433305.104788@gargle.gargle.HOWL> Date: Fri, 7 Nov 2003 09:27:19 +0100 To: Alex Baretta Cc: ocaml Subject: Re: [Caml-list] Map efficiency? In-Reply-To: <3FA7EC77.50502@baretta.com> References: <20031104093905.GF24152@st> <3FA7EC77.50502@baretta.com> X-Mailer: VM 7.03 under Emacs 20.7.2 Reply-To: Jean-Christophe.Filliatre@lri.fr (Jean-Christophe Filliatre) X-MailScanner: Found to be clean X-Loop: caml-list@inria.fr X-Spam: no; 0.00; filliatre:01 filliatre:01 lri:01 caml-list:01 baretta:01 implemented:01 functor:01 camlcvs:01 cvsweb:01 mli:01 functorial:01 caml:01 caml:01 camllight:01 alex:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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