Data.Map, Data.IntMap documentation

Adrian Hey ahey at
Thu Aug 16 18:37:44 EDT 2007

apfelmus wrote:
> The Ord-constraint is too limiting for tries. 

Well it isn't going to disappear while I'm in charge of GT class :-)
Why do you object to it? Ultimately we must be able to test keys
for equality at least. Is there a type that is an instance of Eq,
but not Ord (or could not reasonably be made an instance of Ord)?

It's extremely useful to be able to give meaningful orderings
when converting between tries and lists. In the case of constructing
tries from ordered association lists there's a significant
performance advantage too.

> Also, the map type does not necessarily fix the key type,

For instances of GT it does. The point is that eventually the Trie type
(and corresponding GT instance) will be designed optimally and
specifically for one particular key type (using DrIFT, Derive, template
Haskell or something..)

> we can use one map with different key types.

Not with GT. If (say) Data.Map was an instance then we would have
something like..

instance Ord k => GT (Map k) k where ..

I.E. The map type constructor in question is (Map k), not Map.
(Map k does fix the key type as k)

Adrian Hey

More information about the Libraries mailing list