Generic tries (long)
apfelmus at quantentunnel.de
Thu Jun 19 06:33:58 EDT 2008
Jamie Brandon wrote:
> Ive put up the haddock api at http://code.haskell.org/gmap/api/GMap.html
I have a few comments on the proposed API.
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 .
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
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? Similar for union .
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.
5) I think the following functions are queer
lookupCont f k m = lookup k m >>= f
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.
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?
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. I'd throw
away the from...L functions, too.
More information about the Libraries