On Mon, Jul 29, 2013 at 11:47 AM, Ryan Newton
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