Hello apfelmus, Thanks for taking the time to look at this. As what Jamie has posted is largely based on my own initial efforts I can offer some insight about what's going on here and why the class API looks like it does. The first thing to note is that what Jamie has posted is the proposed class methods *only*. It's not the complete user level map API. There's also a whole lot of more convenient and sensible looking functions that are just regular overloaded functions. Unfortunately these are not visible in the API posted. Among them are things like this.. size :: GT map k => map a -> Int size mp = ASINT(addSize mp L(0)) (ASINT and L are a cpp macros) elemsAscending :: GT map k => map a -> [a] elemsAscending mp = foldrElemsAscending (:) mp [] assocsAscending :: GT map k => map a -> [(k,a)] assocsAscending mp = foldrAssocsAscending (\k a assocs -> (k,a):assocs) mp [] keysAscending :: GT map k => map a -> [k] keysAscending mp = foldrKeysAscending (:) mp [] The second thing to note is that the class API has been designed with the *implementation* of generalised tries in mind. It's not necessary that any instance is actually implemented as any kind of trie, but it is necessary that the resulting API contains what's needed to enable its use in other instances that are based on generalised tries. So the actual class methods chosen are designed to be convenience for generalised trie implementation, not typical map users. The types are chosen to reflect how they will likely be used in other generalised trie implementations and the functionality provided is what it seems is actually needed to do this efficiently. What the class API contains has kind of evolved empirically with stuff being added as and when it was discovered it was needed (by implementing a few common instancance by hand). Here's my thoughtS about your specific observations.. apfelmus wrote:
1) Some terminology seems queer to me. In particular, I don't like the terms "assoc" and "association" in the documentation. The Data.Map documentation uses "key/value pair" or just "key" and "value"/"element" instead, which I think is much better. For instance:
"Insert a new association in the map" :( "Insert a new key and value in the map." :)
Also, I like fromList better than fromAssocs .
Well this is one of those bike shed arguments :-) I'm easy about it so if Jamie agrees with you that's fine. Use of the term "association" seems quite common. I've seen numereous uses of the term "association list", never seen anyone talk about "key/value pair list".
2) Don't use Int# , looks like a premature optimization to me. Furthermore, I'd change the queer addSize to simply
size :: map a -> Int
This does exist (see above), but it's not a class method. One could argue that is was unnecessary to make unboxing explicit. It's something I got into the habit of doing because it's way easier to do that than is inspecting ghc's output to make it's done it on its own (and figuring out what to do about it if it hasn't). Also, because of the nested nature generalised tries addSize is more convenient for implementors than size IMO.
3) insert is strange. Why not use the convention in Data.Map, name it insertWith and have
insert :: k -> a -> map a -> map a instead?
Yes, this this should probably be added to the user API. As a choice of primitive class method, the current form seems more appropriate (though perhaps not it's name). All the common user level variants can easily be implemented with this primitive.
Similar for union .
Actually I don't like Data.Maps union much. It would be deprecated if I ruled the world. I think users should be always be made to specify how overlapping values are to be combined (or discarded or whatever). So the name union is now free we don't need to qualify the function that is explicit about this using a "With" suffix.
4) Most functions, in particular the ..Maybe variants have fixed default definitions. I wouldn't include them in the class. How about a minimal class interface along the lines of
class GMap map k | map -> k where empty :: map a null :: map a -> Bool
lookup :: k -> map a -> Maybe a alter :: (Maybe a -> Maybe a) -> k -> map a -> map a merge :: (k -> Maybe a -> Maybe b -> Maybe c) -> map a -> map b -> map c
fromList :: [(k,a)] -> map a toList :: map a -> [(k,a)]
instance Functor map where ...
and implementing the various variants as normal polymorphic functions? Like
insert k a = alter (const $ Just a) k singleton k a = insert k a empty
IMHO, having a few "flag" functions like
difference :: k -> Maybe a -> Maybe b -> Maybe b union :: k -> Maybe a -> Maybe a -> Maybe a intersect :: k -> Maybe a -> Maybe a -> Maybe a
that can be plugged into merge is much nicer than having to remember/lookup all the ..Maybe and whatnot'' variants.
I've never been very keen on alter myself (on efficiency grounds) and was wondering whether of not to include it. If the "altering" results in an unchanged map it would be nice to just return the unchanged map (rather than duplicate all nodes on the search path). There are other possible alternatives to alter that are more efficient in this respect. The merge function looks like an interesting idea, but it's not clear to me that it can always (or ever even :-) be implemented as efficiently as the more specialised versions. Maybe as and experiment we could implement it and if it turns out that union,intersection etc can be implemeted using it with liitle or no extra cost then we could put them in the convinience API instead (not as class methods).
5) I think the following functions are queer
lookupCont f k m = lookup k m >>= f
Or perhaps.. lookup = lookupCont Just Yes, there's probably unwanted duplication in the class methods there. My vote would be to keep lookupCont and a class method and have lookup as regular overloaded function.
pair k1 k2 = if k1 == k2 then Nothing else Just $ \a1 a2 -> insert k1 a1 (insert k2 a2 empty)
What use is pair ? I'd definitively put them outside the class if not remove them entirely.
Again, pair is one of those things that a typical Map user wouldn't use, but is definitely needed to implement an efficient trie for Lists and probably product types in general. The reason for it's existance is that singleton maps need special treatment (you want to avoid making long chains of them). Unfortunately the above definition is inefficient. You've already done most of the work requred to evaluate pair in the first equality test. This would all have to be repeated in the second insertion. Have a look at the ListGT module to see how pair is defined and used for the gory details.
6) status is an interesting idea with a meaningless name. Don't you have a name that is more to the point, that expresses the nub (pun intended) of what status does?
If you're suggesting it should be called nub, that seems confusing considering that name is already used in Data.List to mean something quite different. Perhaps you can suggest some other name?
7) I'm overwhelmed by the many foldr...Asc/Descending functions. They all can be expressed in terms of toListAsc and toListDesc and I don't think that "marginally faster" is a reason not to do so.
..or vice-versa, but without the need for list deforestation to get the same efficiency. Also I think we need to distinguish between the variants that require key reconstruction from those that don't (keys generally aren't stored in a trie).
I'd throw away the from...L functions, too.
The L versions can improve performance in some map implementations where length is needed and is already known as by product of other stuff that's going on. In such cases it seems to make sense to pass it as an argument rather than incur the cost of evaluating it again from scratch. Anway, I don't think we should get to worried about the precise details of class methods right now. I think the main concern should be getting the class hierarchy right, I'm not sure that it at present. e.g. There may be specialised representations that support lookup very efficiently but not much else. Should we have a separate class for them? Should we have separate classes for implementations that store keys (hence no key reconstruction cost) and those that must reconstruct keys? Then there's the ordering can of worms too. This is the sort of thing that really needs to be got right from the start IMHO. Regards -- Adrian Hey