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