Who needs Ord for Sets and Maps anyway?

[Okasaki, C. DR EECS]

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. [...]

and

> 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
different dimensions:

  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.

-- Chris