Generic tries (long)
apfelmus at quantentunnel.de
Sat Jun 21 05:09:49 EDT 2008
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
You mean the case when
f Nothing = Nothing
in alter f .. ? Hm, maybe some zipper-like extension of lookup can do
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. :)
More information about the Libraries