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

Shachaf Ben-Kiki shachaf at
Tue Jul 30 06:28:10 CEST 2013

On Mon, Jul 29, 2013 at 8:57 PM, Ryan Newton <rrnewton at> wrote:
> Oops, that was sloppy.  Yes, your version does get the job done without
> allocating.  The corrected test is attached to this email.
> The lens interface does look quite full featured!  And it's nice to see that
> it consistently includes '_' variants.  I cite that as additional evidence
> for the norm ;-).
> Personally, I still want traverseWithKey_ for convenience, especially
> because the solution you used is non-obvious.  I imagine many Data.Map users
> would not come up with it (as the rest of us on this thread didn't).

Sure, putting it in containers is fine. I just want to mention that
these kinds of functions are very general-purpose. In particular,
using just traverseWithKey and the proposed alterF, you can implement
at least all of:

(!) adjust adjustWithKey alter delete empty findWithDefault foldl
foldl' foldlWithKey foldlWithKey' foldr foldr' foldrWithKey
foldrWithKey' insert insertLookupWithKey insertWith insertWithKey
lookup map mapAccum mapAccumRWithKey mapAccumWithKey mapMaybe
mapMaybeWithKey mapWithKey member notMember toList update
updateLookupWithKey updateWithKey

With optimal asymptotic behavior and, in many cases, with
just-about-optimal constant factors too (this is essentially what lens
does). But adding this function directly to containers for
completeness seems reasonable.


More information about the Libraries mailing list