Adrian Hey wrote:
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.
What I want to say is that the functional dependency map -> k is too restrictive. A single map type can serve as map for different types of keys and values. So, the type Foo k1 k2 a = Data.Map k1 (Data.Map k2 a) can be seen as a map from keys (k1,k2) to values a instance Map (Foo k1 k2 a) (k1,k2) where type Elem .. .. = a but also as a map from keys k1 to values (Data.Map k2 a) instance Map (Data.Map k1 (Data.Map k2 a)) k1 where type Elem .. .. = Data.Map k2 a Regards, apfelmus