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
Canonical Set/Map datastructure?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2008-03-05 (17:16)
From: Brian Hurt <bhurt@j...>
Subject: Re: [Caml-list] Canonical Set/Map datastructure?
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 is not equivalent to

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