A single general modification function for Map and IntMap proposal

[Nikita Volkov]

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

   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.

4. People seem to be indifferent to functions `insertLookupWithKey` and `updateLookupWithKey`, concerning their deprecation. The other proposed functions from the list following, however, generally are not wished to deprecate: insertWith, insertWithKey, adjust, adjustWithKey, update, updateWithKey, alter.

Best regards,
Nikita Volkov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130619/7fc38139/attachment.htm>