Data.Map, Data.IntMap documentation

apfelmus apfelmus at
Wed Aug 22 03:28:52 EDT 2007

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


More information about the Libraries mailing list