A single general modification function for Map and IntMap proposal

[Milan Straka]

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