Generic tries (long)

[apfelmus]

Adrian Hey wrote:
> 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.
>
> The second thing to note is that the class API has been designed with
> the *implementation* of generalised tries in mind.

Ah ok, I thought that would be the user API already.

So, the class API is for "users" who want to plug in their own 
generalized trie implementations? In any case, I'm all for keeping it 
simple and minimal, possible minor efficiency penalties notwithstanding :)

>> I don't like the terms "assoc" and "association"
> 
> 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".

The term "association list" seems to be atomic, i.e. it's not a list of 
associations. The dictionary of A&DS ( http://www.nist.gov/dads/ ) 
always says "key" and "value", though it doesn't mention pairs of these 
directly. The documentation for Data.Map uses "key/value pair" explicitly.

>>      alter    :: (Maybe a -> Maybe a) -> k -> map a -> map a
>
> 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.

You mean the case when

   f Nothing = Nothing

in  alter f .. ? Hm, maybe some zipper-like extension of  lookup  can do 
the trick

   focus :: k -> map a -> (Maybe a, Maybe a -> map a)

   lookup k    = fst . focus k
   delete k m  = case focus k m of
       (Nothing, _) -> m
       (_      , g) -> g Nothing
   alter f k m = case focus k m of
       (Nothing, g) -> case f Nothing of
            Nothing -> m
            x       -> g x
       (x      , g) -> g x

>> 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?

No, it shouldn't be  nub  of course, just a similarly succinct yet 
meaningful name. Hm, maybe  monkeyView  in accordance with the way the 
monkeys count:  one, two, many. :)


Regards,
apfelmus