A single general modification function for Map and IntMap proposal

[Edward A Kmett]

Flipping to lambda -> key means that you cannot compose these for nested lookups.

alterF in its current form is a valid lens.

A very common idiom from the lens community is to do lookups in nested maps with the equivalent of:

alterF key1 . traverse . alterF key2

There is a similar idiom for doing inserts into nested maps as well.

Flipping it means any composition of alterF incurs lots of flips.

-Edward

On Jun 19, 2013, at 8:27 AM, Milan Straka <fox at ucw.cz> wrote:

> Hi all,
> 
>> -----Original message-----
>> From: Nikita Volkov <nikita.y.volkov at gmail.com>
>> Sent: 19 Jun 2013, 13:47
>> 
>> Hello guys!
>> 
>> A deadline of a discusssion on this has been reached. To review the discussion you can visit the archives. Following is a summarization.
>> 
>> 1. Following is an implementation proposed by Schachaf Ben-Kiki, which in a combination with an `INLINABLE` pragma produces very impressive results by making even the primitive operations reimplemented in terms of it perform better:
>> 
>> insert: ~ +5% increase using alterF
>> delete: ~ +10% increase using alterF
> 
> I probably did not make myself clear enough -- the insert reimplemented
> with alterF runs 5% slower (the running time is increased by 5%) and
> similarly for delete.
> 
>>   alterF :: (Ord k, Functor f) => k -> (Maybe a -> f (Maybe a)) -> Map k a -> f (Map k a)
>>   STRICT_1_OF_2(alterF)
>>   alterF k f = go
>>     where
>>       go Tip = maybe Tip (singleton k) <$> f Nothing
>>       go (Bin sx kx x l r) =
>>         case compare k kx of
>>           LT -> (\l' -> balance kx x l' r) <$> go l
>>           GT -> (\r' -> balance kx x l r') <$> go r
>>           EQ -> maybe (glue l r) (\x' -> Bin sx kx x' l r) <$> f (Just x)
>> 
>> 2. `alterF` seems to be a mutually accepted title for the function
>> 
>> 3. There was one downvote for implementing `alterF` with a changed order of parameters to "key -> lambda", as compared to "lambda -> key" of other modification functions in the library. Others seemed to be neutral about it. The implementation above is in that changed order. After some thinking my vote can be counted as a downvote too on that.
> 
> Looking at alterF, I think we should be consistent with the rest of the
> API and use lambda -> key.
> 
> 
> Cheers,
> Milan
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries