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

[Edward Kmett]

On Tue, Aug 6, 2013 at 4:19 PM, Milan Straka <fox at ucw.cz> wrote:

> Hi Edward,
>
> > -----Original message-----
> > From: Edward Kmett <ekmett at gmail.com>
> > Sent: 6 Aug 2013, 14:26
> >
> > On Tue, Aug 6, 2013 at 2:09 PM, Milan Straka <fox at ucw.cz> wrote:
> >
> > > Hi Edward,I am not suggesting we should change the behaviour of
> existing
> > > functions
> > > and traverseWithKey_ should definitely use the same order as
> > > traverseWithKey. Changing semantics without changing type signatures is
> > > really suspicious and usually plainly wrong.
> > >
> >
> > I wholeheartedly agree. =) I was just basing that on the code Ryan
> posted:
> >
> > >   traverseWithKey_ f = go
> > >     where go Tip = pure ()
> > >           go (Bin _ k v l r) = f k v *> go l *> go r
> > >
> > >
> > ... which visits the key/value pairs out of order unlike, say:
> >
> >   go (Bin _ k v l r = go l *> f k v *> go r
>
> Oh, yes, we will definitely use the definition you suggest.
>
> > > Nevertheless, I was wondering whether we should have a monadic fold
> > > (foldrM and foldlM) which would process the elements in a given order
> > > (ascending and descending, analogously to foldr and foldl). From one
> > > point of view, we can implement foldrM and foldlM using foldr and
> foldl,
> > >
> >
> > Sure, foldrM is typically implemented in terms of foldl and foldlM is
> > typically implemented in terms of foldr.
> >
> > Do the usual definitions like that leak on a Map?
>
> It is difficult to say whether it is a 'leak'. These methods (they are
> the same as Foldable.foldrM and Foldable.foldlM) heap-allocate space
> linear in the size of the map (to create the closures). When implemented
> directly, they do not heap-allocate.


Ick. I hadn't walked through the expansion of those by hands and had
admittedly just hoped they worked out of the box.

That means the similar combinators we have for them in lens probably also
leak. =(

This indicates to me we may want to bite the bullet and move foldlM and
foldrM into the Foldable class.

As hideous as that is, the unmitigable space leak strikes me as worse.


> > traverseWithKey_ would normally be implemented with an appropriate
> newtype
> > and foldMapWithKey, rather than traverseWithKey. Does that also leak?
>
> That does not leak, as Shachaf Ben-Kiki pointed out. That is one of the
> reasons why this discussion is so long :)
>
> BTW, Foldable.traverse_ also heap-allocates space linear in the size of
> the map, because it is defined as
>   traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
>   traverse_ f = foldr ((*>) . f) (pure ())
> Maybe it would be better to define it using foldMap + the appropriate
> newtype? Then it would not heap-allocate, at least for Data.Map.
>

Definitely. I'll talk to Shachaf and craft a suitable proposal to fix up
traverse_.

-Edward
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130806/d709e1e9/attachment.htm>