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

-----Original message----- From: Ryan Newton Sent: 30 Jul 2013, 12:01

Ok, let us know what you find out. I totally agree that Data.Map has gotten pretty cluttered.

But, also, part of my concern is that even if the optimizer does know how to optimize that fold, how does the programmer who needs this kind of routine *know* that it will work? (Especially since we didn't.)

I believe implementing traverseWithKey_ using a foldWithKey is quite natural (you want to go over the elements and do something with them, in this case perform some action on them). I expected it to work and I am surprised it does not. So for me it is the other way around -- I have a function which I expected to behave nice as a fold and it does not. There is probably a reason for that and that may cause addition of traverseWithKey_ to the API.

I think it's a bad habit to for users to stop paying attention to the cost model entirely and instead believe that compiler magic will eliminate everything! Yet exactly that kind of thinking seems to be encouraged by data structure libraries that create unnecessary copies frivolously (esp. with fusion frameworks that sometimes/maybe fix the problem).

Yes, that is true. Nevertheless, it is not easy to think about what will and what will not cause heap allocation in Haskell. Also, heap allocation is quite cheap in Haskell, sometimes faster implementations of containers methods allocate more memory (but we usually do not use them and prefer less allocation). Wanting to avoid allocation sometimes causes to avoid higher order functions and advanced functional techniques, which is also not ideal. Nevertheless, I will try to investigate. Cheers, Milan