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 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).

On Tue, Jul 30, 2013 at 11:32 AM, Milan Straka <fox@ucw.cz> wrote:

Hi Ryan,

> -----Original message-----
> From: Ryan Newton <rrnewton@gmail.com>
> Sent: 30 Jul 2013, 09:35
>
> > (!) 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
> >
>
> So then this becomes a recommendation for the implementation strategy then
> right? (e.g. within containers) Users probably still want a rich set of
> variants, and they need to be packaged somewhere. But it seems like
> there's an argument that deriving these from a small core helps to ensure
> that there are no bugs.
>
> Yet that sounds like a battle for another day. On the topic of this
> proposal -- since Shachaf doesn't object, would you (Johan / Milan) mind
> merging this patch?

I would like to postpone merging for a bit and spend more time
investigating the issue.

I want to investigate why exactly
foldrWithKey (\k a b -> f k a *> b) (pure ())
does not work as I would expect it not to allocate.

I am not convinced that traverseWithKey_ is a good addition to the API
because my original thought was "this is just a fold". The API of
containers has tendency to grow, so I am careful about adding functions
that can be expressed easily using existing ones.

Of course, ability to iterate effectively over the elements of the
containers definitely IS useful, so if I am unable to make the fold work
(or GHC optimizer cannot do it at present), I will merge it.

Cheers,
Milan