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

Edward Kmett ekmett at
Tue Aug 6 20:26:01 CEST 2013

On Tue, Aug 6, 2013 at 2:09 PM, Milan Straka <fox at> wrote:

> Hi Edward,I am not suggesting we should change the behaviour of existing
> functions
> and traverseWithKey_ should definitely use the same order as
> traverseWithKey. Changing semantics without changing type signatures is
> really suspicious and usually plainly wrong.

I wholeheartedly agree. =) I was just basing that on the code Ryan posted:

>   traverseWithKey_ f = go
>     where go Tip = pure ()
>           go (Bin _ k v l r) = f k v *> go l *> go r
... which visits the key/value pairs out of order unlike, say:

  go (Bin _ k v l r = go l *> f k v *> go r

> Nevertheless, I was wondering whether we should have a monadic fold
> (foldrM and foldlM) which would process the elements in a given order
> (ascending and descending, analogously to foldr and foldl). From one
> point of view, we can implement foldrM and foldlM using foldr and foldl,

Sure, foldrM is typically implemented in terms of foldl and foldlM is
typically implemented in terms of foldr.

Do the usual definitions like that leak on a Map?

foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m
bfoldrM f z0 xs = foldl f' return xs z0  where f' k x z = f x z >>= k

foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m
afoldlM f z0 xs = foldr f' return xs z0  where f' x k z = f z x >>= k

nevertheless using linear heap space complexity compared to constant
> heap space complexity we can achieve with specialized implementations.
> This is the same situation as traverseWithKey_ -- we can implement it
> using traverseWithKey, but the heap space complexity increases.

traverseWithKey_ would normally be implemented with an appropriate newtype
and foldMapWithKey, rather than traverseWithKey. Does that also leak?

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the Libraries mailing list