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

6 Aug 2013

      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  wrote:
...
On Sat, Aug 3, 2013 at 5:31 PM, Simon Peyton-Jones 
 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 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@haskell.org
http://www.haskell.org/mailman/listinfo/libraries

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

Edward Kmett