Who needs Ord for Sets and Maps anyway?

[Adrian Hey]

Hello Chris,

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

Yes, the more I think about this the more difficult it seems to produce
abstract, polymorphic and efficent Sets/Maps. The Ord/Binary tree
approach really does seem a bit naive to me now (even if it does use
AVL trees :-) But realistic alternatives seem to require the use of
language features that are non-standard (and mostly beyond my grasp
at the moment anyway, but I've never really looked at them seriously).

We can produce specialised implementations for particular types and
include them in standard libs. But this still doesn't address the real
problem (well I think it's the real problem) of how users can easily
produce implementations for their own (non-standard) types. Just
deriving Ord won't be good enough.

Is Edison still being maintained, BTW? I wasn't even aware that is was
distributed (with GHC least) until quite recently. (It seems a pity to
have it languishing in obscurity under hslibs.)

Regards
--
Adrian Hey