Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
polymorphically comparable Maps?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 1999-02-23 (16:59)
From: Stefan Monnier <monnier+lists/caml/news/@t...>
Subject: Re: polymorphically comparable Maps?
>>>>> "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
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' ?