Who needs Ord for Sets and Maps anyway?
Okasaki, C. DR EECS
Christopher.Okasaki at usma.edu
Tue Jan 17 11:23:17 EST 2006
Adrian Hey wrote:
> Well, speaking of "non-trivial comparisons" reminds me of something
> that's been worrying me about this whole approach to implementing
> Sets and Maps. I.E. Requiring that element/key types are instances
> of Ord and assuming that lookup etc is achieved by performing some
> kind of binary search.
> This seems wrong in general. [...]
> This also highlights another reason why IMO specifying "biasing"
> is bad, because doing this implicitly assumes that Sets/Maps somehow
> contain concrete structural representations of elements/keys.
> This is not necessarily so. It's not true with any implementation
> like that described above (or even simple tries).
You've just highlighted why the collections hierarchy in Edison was a
lattice of 8 classes. Basically, there are two choices in each of three
1. The set/map distinction
2. Require Ord or don't (your first point above)
3. "Observable" or not (your second point above)
I think the last point is the one that caused the most confusion, but it
is exactly the issue you highlight above -- some structures contain the
actual elements/keys, but some (such as tries or sets based on bitmaps)
don't. The non-observable parts of the hierarchy are there precisely to
support implementations like tries and bitmaps where it is not easy to
get your hands on the actual elements.
More information about the Libraries