traverseWithKey_?

[ocharles]

Any interest in having traverseWithKey_? I want to run walk a monadic action over a Map, but I don't care about its results. Seems like a waste to actually build up a Map of (), only to throw it away.

[treeowl]

We could, and we probably should (to be sure to get as efficient an implementation as possible), but there are several ways to do it using foldMapWithKey with an appropriate Monoid instance.

[ocharles]

I thought that might be the case, but I wasn't sure if that would still end up creating a load of garbage. I'll try that. (For context, I have a bunch of nested maps (Map Cull (PassList (Map UseLightMapUV (Map Texture0Name (Map (SourceBlend, DestBlend) (Map TextureTransformation (Map DepthFunction (IO ())))))))) that describes how to draw an OpenGL scene - I want to traverse this producing actual OpenGL state transitions. The Map structure is to give me an efficient way to batch operations in common state).

[treeowl]

Another complication: the definition of traverse_ in Data.Foldable uses foldr, which is great for traversing lists, and great for traversing any structure with a "strict" applicative, but lousy otherwise. Do we follow its example, or use something more "natural" that may be worse for some important applicatives?

[treeowl]

This monoid will give you one piece of garbage per element, but should toss the garbage quickly:

data Apl f = forall a. Apl (f a)
instance Applicative f => Monoid (Apl f) where
  mempty = Apl (pure ())
  mappend (Apl xs) (Apl ys) = Apl (xs *> ys)
runApl :: Functor f => Apl f -> f ()
runApl (Apl xs) = void xs

[treeowl]

The foldr approach is probably better in many/most practical cases, I suspect.

[treeowl]

Go with that:

traverseWithKey_ f n = foldrWithKey .....

[ocharles]

foldrWithKey with Apl, that is (over foldMapWithKey?)

[treeowl]

Sorry, I meant those as alternatives. For typical things like IO and strict ST, just use traverseWithKey_ f n = foldrWithKey (\k a r -> f k a *> r) (pure ()) For an Applicative that you want to apply in a "balanced" fashion (e.g., one that performs actions concurrently, or that builds a tree purely), use the funny monoid approach.

…

On Apr 1, 2017 6:28 PM, "Oliver Charles" ***@***.***> wrote: foldrWithKey with Apl, that is (over foldMapWithKey?) — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#422 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_ZMinTGHU-sa5PUTvaIkxwTedUAOks5rrs9vgaJpZM4MwnTn> .

[ocharles]

Oh I see, thanks!

…

On Sun, 2 Apr 2017, 12:29 am David Feuer, ***@***.***> wrote: Sorry, I meant those as alternatives. For typical things like IO and strict ST, just use traverseWithKey_ f n = foldrWithKey (\k a r -> f k a *> r) (pure ()) For an Applicative that you want to apply in a "balanced" fashion (e.g., one that performs actions concurrently, or that builds a tree purely), use the funny monoid approach. On Apr 1, 2017 6:28 PM, "Oliver Charles" ***@***.***> wrote: > foldrWithKey with Apl, that is (over foldMapWithKey?) > > — > You are receiving this because you commented. > Reply to this email directly, view it on GitHub > <#422 (comment) >, > or mute the thread > < https://github.com/notifications/unsubscribe-auth/ABzi_ZMinTGHU-sa5PUTvaIkxwTedUAOks5rrs9vgaJpZM4MwnTn > > . > — You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub <#422 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AABRjjgpGOFCn85sv3-CmBWCDyxBfqKLks5rrt3kgaJpZM4MwnTn> .

[mikeplus64]

newtype Apl f a = Apl (f a) with instance (Applicative f, Monoid a) => Monoid (Apl f a) ought to work a little better -- there is no Apl constructor garbage, anyway. Or even simpler, newtype Apl f = Apl (f ()) with the exact same monoid instance as in @treeowl's comment.

At least for using foldMapWithKey, anyhow.

[treeowl]

Producing an `f ()` from an `f a` requires `<$`, which is not always free. Using that `Monoid` forces you to do so for each element. The (much more generally useful; I've been proposed adding it to `Data.Monoid` myself) first version has exactly the same problem. You need to convert them all to some `Monoid`, which might as well be `()`. The nasty existential version makes garbage, but potentially much less than the other versions. On Apr 5, 2017 12:37 AM, "Mike Ledger" <[email protected]> wrote: newtype Apl f a = Apl (f a) with instance (Applicative f, Monoid a) => Monoid (Apl f a) ought to work a little better -- there is no Apl constructor garbage, anyway. Or even simpler, newtype Apl f = Apl (f ()) with the exact same monoid instance as in @treeowl <https://github.com/treeowl>'s comment. — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#422 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ABzi_e_Iuh7ZThp0kPGdYbG_QMfBRbA9ks5rsxqEgaJpZM4MwnTn> .

[mikeplus64]

Ah, I see.

(More than anything though I think that's a fair argument for traverse_ :: (a -> f ()) -> f a -> f () ... I think I can remember the haskell-cafe thread about this. Maybe a very dumb rewrite rule like () <$ (b :: f ()) = b could sidestep the problem entirely)

[OlivierSohn]

Hello,

I would need that function too! Before reading this thread, I chose to go with:

void $ traverseWithKey

but now I understand that I could have done:

traverseWithKey_ f = foldrWithKey (\k a r -> f k a *> r) (pure ())

I wonder if GHC with optimizations would "see" that I don't use the returned map in the first case, and then generate the same code as with the second version. I guess I'd have to look at the core to know :)

[sjakobi]

foldlWithKey' (\acc k v -> acc *> f k v) (pure ()) seems to work well for dhall.

EDIT: That should be foldlWithKey' (\acc k v -> acc <* f k v) (pure ()) given a function of type (a -> f b).

[treeowl]

@sjakobi I'm extremely wary of strict folds in contexts that look like this. They're usually not the right kind of strict.

[sjakobi]

@treeowl Thanks for the heads-up! Dhall uses this function for typechecking which seems to be a case where you want to optimize for success, i.e. a complete traversal.

I just tried the foldrWithKey variant, which turned out 7-20% slower.

[sjakobi]

Maybe I should add a prime to mark the strictness to that variant.

[3noch]

I'm just curious how itraverse_ from lens does this / compares.

[sjakobi]

Related: haskell-unordered-containers/unordered-containers#108

[meooow25]

Here's an idea:

data WithKey ka where
  WithKey :: !(Map k a) -> WithKey (k, a)

instance Foldable WithKey where
  foldr f z (WithKey m) = ...
  foldMap f z (WithKey m) = ...
  ...

Now we don't need to redefine every Foldable utility for Map.

printAssocs :: (Show k, Show a) => Map k a -> IO ()
printAssocs m = Data.Foldable.traverse_ (\(k,x) -> print (k,x)) (WithKey m)

There are a couple of problems with this though.

1. It needs GADTs, which is not portable (this also came up in More efficient folds for Seq #1036)
2. WithKey cannot be a newtype today (https://gitlab.haskell.org/ghc/ghc/-/wikis/newtype-optimization-for-gadts), which means it has a cost if it's kept around. Though if you immediately create and use it, it will likely get optimized away.

[treeowl]

It certainly looks elegant.

[konsumlamm]

indexed-traversable has itraverse_ for this, which is implemented using ifoldMap (i.e. foldMapWithKey), see https://hackage.haskell.org/package/indexed-traversable-0.1.4/docs/src/Data.Foldable.WithIndex.html#itraverse_.

[meooow25]

indexed-traversable seems like a decent solution. The implementation is good and the library has no non-GHC-boot deps. I think we can just recommend people use it for derived folds-with-key, unless someone really insists on having it in containers.