Date: Tue, 23 Feb 1999 12:28:32 -0500
Message-Id: <199902231728.MAA00608@xcom-78-155.mdc.net>
From: "Adam P. Jenkins" <ajenkins@netway.com>
To: caml-list@inria.fr
Subject: Re: polymorphically comparable Maps?
In-Reply-To: <5lww199iaq.fsf@tequila.cs.yale.edu>
<5lww199iaq.fsf@tequila.cs.yale.edu>
Stefan Monnier writes:
> >>>>> "Thorsten" == Thorsten Ohl <ohl@hep.tu-darmstadt.de> 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
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET