foldl' semantic change

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

foldl' semantic change

David Feuer

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things:

1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice).

2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays.

3. The containers package should be consistent with base in this regard.


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

Re: foldl' semantic change

Bart Massey
-1 on retaining this. Part of the implied contract of Data.List is that all functions be as lazy as possible. Besides, a change that potentially breaks old programs that use foldl' seems like a bad idea unless there's a really strong reason for it. I don't have an existing example offhand, but it seems at least possible that something like

    last = foldl' (flip const) undefined

is out there...

On Fri, Jun 10, 2016 at 5:29 AM David Feuer <[hidden email]> wrote:

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things:

1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice).

2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays.

3. The containers package should be consistent with base in this regard.

_______________________________________________
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: foldl' semantic change

David Feuer

I would certainly have agreed back when 4.8 was in development. This was undoubtedly a breaking change. The fact that it's now been out for some time muddies the waters. So does the fact that the strictness has never been documented. It seems likely that most packages relying on the old behavior have been updated, and it's possible that some may have come to rely on it. I see this unfortunate situation as something of an opportunity to take a fresh look and decide what we want.

On the pro-revert side,

foldl'new f b xs = b `seq` foldl'old f b xs

which seems considerably less challenging than implementing the lazy version from scratch with the built-in GHC magic. But there could be times when that leads to some efficiency problem.

On Jun 10, 2016 12:10 PM, "Bart Massey" <[hidden email]> wrote:
-1 on retaining this. Part of the implied contract of Data.List is that all functions be as lazy as possible. Besides, a change that potentially breaks old programs that use foldl' seems like a bad idea unless there's a really strong reason for it. I don't have an existing example offhand, but it seems at least possible that something like

    last = foldl' (flip const) undefined

is out there...

On Fri, Jun 10, 2016 at 5:29 AM David Feuer <[hidden email]> wrote:

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things:

1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice).

2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays.

3. The containers package should be consistent with base in this regard.

_______________________________________________
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: foldl' semantic change

Herbert Valerio Riedel
In reply to this post by David Feuer
On 2016-06-10 at 14:29:47 +0200, David Feuer wrote:

[...]

> 3. The containers package should be consistent with base in this regard.

for the record, `containers` appears to follow the new stricter
semantics for lists at least since 2014:

  https://mail.haskell.org/pipermail/libraries/2014-November/024081.html

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

Re: foldl' semantic change

David Feuer

That may be true for most of it, but Data.Sequence has been using the Foldable defaults. That's going to change in the next version, but unless I goofed up the semantics remain the same.

On Jun 10, 2016 12:59 PM, "Herbert Valerio Riedel" <[hidden email]> wrote:
On 2016-06-10 at 14:29:47 +0200, David Feuer wrote:

[...]

> 3. The containers package should be consistent with base in this regard.

for the record, `containers` appears to follow the new stricter
semantics for lists at least since 2014:

  https://mail.haskell.org/pipermail/libraries/2014-November/024081.html


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

Re: foldl' semantic change

Bart Massey
In reply to this post by David Feuer
I guess by "packages may have come to rely on it" you mean some situation where performance is improved by the implicit strictness? It's hard for me to imagine relying on getting bottom instead of a result. However, it's also hard for me to imagine relying on foldl' forcing the initial value in the case of folding on an empty list, and in non-empty list cases the folding function is likely going to be strict on the accumulator anyhow. (The last example I gave is an exception to that rule.)

As to the lack of documentation of laziness, my understanding is that functions in Data.List are expected to be lazy anywhere that their strictness is not explicitly documented? I don't know if there's actually language like that in any of the Reports, but the Haddock for Data.List says, among other things:

> For a general Foldable structure this should be semantically identical to,
foldl f z = foldl' f z . toList
which doesn't seem to be actually the case right now, but does seem to be desirable. (Is the prime on the wrong side here? This seems backward to me, but I'm easily confused.)

Anyhow, I'll be disappointed if it remains no longer viable to write  last = foldl' (flip const) undefined  as I did above. It makes the language harder to teach, and is nonintuitive to me.

On Fri, Jun 10, 2016 at 9:35 AM David Feuer <[hidden email]> wrote:

I would certainly have agreed back when 4.8 was in development. This was undoubtedly a breaking change. The fact that it's now been out for some time muddies the waters. So does the fact that the strictness has never been documented. It seems likely that most packages relying on the old behavior have been updated, and it's possible that some may have come to rely on it. I see this unfortunate situation as something of an opportunity to take a fresh look and decide what we want.

On the pro-revert side,

foldl'new f b xs = b `seq` foldl'old f b xs

which seems considerably less challenging than implementing the lazy version from scratch with the built-in GHC magic. But there could be times when that leads to some efficiency problem.

On Jun 10, 2016 12:10 PM, "Bart Massey" <[hidden email]> wrote:
-1 on retaining this. Part of the implied contract of Data.List is that all functions be as lazy as possible. Besides, a change that potentially breaks old programs that use foldl' seems like a bad idea unless there's a really strong reason for it. I don't have an existing example offhand, but it seems at least possible that something like

    last = foldl' (flip const) undefined

is out there...

On Fri, Jun 10, 2016 at 5:29 AM David Feuer <[hidden email]> wrote:

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things:

1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice).

2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays.

3. The containers package should be consistent with base in this regard.

_______________________________________________
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: [core libraries] Re: foldl' semantic change

Eric Mertens
Regarding implementing last with foldl, this is exactly the time you would not use foldl' but would only use foldl. Implementing last with foldl' will force all of the elements of the list on the way to returning the last element.

Best regards,
Eric Mertens
glguy

On Fri, Jun 10, 2016 at 10:40 AM Bart Massey <[hidden email]> wrote:
I guess by "packages may have come to rely on it" you mean some situation where performance is improved by the implicit strictness? It's hard for me to imagine relying on getting bottom instead of a result. However, it's also hard for me to imagine relying on foldl' forcing the initial value in the case of folding on an empty list, and in non-empty list cases the folding function is likely going to be strict on the accumulator anyhow. (The last example I gave is an exception to that rule.)

As to the lack of documentation of laziness, my understanding is that functions in Data.List are expected to be lazy anywhere that their strictness is not explicitly documented? I don't know if there's actually language like that in any of the Reports, but the Haddock for Data.List says, among other things:

> For a general Foldable structure this should be semantically identical to,
foldl f z = foldl' f z . toList
which doesn't seem to be actually the case right now, but does seem to be desirable. (Is the prime on the wrong side here? This seems backward to me, but I'm easily confused.)

Anyhow, I'll be disappointed if it remains no longer viable to write  last = foldl' (flip const) undefined  as I did above. It makes the language harder to teach, and is nonintuitive to me.

On Fri, Jun 10, 2016 at 9:35 AM David Feuer <[hidden email]> wrote:

I would certainly have agreed back when 4.8 was in development. This was undoubtedly a breaking change. The fact that it's now been out for some time muddies the waters. So does the fact that the strictness has never been documented. It seems likely that most packages relying on the old behavior have been updated, and it's possible that some may have come to rely on it. I see this unfortunate situation as something of an opportunity to take a fresh look and decide what we want.

On the pro-revert side,

foldl'new f b xs = b `seq` foldl'old f b xs

which seems considerably less challenging than implementing the lazy version from scratch with the built-in GHC magic. But there could be times when that leads to some efficiency problem.

On Jun 10, 2016 12:10 PM, "Bart Massey" <[hidden email]> wrote:
-1 on retaining this. Part of the implied contract of Data.List is that all functions be as lazy as possible. Besides, a change that potentially breaks old programs that use foldl' seems like a bad idea unless there's a really strong reason for it. I don't have an existing example offhand, but it seems at least possible that something like

    last = foldl' (flip const) undefined

is out there...

On Fri, Jun 10, 2016 at 5:29 AM David Feuer <[hidden email]> wrote:

The semantics of foldl' for lists were changed between base 4.7 and base 4.8. Specifically, foldl' became strict in the initial value of its accumulator. I opened http://ghc.haskell.org/trac/ghc/ticket/12173 to report this. The change was entirely accidental, according to Joachim Breitner. However, Duncan Coutts indicated he is pleased with the change. I don't personally have a dog in this race, but I feel very strongly about three things:

1. The strictness should be fully documented, both in Haddock and the next Haskell Report (the Haskell 2010 Report does not go into sufficient detail to support either choice).

2. There should be *one* meaning of foldl' in base. Thus the default Foldable instance should match the ones for lists and arrays.

3. The containers package should be consistent with base in this regard.

_______________________________________________
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: foldl' semantic change

wren romano
In reply to this post by Bart Massey
On Fri, Jun 10, 2016 at 1:40 PM, Bart Massey <[hidden email]> wrote:
> It's hard for me to imagine relying on getting bottom instead of a result.

Thanks to the presence of extensible exceptions, some people may do
things like (foldl' f (throw blah)) and then catch the exception
further up. It's terrible, I know. Using explicit continuations would
be much cleaner. But still, it is what it is


> However, it's also
> hard for me to imagine relying on foldl' forcing the initial value in the
> case of folding on an empty list, and in non-empty list cases the folding
> function is likely going to be strict on the accumulator anyhow.

The main issue I see here is a sort of inference issue. That is, if
the initial value to fold' is marked as lazy then we might build up
some huge thunk which must in practice actually get forced; whereas if
the initial value is strict then we can percolate the knowledge of
that strictness further up, potentially evaluating things more eagerly
and thus avoiding the overhead of thunking, allocation, etc.

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