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

[Simon Peyton-Jones]

Sounds neat!  Is nested CPR analysis on a branch?

Not yet.. on my laptop only so far.

I've lost context on this traverseWithKey_ thread.  If you or Milan need my help, could you start again, stating the problem with a standalone test case?  I gather from Milan that may there isn't a problem, or at least not a problem that GHC can reasonably solve.  If there's nothing to follow up, no need to reply.  Thanks

Simon

From: Ryan Newton [mailto:rrnewton at gmail.com]
Sent: 06 August 2013 14:51
To: Sjoerd Visscher
Cc: Milan Straka; Simon Peyton-Jones; Haskell Libraries
Subject: Re: Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_

On Sat, Aug 3, 2013 at 5:31 PM, Simon Peyton-Jones <simonpj at microsoft.com<mailto: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<mailto: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/20130816/e75070bc/attachment.htm>