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 (16:49)
From: Berke Durak <berke.durak@e...>
Subject: Canonical Set/Map datastructure?
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.

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?

That would permit polymorphic set and map modules that work correctly on sets of sets, for
instance.  Of course, the order induced on sets by the adhoc comparison doesn't have to
be a useful order; just being a good order would suffice.