Proposal: Non-allocating way to iterate over a Data.Map: traverseWithKey_
Edward Kmett
ekmett at gmail.com
Tue Aug 6 19:38:19 CEST 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 <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>
More information about the Libraries
mailing list