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