Well, I see. It'd be nice. That aside, the absence of traverse_ doesn't seem to be intended (even the documentation for mapM_ says "mapM_ is just traverse_"!) 2015-03-30 16:54 GMT+09:00 Herbert Valerio Riedel :

On 2015-03-30 at 07:05:56 +0200, Fumiaki Kinoshita wrote:

[...]

...

I found out that (<>) (in Data.Monoid) is missing, also. It would be nice to reexamine Prelude to export things we want to export.

Fwiw, (<>) was actually left-out as it wasn't required (it's just a an alias for `mappend`), *and* to keep our options open (or at least not make it more difficult) in terms of possible migration-plans available for the case we'd be moving 'Semigroup' to base/Prelude at some point in the future.

On 2015-03-31 at 06:27:32 +0200, Chris Wong wrote: [...]

While it would be useful to have it in the Prelude, traverse_ doesn't fit either of the motivations above. So I think its omission is intended here.

That is not to say that it can't be proposed for inclusion... IOW, just turn the cautious "'traverse_' is not exported from Prelude [..] Is this intentional?"-question into an explicit/proper library proposal! Cheers, hvr

On Tue, 31 Mar 2015, Joachim Breitner wrote:

At a first glance, the rule "traverse == traverse_" seems to be sound where the resulting program well-typed, as if it is well-typed in both cases, this means that the result was not used.

Of course, an explicit "traverse_" is still useful, but wouldn’t it nevertheless be nice to have a sufficient smart compiler?

If it works it will still surprise programmers if the magic does not happen for a custom function similar to 'traverse'. E.g. I had a data structure with two type parameters and thus two traverse function parameters. I think it is better to tell programmers about the general problem instead of fixing a selection of instances.

In general we don't currently go out of our way to export RULES that risk breakage / semantics changes when the user supplies an instance that merely doesn't satisfy the laws. The only ones that actually come to mind are the ones hiding in Control.Arrow that I don't think anybody has looked at since they were first written. We also have a few around realToFrac that have questionable semantics that are a source of constant semantic pain as well. A fairly exotic, but known, use-case for a Traversable is to exploit the fact that we can extract given the data has a known shape and put the data back in using the same shape. This sits behind a number of tricks in my 'lens' and 'ad' libraries. If you are given a Traversable `f` in as input and spit it back out as output, and you know nothing else about `f`, you can know that the `f` you took in has the same number of entries as the one you spat out. This gives a safe way to reason about zipping things that are derived from the same input, which comes up a lot in the context of 'ad', etc. This is done in one of two ways. 1.) You can linearize the structure and you recover the shape left to right. This runs into the same problem as relying on toList to characterize a Foldable. It ignores infinite cases. (For things like AD where the infinite cases breaks down, thats fine, for other use cases it isn't.) 2.) Or you make an illegal Applicative that captures the structure as it walks in a tree. We can either replay the tree on the same Traversable (2a), or we can build a heavier GADT during construction (2b). Uniplate takes the (2a) approach, lens takes (2b) in e.g. A variant on the construction of http://hackage.haskell.org/package/lens-4.8/docs/src/Control-Lens-Internal-M... for instance can use the ability to 're-walk' a Traversable on the same data type and get exactly the same arrangement of structures (including fmaps) to avoid having to store the structure in a GADT. Your proposed optimization breaks at least the (2a) approach above. The key is don't get to know that `foldMap f` and `getConst . traverse (Const . f)` for a given container build the exact same tree. One might associate differently than the other, and in fact if you supplied a definition of the Foldable in terms of foldr and the Traversable in terms of traverse, this is precisely what happens, so it isn't even an academic exercise. =/ Consequently, the walk to gather all the values in the tree can't be done with traverse_, but can be done with traverse, despite the fact that we're ignoring the result inside the monad. -Edward On Tue, Mar 31, 2015 at 6:43 AM, Joachim Breitner wrote:

Hi,

Am Dienstag, den 31.03.2015, 12:33 +0200 schrieb Henning Thielemann:

...

If it works it will still surprise programmers if the magic does not happen for a custom function similar to 'traverse'. E.g. I had a data structure with two type parameters and thus two traverse function parameters. I think it is better to tell programmers about the general problem instead of fixing a selection of instances. True.

But that is a problem with every compiler optimization. If you have a recursive function taking some Int, the compiler might be able to determine that you use it strictly and unbox it, and great things happen. It will not always figure this out, and if it does not, you have to help it (e.g. using strictness annotations).

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

On an instance by instance basis I have zero objection and it can definitely work fine. -Edward On Tue, Mar 31, 2015 at 7:56 AM, Joachim Breitner wrote:

Hi,

Am Dienstag, den 31.03.2015, 07:04 -0400 schrieb Edward Kmett:

...

Your proposed optimization breaks at least the (2a) approach above.

The key is don't get to know that `foldMap f` and `getConst . traverse (Const . f)` for a given container build the exact same tree. One might associate differently than the other, and in fact if you supplied a definition of the Foldable in terms of foldr and the Traversable in terms of traverse, this is precisely what happens, so it isn't even an academic exercise. =/

This argues against a generic "traverse = traverse_" rule. But how about per-instances rules, for instances where we know that they build the applicative result in the same way?

Greetings, Joachim

-- Joachim “nomeata” Breitner mail@joachim-breitner.de • http://www.joachim-breitner.de/ Jabber: nomeata@joachim-breitner.de • GPG-Key: 0xF0FBF51F Debian Developer: nomeata@debian.org

_______________________________________________ Libraries mailing list Libraries@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

I understand the ground. It seems reasonable not to add symbols facilely. But in this case, the "too specialized" version is exported while more fundamental one is not. Although folks (including me) use mapM_ mostly today, someday we will like to have traverse_, I guess. 2015-03-31 19:41 GMT+09:00 Edward Kmett :

We deliberately took no more symbols than we needed in 7.10 from Prelude as part of the Foldable/Traversable Proposal. There are multiple combinators in Data.Foldable and Data.Traversable that we do not export. traverse_ is one of them as, strictly speaking, traverse_ was a symbol we didn't have to take.

If we had would anybody have complained any more loudly? Not sure... but it was a deliberate choice to not bring in any symbols into Prelude that weren't already there that weren't part of the definition of a class or needed to define instances that already existed.

-Edward

On Mon, Mar 30, 2015 at 11:33 PM, Fumiaki Kinoshita wrote:

...

Well, I see. It'd be nice.

That aside, the absence of traverse_ doesn't seem to be intended (even the documentation for mapM_ says "mapM_ is just traverse_"!)

2015-03-30 16:54 GMT+09:00 Herbert Valerio Riedel :

...

On 2015-03-30 at 07:05:56 +0200, Fumiaki Kinoshita wrote:

[...]

...

I found out that (<>) (in Data.Monoid) is missing, also. It would be nice to reexamine Prelude to export things we want to export.

Fwiw, (<>) was actually left-out as it wasn't required (it's just a an alias for `mappend`), *and* to keep our options open (or at least not make it more difficult) in terms of possible migration-plans available for the case we'd be moving 'Semigroup' to base/Prelude at some point in the future.

_______________________________________________ ghc-devs mailing list ghc-devs@haskell.org http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs