Generic tries (long)

[apfelmus]

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.



Regards,
apfelmus