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

[Ryan Newton]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/libraries/attachments/20130806/9c5c1f3c/attachment.htm>