Re: polymorphically comparable Maps?

From: Stefan Monnier (monnier+lists/caml/news/@tequila.cs.yale.edu)
Date: Tue Feb 23 1999 - 17:49:33 MET


To: caml-list@inria.fr
From: Stefan Monnier <monnier+lists/caml/news/@tequila.cs.yale.edu>
Subject: Re: polymorphically comparable Maps?
Date: 23 Feb 1999 11:49:33 -0500

>>>>> "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' ?

        Stefan



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET