Re: polymorphically comparable Maps?

[Stefan Monnier <monnier+lists/caml/news/@tequila.cs.yale.edu>]

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