Data.Map, Data.IntMap documentation
apfelmus at quantentunnel.de
Fri Aug 17 04:06:26 EDT 2007
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.
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.
More information about the Libraries