Re: [Caml-list] Canonical Set/Map datastructure?

[Brian Hurt <bhurt@janestcapital.com>]

Berke Durak wrote:

> The Map and Set modules use AVL trees which are efficient but not 
> canonical - a given
> set of elements can have more than one representation.  This means 
> that you cannot use
> ad hoc comparison on sets and maps, and this is why they are presented 
> as functors.

However, as you can walk the tree in O(N), it's still possible to do 
set/map compare in O(N) worst case.  All this means is that 
Pervasives.compare is not equivalent to Set.compare.

>
> Does anyone know if, in the many years that have passed since the 
> implementation of
> those fine modules, someone has invented a (functional) datastructure 
> that is as
> efficient while being canonic?

The preserves "fast" (O(log N)) insert and removal?  No.  If you're 
willing to accept O(N) insert/removal cost, simple sorted lists work.  
I'm not sure if it's possible to have both fast insert/removal and a 
canonical form.

Brian