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