From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id KAA18107 for caml-redistribution; Thu, 25 Feb 1999 10:08:34 +0100 (MET) Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id SAA23621 for ; Tue, 23 Feb 1999 18:29:04 +0100 (MET) Received: from xcom-78-155.mdc.net (xcom-78-155.mdc.net [209.251.78.155]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id SAA15409 for ; Tue, 23 Feb 1999 18:28:53 +0100 (MET) Received: (from ajenkins@localhost) by xcom-78-155.mdc.net (8.8.7/8.8.7) id MAA00608; Tue, 23 Feb 1999 12:28:32 -0500 Date: Tue, 23 Feb 1999 12:28:32 -0500 Message-Id: <199902231728.MAA00608@xcom-78-155.mdc.net> X-Authentication-Warning: xcom-78-155.mdc.net: ajenkins set sender to ajenkins@netway.com using -f From: "Adam P. Jenkins" MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: caml-list@inria.fr Subject: Re: polymorphically comparable Maps? Newsgroups: lists.caml In-Reply-To: <5lww199iaq.fsf@tequila.cs.yale.edu> References: <14033.38333.652607.941379@heplix4.ikp.physik.tu-darmstadt.de> <5lww199iaq.fsf@tequila.cs.yale.edu> X-Mailer: VM 6.35 under Emacs 20.3.1 Sender: weis Stefan Monnier writes: > >>>>> "Thorsten" == Thorsten Ohl writes: > > library) with the property that identical maps will have an identical > > representation? Sorted association lists work, but have linear access > > and insertion. Is there something logarithmical (even with an OCaml > > implementation)? > > I can't think of any obvious good answer, but if you can live with > explicit `canonicalization' (linear time) steps in order to then > get logarithmical access and identical representation, then some > kind of binary tree can do the job. Of course, equality comparison > (although simple thanks to the identical representation) will still > be linear, so it doesn't buy you much since equality comparisons of > non-balanced binary trees (or pretty much any map of ordered types) > can also be done fairly simply in linear time. > > So why exactly do you want that representation to be `identical' ? I almost sent in the same answer you gave, but then realized that I'd missed the significance of the word "polymorphic" in the subject. The polymorphic comparison functions in ocaml -- (<), (<=), compare, etc. -- cannot be overloaded for user-defined types, so if you want your Map datatype to be able to work with the polymorphic comparison functions then you need to make semantically identical maps also be structurally identical. As for why one would want the map datatype to be polymorphically comparable, if you want a map to be part of some other datastructure, such as a list of maps, and want to be able to compare two lists of maps using, say, (=), then the maps need to be structurally identical for this to work. Adam -- Adam P. Jenkins ajenkins@netway.com