Hi Berke,

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

I have an implementation, which you're welcome to use/adapt. It's
certainly not particularly well optimized, but I've relied on it
for a few years with no problems. The code is in this file:

  http://www.cl.cam.ac.uk/~jrh13/atp/OCaml/lib.ml

Search for "Diego" and the relevant stuff starts there; a few
earlier functions (like "uniq") are used, but they are easy to
copy or replace.

This was the outcome of a similar question I asked on the OCaml
list a few years ago. Diego Olivier Fernandez Pons not only
pointed me at some interesting theoretical results, but also
suggested an idea using hashes and Patricia trees that works very
well in practice. That's what I implemented. My implementation
is for maps only, but it's easy to adapt for sets. Or you could
just use maps to type "unit" if you're lazy like me.

John.