From: Berke Durak <berke.durak@exalead.com>
To: Caml-list List <caml-list@inria.fr>
Subject: Canonical Set/Map datastructure?
Date: Wed, 05 Mar 2008 17:49:39 +0100 [thread overview]
Message-ID: <47CECF23.1020508@exalead.com> (raw)
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.
--
Berke DURAK
next reply other threads:[~2008-03-05 16:49 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2008-03-05 16:49 Berke Durak [this message]
2008-03-05 17:16 ` [Caml-list] " Brian Hurt
2008-03-05 17:27 ` Alain Frisch
2008-03-05 19:53 ` Jean-Christophe Filliâtre
2008-03-05 20:03 ` Jon Harrop
2008-03-05 21:56 ` Alain Frisch
2008-03-06 7:45 ` Jean-Christophe Filliâtre
2008-03-05 17:34 ` Harrison, John R
2008-03-06 9:53 ` Berke Durak
2008-03-06 17:36 ` Harrison, John R
2008-03-07 10:09 ` Berke Durak
2008-03-07 17:13 ` Harrison, John R
2008-03-07 10:19 ` Alain Frisch
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=47CECF23.1020508@exalead.com \
--to=berke.durak@exalead.com \
--cc=caml-list@inria.fr \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).