A single general modification function for Map and IntMap proposal

[Shachaf Ben-Kiki]

On Tue, Apr 30, 2013 at 8:20 AM, Milan Straka <fox at ucw.cz> wrote:
> Hi all,
>
>> -----Original message-----
>> From: Nikita Volkov <nikita.y.volkov at gmail.com>
>> Sent: 30 Apr 2013, 17:18
>>
>> Because of the above I have very often found myself in requirement for the following function:
>>
>>    withItem ::
>>      (Ord k) =>
>>      k ->
>>      (Maybe i -> (r, Maybe i)) ->
>>      Map k i -> (r, Map k i)
>>    withItem k f m =
>>      let
>>        item = Map.lookup k m
>>        (r, item') = f item
>>        m' = Map.update (const item') k m
>>      in (r, m')
>
> last time we talked about adding
>   lens :: k -> Map k a -> (Maybe a -> Map k a, Maybe a)
> the performance of the direct implementation was actually worse than
> using lookup+insert or such, see the thread
> http://www.haskell.org/pipermail/libraries/2012-January/017423.html
> and the benchmark results at
> http://www.haskell.org/pipermail/libraries/2012-January/017435.html
>

If this is a good API, and the direct implementation is slower than an
indirect implementation in terms of lookup+insert+delete, then the
indirect implementation should be exported. Keep in mind that this
operation is just `alterM` (except generalized to Functor --
`alterF`?).

However: I just wrote a quick direct version:

    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)

And benchmarked lookup-via-alterF, insert-via-alterF, etc. -- they
come out much slower. However, if I add an INLINE pragma or SPECIALIZE
pragmas for common/relevant functors (e.g. Const r, Identity, (r,)),
then they come out almost the same speed as the primitive function.

I don't think INLINE is necessarily bad for this function. (I don't
like the idea of using SPECIALIZE here because I don't think e.g.
Identity should have special privileges over some other newtype with
the same Functor instance.) So maybe the direct implementation should
be reconsidered. I can do a more thorough benchmark later if people
are interested.

>
> I am also a bit worried whether withItem is the "right" general
> function. For example Shachaf Ben-Kiki mentions the
>   at :: (Ord k, Functor f) => k -> (Maybe i -> f (Maybe i)) -> Map k i -> f (Map k i)
> from the lens package in other mail, but maybe there are others.
>

I think that alterF almost certainly *a* right function -- it's just a
monadic/functorial version of `alter`, which is the most general
"simple" updating function. Possibly there should be others too, but
this one is useful and general. Although it needs a better name. :-)

(Note that e.g.
    adjustF :: (Ord k, Applicative f) => k -> (a -> f a) -> M.Map k a
-> f (M.Map k a)
can just be
    \k -> alterF k . traverse
just as with alter/adjust.
)

>
>>    1. Implement an efficient version of "withItem" for lazy and strict versions of "Map" and "IntMap".
>
> Maybe we will need a benchmark to see whether withItem is really faster
> than combination of lookup+update.
>
>>    3. Begin the deprecation process of the following functions: insertWith, insertWithKey, insertLookupWithKey, adjust, adjustWithKey, update, updateWithKey, updateLookupWithKey, alter.
>
> I am against deprecating insertWith, insertWithKey, updateWithKey,
> updateWithKey, because they are useful.
>
> I am against deprecating adjust, adjustWithKey and alter, mostly because
> of compatibility reasons, although I agree that their name is not
> descriptive.
>
> I am indifferent about insertLookupWithKey and updateLookupWithKey. It
> would be nice to show that their implementation is really faster than
> lookup+insert / lookup+update combo.
>

    Shachaf