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

[Ryan Newton]

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 at ucw.cz> wrote:

> Hi Ryan,
>
> > -----Original message-----
> > From: Ryan Newton <rrnewton at 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130730/3bc10095/attachment.htm>