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

[Milan Straka]

> -----Original message-----
> From: Ryan Newton <rrnewton at gmail.com>
> 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