Data.Map, Data.IntMap documentation

[Adrian Hey]

apfelmus wrote:
> Well of course, every algebraic type can be made an instance of Ord and 
> Eq. But neither is necessary for implementing
> 
>  Ralf Hinze. Generalizing generalized tries.
>  http://www.informatik.uni-bonn.de/~ralf/publications/GGTries.ps.gz

Indeed, none of the current or anticipated future GT implementations
ever actually compare two Keys, despite the Ord constraint (well except
OrdGT itself). But ListGT does (and others possibly will) test for
equality, so will need an Eq constraint.

This is done for reasons of efficiency. Using a ListGT implementation
like the one given in the paper you cite would remove the need for
this, but would give poor performance and excessive heap burn rate
for some common operations, so I'm not going to go that way.

> Those instances that want an Ord requirement can impose it but those 
> that don't want it won't need to impose it.

But I don't see any harm in it even for people who don't care about
ordering, and it's pretty useful for those (the majority I believe)
who do care.

I also don't see the problem. To produce a trie type for a given key
type you have to know something about the structure of the key,
certainly enough to be able to test keys for equality (in principle,
even if the eventual implemetation never actually does this). Same
applies to ordering, except for a few vary rare "hack" cases
like the examples that have been given (which are probably cureable,
even if they haven't actually been cured at present).

If say instead of assocsAscending we just had assocs (which didn't
provide any guarantee about ordering), then anyone who wanted
the list sorted would have to do a separate sort. Also in the absence
of some other Ord respecting trie type they'd have to do this sort
the slow way (by O(n.log n) comparisons).

One thing possibly might be to move the Ord constraint from the
class head and put in relevant methods, or maybe have a separate
GTO class..

  class (Ord k, GT map k) => GTO map k where..

I'll give that some thought, but I rather like knowing for sure that
if I have (GT map k) then I also have (Ord k) and hence (Eq k) and
I don't like complexifying the class hierarchy for no good reason
(I'm not persuaded that this Ord issue really is an issue at all)

> I don't see why a map should work for a single key type only, except 
> that maps as type constructors support only one key type of course, 
> since the element type is fixed then. Different key types may yield 
> different element types.

I'm not sure I understand what you mean by single key type only. AFAICS
you can only implement an *efficient* trie if it has been designed
specifically for the key type in question, so of course it should come
as no surprise that it will only work for the key type in question.
But this is not a problem if GT derivation for any type you define
is automated.

But the keys can be polymorphic and you can still make GT instances
provided you have GT constraints on the type variables. The ListGT
instance will work for many key types for example, but they all
have to be lists of something.

Regards
--
Adrian Hey