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

[Shachaf Ben-Kiki]

On Mon, Jul 29, 2013 at 11:47 AM, Ryan Newton <rrnewton at gmail.com> wrote:
> Shachaf, I checked and Milan's commits that improve traverseWithKey were
> already incorporated when I ran my tests above.  The extra speedup is good
> but doesn't change the O(1) vs. O(N) allocation situation.

Wait, are you saying you couldn't get it to work in constant memory at
all without modifying containers? I didn't actually look at the
benchmarks in much detail before. I just looked at the code -- it
looks like in your latest posted benchmark you don't actually use the
alternate traverseWithKey_ anywhere -- instead you use foldrWithKey
twice (the perils of not compiling with -Wall!). I just ran the
benchmark with the alternate version and it looks like it uses
constant memory.

Maybe I'm misunderstanding. I'm not against adding this to containers,
but it should be clear with such a patch whether it's being added for
necessity or convenience. It looks to me like it's the latter.

(By the way: lens also provides this function, with the name
"itraverse_" (i for indexed). I tried it and it looks like it also
uses constant memory.)

    Shachaf