Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

[Shachaf Ben-Kiki]

On Tue, Jul 2, 2013 at 1:46 PM, Ryan Newton <rrnewton at gmail.com> wrote:
>
>>     foldMapWithKey :: Monoid r => (k -> a -> r) -> M.Map k a -> r
>>     foldMapWithKey f = getConst . M.traverseWithKey (\k x -> Const (f k
>> x))
>
>
> Shachaf, thanks for fleshing it out.  I updated the test with your version
> as well:
>
>    https://gist.github.com/rrnewton/5912908
>
> In short, it performs exactly the same as the foldrWithKey version, as you
> pointed out (32M allocation).
>
> In both cases, using first class monadic/applicative values seems to foil
> GHC.
>
> And btw, these do show the scaling you would expect, on 2M elements, it
> allocates 64MB, 4M -> 128MB, and so on, whereas the traverseWithKey_ version
> allocates a constant amount.
>
>   -Ryan
>

If you're actually benchmarking it, you should note a few things:

* As I mentioned, lens's actual implementation of this function is
slightly different:

    -- The argument 'a' of the result should not be used!
    newtype Traversed a f = Traversed { getTraversed :: f a }
    instance Applicative f => Monoid (Traversed a f) where
      mempty = Traversed (pure (error "Traversed: value used"))
      Traversed ma `mappend` Traversed mb = Traversed (ma *> mb)

with one "void" applied at the very end of the fold, instead of one in
each step. This may or may not be better; it should probably be
measured.

* Following a discussion with Milan off-list, he implemented a simple
optimization in traverseWithKey which might have a significant impact.
See https://github.com/haskell/containers/commit/4d24ff5d08f0bb27ca73a9888286d6426149515b
. It should probably be considered in these benchmarks.

* I haven't thought it through, but it's possible that using a
"difference monoid" -- i.e. folding with Endo, the way
Data.Foldable.foldr is implemented by default -- would also be useful
to measure, to compare with the existing foldrWithKey.

    Shachaf