updateLookupWithKey bug? Was: Data.Map, Data.IntMap documentation (1611)

[Adrian Hey]

Actually I think there are several functions in Data.Map that should be
deprecated, including this one (as I did in the clone I wrote).

When it comes to complex hybrid operations like this there are just
to many possible variations, none of which are obviously "correct".
So unless you're going to provide them all and think of sensible
names for them all it's probably best to provide none of them.

Instead, it's trivially easy to implement a really cheap (but limited)
zipper like thing, as is done with the OMap type in the AVL clone.
Using this, the function in question (or anything similar) can easily
be implemented by users themselves..

There's special about AVL trees, this can be done with any binary
tree. It's just a simple node indexing scheme.

And it is really cheap. Even with Ints as keys an OMap based insertion
only takes about 10% longer than a regular insertion, and you get the
added advantage that if the the tree is unmodified you really do get
exactly the same tree (you don't pointlessly burn a lot of heap
duplicating all the nodes on the search path).

Regards
--
Adrian Hey

Don Stewart wrote:
> And sounds like we need some QuickCheck properties too!
> 
> apa3a:
>> I started to update documentation for Data.IntMap. I
>> found a discrepancy between the modules'
>> updateLookupWithKey behavior right in the area brought
>> to my attention earlier:
>>
>> --- Andriy Palamarchuk <apa3a at yahoo.com> wrote:
>>
>>> * As per
>>>
>> http://www.haskell.org/pipermail/libraries/2007-March/007304.html
>>> added following information to the description of
>>> updateLookupWithKey:
>>>
>>> The function returns changed value, if it is
>> updated.
>>> Returns the original key value if the map entry is
>> deleted.
>>
>> The test case:
>>
>>> :m Data.Map
>>> let f k x = if x == "a" then Just ((show k) ++ ":new
>> a") else Nothing
>>> updateLookupWithKey f 5 (fromList [(5,"a"),
>> (3,"b")])
>>
>> (Just "5:new a",fromList [(3,"b"),(5,"5:new a")])
>>
>>> :m Data.IntMap
>>> updateLookupWithKey f 5 (fromList [(5,"a"),
>> (3,"b")])
>>
>> (Just "a",fromList [(3,"b"),(5,"5:new a")])
>>
>> The problem here is that Data.Map.updateLookupWithKey
>> returns the *updated* value, but
>> Data.IntMap.updateLookupWithKey returns the value
>> *before* update.
>>
>> Please agree on the behavior, fix the bug and let me
>> know what to write in the docs.
>> Thanks,
>> Andriy
>>
>>
>> __________________________________________________
>> Do You Yahoo!?
>> Tired of spam?  Yahoo! Mail has the best spam protection around 
>> http://mail.yahoo.com 
>> _______________________________________________
>> Libraries mailing list
>> Libraries at haskell.org
>> http://www.haskell.org/mailman/listinfo/libraries
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
> 
>