Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_
Shachaf Ben-Kiki
shachaf at gmail.com
Fri Jul 5 09:51:19 CEST 2013
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
More information about the Libraries
mailing list