<div dir="ltr"><div style>I find generalizing even more with "at" or "alterF" a very interesting suggestion and I'm fine with either title. I however was not able to trace any practical use of it, because in my imagination the original proposal covered all scenarios, so it'd be helpful to see some examples. Also since the performance turned out to be such an intricate issue in this case I think it is worth benchmarking both the functorial and the simple version. But either way I like the idea.</div>
<div style><br></div><div style>I also want to highlight the expressed idea that either version of this function should make it into the library no matter whether we're able to come up with an efficient implementation, since those functions also provide another important benefit by abstracting over a common pattern, thus simplifying the client code.</div>
<div><br></div><div>Schachaf, concerning your implementation. Great! It looks like a beginning of an implementation process. What do you think about posting it with the benchmark as a branch of your fork of "containers" project on GitHub? This way other participants will be able to fork from you and continue on with experiments, so it'll be easier for us to manage code and to keep in sync. </div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/5/1 Shachaf Ben-Kiki <span dir="ltr"><<a href="mailto:shachaf@gmail.com" target="_blank">shachaf@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">On Tue, Apr 30, 2013 at 8:20 AM, Milan Straka <<a href="mailto:fox@ucw.cz">fox@ucw.cz</a>> wrote:<br>
> Hi all,<br>
><br>
>> -----Original message-----<br>
>> From: Nikita Volkov <<a href="mailto:nikita.y.volkov@gmail.com">nikita.y.volkov@gmail.com</a>><br>
>> Sent: 30 Apr 2013, 17:18<br>
>><br>
>> Because of the above I have very often found myself in requirement for the following function:<br>
>><br>
>> withItem ::<br>
>> (Ord k) =><br>
>> k -><br>
>> (Maybe i -> (r, Maybe i)) -><br>
>> Map k i -> (r, Map k i)<br>
>> withItem k f m =<br>
>> let<br>
>> item = Map.lookup k m<br>
>> (r, item') = f item<br>
>> m' = Map.update (const item') k m<br>
>> in (r, m')<br>
><br>
> last time we talked about adding<br>
> lens :: k -> Map k a -> (Maybe a -> Map k a, Maybe a)<br>
> the performance of the direct implementation was actually worse than<br>
> using lookup+insert or such, see the thread<br>
> <a href="http://www.haskell.org/pipermail/libraries/2012-January/017423.html" target="_blank">http://www.haskell.org/pipermail/libraries/2012-January/017423.html</a><br>
> and the benchmark results at<br>
> <a href="http://www.haskell.org/pipermail/libraries/2012-January/017435.html" target="_blank">http://www.haskell.org/pipermail/libraries/2012-January/017435.html</a><br>
><br>
<br>
</div>If this is a good API, and the direct implementation is slower than an<br>
indirect implementation in terms of lookup+insert+delete, then the<br>
indirect implementation should be exported. Keep in mind that this<br>
operation is just `alterM` (except generalized to Functor --<br>
`alterF`?).<br>
<br>
However: I just wrote a quick direct version:<br>
<br>
alterF :: (Ord k, Functor f) => k -> (Maybe a -> f (Maybe a)) -><br>
Map k a -> f (Map k a)<br>
STRICT_1_OF_2(alterF)<br>
alterF k f = go<br>
where<br>
go Tip = maybe Tip (singleton k) <$> f Nothing<br>
go (Bin sx kx x l r) =<br>
case compare k kx of<br>
LT -> (\l' -> balance kx x l' r) <$> go l<br>
GT -> (\r' -> balance kx x l r') <$> go r<br>
EQ -> maybe (glue l r) (\x' -> Bin sx kx x' l r) <$> f (Just x)<br>
<br>
And benchmarked lookup-via-alterF, insert-via-alterF, etc. -- they<br>
come out much slower. However, if I add an INLINE pragma or SPECIALIZE<br>
pragmas for common/relevant functors (e.g. Const r, Identity, (r,)),<br>
then they come out almost the same speed as the primitive function.<br>
<br>
I don't think INLINE is necessarily bad for this function. (I don't<br>
like the idea of using SPECIALIZE here because I don't think e.g.<br>
Identity should have special privileges over some other newtype with<br>
the same Functor instance.) So maybe the direct implementation should<br>
be reconsidered. I can do a more thorough benchmark later if people<br>
are interested.<br>
<div class="im"><br>
><br>
> I am also a bit worried whether withItem is the "right" general<br>
> function. For example Shachaf Ben-Kiki mentions the<br>
> at :: (Ord k, Functor f) => k -> (Maybe i -> f (Maybe i)) -> Map k i -> f (Map k i)<br>
> from the lens package in other mail, but maybe there are others.<br>
><br>
<br>
</div>I think that alterF almost certainly *a* right function -- it's just a<br>
monadic/functorial version of `alter`, which is the most general<br>
"simple" updating function. Possibly there should be others too, but<br>
this one is useful and general. Although it needs a better name. :-)<br>
<br>
(Note that e.g.<br>
adjustF :: (Ord k, Applicative f) => k -> (a -> f a) -> M.Map k a<br>
-> f (M.Map k a)<br>
can just be<br>
\k -> alterF k . traverse<br>
just as with alter/adjust.<br>
<div class="HOEnZb"><div class="h5">)<br>
<br>
><br>
>> 1. Implement an efficient version of "withItem" for lazy and strict versions of "Map" and "IntMap".<br>
><br>
> Maybe we will need a benchmark to see whether withItem is really faster<br>
> than combination of lookup+update.<br>
><br>
>> 3. Begin the deprecation process of the following functions: insertWith, insertWithKey, insertLookupWithKey, adjust, adjustWithKey, update, updateWithKey, updateLookupWithKey, alter.<br>
><br>
> I am against deprecating insertWith, insertWithKey, updateWithKey,<br>
> updateWithKey, because they are useful.<br>
><br>
> I am against deprecating adjust, adjustWithKey and alter, mostly because<br>
> of compatibility reasons, although I agree that their name is not<br>
> descriptive.<br>
><br>
> I am indifferent about insertLookupWithKey and updateLookupWithKey. It<br>
> would be nice to show that their implementation is really faster than<br>
> lookup+insert / lookup+update combo.<br>
><br>
<br>
</div></div><span class="HOEnZb"><font color="#888888"> Shachaf<br>
</font></span></blockquote></div><br></div>