Data.Map, Data.IntMap documentation

[apfelmus]

What I want to say is that a very general Map class can itself be useful 
as abstraction, i.e. the programmer can build his own map types when 
they capture the essence of his problem.

David House and I once stumbled upon this. The task was to write a 
polymorphic delete/insert for a web-forum. I mean, you can delete 
individual posts or whole forums

   type Site  = Data.Map ForumID Forum
   type Forum = Data.Map ForumID Post
   type Post  = String

but you'd have to write different delete functions for that. The insight 
was that the Site is a map of forums

   instance Map Site ForumID where
      type Elem Site ForumID = Forum

while also being a map of Posts

   instance Map Site (ForumID, PostID) where
      type Elem Site (ForumID, PostID) = Post

So, insert and delete work for both the forums and the posts. The path 
from the root of the hierarchy to the object in question says whether 
it's a forum or a post to operate on.

Adrian Hey wrote:
> 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.

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

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

>> 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)

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.


Regards,
apfelmus