Re: traverse_

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
14 messages Options
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Fumiaki Kinoshita
> Hi,

> I have just installed GHC 7.10.1. I'm a little bit surprised because
> 'traverse_' is not exported from Prelude. But 'traverse' is exported.
> Is this intentional?

> I expected that I can forget xxxM, xxxM_, xxxA, and xxxA_ functions
> with GHC 7.10.1. I want to use 'traverse_' instead of 'mapM_'.

> --Kazu

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

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

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.

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Fumiaki Kinoshita
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 <[hidden email]>:
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.



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Chris Wong-2
Both traverse and mapM_ are in the GHC 7.10 Prelude for specific reasons.

mapM_ was already in the Prelude before the AMP proposal, so it was
grandfathered in.

traverse is required for writing Traversable instances.

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.

On Tue, Mar 31, 2015 at 4:33 PM, Fumiaki Kinoshita <[hidden email]> 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 <[hidden email]>:
>>
>> 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.
>>
>
>
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
>



--
https://lambda.xyz
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Herbert Valerio Riedel
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
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

RULE traverse = traverse_?

Joachim Breitner-2
Hi,

has it been considered that the compiler might be instructed to replace
traverse by traverse_ if the result is not used?

Are the conditions where traverse can be replaced by traverse_
well-defined? Probably not in general, but maybe for individual
Traversable instances? Is this expressible in rules?

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?

Greetings,
Joachim




--
Joachim “nomeata” Breitner
  [hidden email]http://www.joachim-breitner.de/
  Jabber: [hidden email]  • GPG-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RULE traverse = traverse_?

Henning Thielemann


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.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Edward Kmett-2
In reply to this post by Fumiaki Kinoshita
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 <[hidden email]> 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 <[hidden email]>:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: RULE traverse = traverse_?

Joachim Breitner-2
In reply to this post by Henning Thielemann
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
  [hidden email]http://www.joachim-breitner.de/
  Jabber: [hidden email]  • GPG-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: RULE traverse = traverse_?

Edward Kmett-2
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-Magma.html#Molten 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 <[hidden email]> 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
  [hidden email]http://www.joachim-breitner.de/
  Jabber: [hidden email]  • GPG-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: RULE traverse = traverse_?

Joachim Breitner-2
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
  [hidden email]http://www.joachim-breitner.de/
  Jabber: [hidden email]  • GPG-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

signature.asc (836 bytes) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Fumiaki Kinoshita
In reply to this post by Edward Kmett-2
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 <[hidden email]>:
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 <[hidden email]> 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 <[hidden email]>:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs




_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: traverse_

Edward Kmett-2
I have no objection to having the discussion about widening the set of symbols to shave off warts like this in 7.12.

-Edward

On Tue, Mar 31, 2015 at 10:11 AM, Fumiaki Kinoshita <[hidden email]> wrote:
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 <[hidden email]>:
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 <[hidden email]> 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 <[hidden email]>:
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
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-devs





_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: RULE traverse = traverse_?

Edward Kmett-2
In reply to this post by Joachim Breitner-2
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 <[hidden email]> 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
  [hidden email]http://www.joachim-breitner.de/
  Jabber: [hidden email]  • GPG-Key: 0xF0FBF51F
  Debian Developer: [hidden email]

_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries



_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries