Generic tries (long)

[Adrian Hey]

Hello Jamie,

Jamie Brandon wrote:
> Ive put up the haddock api at http://code.haskell.org/gmap/api/GMap.html

The ordering issue is still bothering the heck out of me. With the
above OrderedGMap class (only) we lose the ability to use tries for
sorting faster than the usual O(n . log n), which seems a real shame.
Especially as it means folk will often end up having to do a
O(n . log n) sort stage on the data anyway (without the benefit of
"trie acceleration" presumably).

So I think I would really like to see a subclass that *does* guarantee
Ordering that is consistent with Ord. The question of how instances of
that subclass are produced/derived or whatever is still open. Automated
trie deriving could presumably only guarantee ordering consistent with
a (wholly) derived Ord instance, not hand written Ord instances.

I also find myself wondering if we really need to make the distinction
between Map implementations that really can make *no* guarantee about
consiststent ordering and maps that do guarantee consistent ordering
(that is inconsistent with Ords ordering). I'm struggling to imagine
any decent Map implementation that falls into the former category
(I.E. is an instance of GMap *only*). I guess hash tables that used a
linear list for each bucket are one possible example, hmm..

Also, a minor naming niggle with the folds in the GMap class. I think
these should have a "fold" prefix only (not "foldr"), as there is no
implied ordering guarantee.

I'm also wondering if we should at least have an Eq constraint on
keys for GMap. I guess we should.

Regards
--
Adrian Hey