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