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

[Edward Kmett]

traverse and traverse_ visit elements in the same order as foldMap and
foldr up to the Monoid/Applicative laws permitting (finite) reassociation
and unit mapping.

It would stand to reason that traverseWithKey, traverseWithKey_,
foldMapWithKey and foldrWithKey should retain that relationship.

I don't particularly care about what the order is, but that said, if you
start breaking the invariant of the current ordering, you'll silently break
a lot of people's code while still permitting it to typecheck.

This means that the errors will be insidious and difficult to find. e.g.
the lens-based zipper code for walking into a Map will silently break and
I'm sure I'm not the only one who has taken advantage of the existing
ordering on these combinators.

-Edward

On Tue, Aug 6, 2013 at 9:51 AM, Ryan Newton <rrnewton at gmail.com> wrote:

> On Sat, Aug 3, 2013 at 5:31 PM, Simon Peyton-Jones <simonpj at microsoft.com>
>  wrote:
>
>> > Fixing this involves **nested** CPR analysis, which I am working on at
> the moment.
> Sounds neat!  Is nested CPR analysis on a branch?
>
>> This one I do not understand. Could you pull out the two alternative ways
>> of phrasing this algorithm into a standalone form, in which one allocates
>> more than t’other?  Then I could investigate more easily.
>>
> Milan pasted the relevant code (thanks) for traverseWithKey_ vs.
> foldWithKey which I reattach at the bottom of this email.
>
> On Sun, Aug 4, 2013 at 7:48 AM, Sjoerd Visscher <sjoerd at w3future.com>wrote:
>>
>> Would it help if traverse_ was implemented with foldMap using the
>> Traverse_ newtype? In which case maybe we should fix Data.Foldable!
>>
>
> That sounds good to me!  And straightforward.  Any objections?
>
> Milan, why does it bother you that there is no specified order?  I'm
> perfectly happy as long as its deterministic on a particular machine.  (I
> have never been sure whether pure code in Haskell must be deterministic
> across multiple machines... numCapabilities was a counter example for a
> long time.)  Aren't we already used to using Data.Map.toList and
> Data.Set.toList where order is not specified?  Further, other languages
> (like Scheme) have maps/folds that do not specify order of side effects.
>
>   -Ryan
>
> P.S.: Relevant code:
>
> traverseWithKey_ :: Applicative t => (k -> a -> t b) -> Map k a -> t ()
>   traverseWithKey_ f = go
>     where go Tip = pure ()
>           go (Bin _ k v l r) = f k v *> go l *> go r
>
>   foldrWithKey :: (k -> a -> b -> b) -> b -> Map k a -> b
>   foldrWithKey f z = go z
>     where go z' Tip = z'
>           go z' (Bin _ kx x l r) = go (f kx x (go z' r)) l
>
> and we call them like this:
>   let actionTraverse _k 1000000 = putStrLn "Hit 1000000"
>       actionTraverse _k _v = return ()
>   in traverseWithKey_ actionTraverse map
>
> and this:
>   let actionFoldr _k 1000000 z = putStrLn "Hit 1000000" *> z
>       actionFoldr _k _v z = z
>   in foldrWithKey actionFoldr (pure ()) map
>
>
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130806/63f2c045/attachment.htm>