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

["Harrison, John R" <john.r.harrison@intel.com>]

Hi Berke,

| However, the idea of combining hash-consing and Patricia trees,
| however elegant, does not suit my problem.  Basically, you are
| cheating by using an auxiliary data structure, the hashtable (which is
| also O(n^2) worst-case).

The code I pointed you to uses hashes, but not hash tables. As for the
worst-case efficiency, what you say is true, but it's unlikely to
matter in practice. And I suspect it may be unavoidable in principle,
which is the interesting thing I learned last time this was discussed.
See for example the following paper and its references:

 "New Tight Bounds on Uniquely Represented Dictionaries"
 Arne Andersson and Thomas Ottmann
 SIAM J. vol 24, pp. 1091-1103, 1995.

The paper is available online as

  http://user.it.uu.se/~arnea/ps/andetigh.ps

Note in particular the following paragraph:

 "Hence we show that there is a huge gap between unique and non-unique
  representations of dictionaries. We feel that these findings point
  to a fundamental fact in the theory of data structures".

| As I was improving my IO combinator library with sets and maps, the
| structures need to be self-contained, and not need a description as a
| bitstring (which could be done by using Marshal.to_string but I don't
| think the performance would be there).  Maybe some wizardry relying on
| the physical representation of objects would permit storage of
| arbitrary values in Patricia trees, but I remain skeptical. --

My code uses OCaml's polymorphic hashes internally, but these do not
appear in the interface and the user doesn't need to supply anything.
Indeed, you may regard OCaml's polymorphic hash as a hack, but it is
available in OCaml for every type just as surely as polymorphic
equality. So I'm not sure I quite understand the nature of your
objection.

John.