[Proposal] Strict `sum` and `product`

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

[Proposal] Strict `sum` and `product`

Hécate
My fellow Haskell developers, contributors and maintainers,

I wish to present what is certainly a controversial proposal for the
`base` library:
    Making the `sum` and `product` functions from the `base` library strict.

This is not a new question, the debate is old, but I am personally
convinced that the existence of those two lazy functions is something
that should never have happened.
One of the first goals that led to the creation of Haskell was to enable
collaboration and research in the domain of lazy (or non-strict)
programming languages and techniques.
While it led to the discovery of new methods and ways to represent
programs, we also realised that this paradigm has proven to produce
sub-optimal implementations for
these functions.

And while maintaining backward compatibility *is* important when
designing and maintaining a programming language, we have thankfully
developed deprecation mechanisms
that can be used to signal that bad, or sub-optimal decisions of the
past can be corrected.

To refresh our collective memory, here is the current state of things,
regarding `sum`:

```
❯ ghci +RTS -M1024m
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
λ❯ sum [1..10^9]
*** Exception: heap overflow
```
Whereas, with an alternative implementation, such as `foldl'`:
```
λ❯ foldl' (+) 0 [1..10^9]
500000000500000000
(31.35 secs, 88,000,076,288 bytes)
```

I do not think a heap overflow, and the underlying space leak occasioned
by the laziness of `foldl`, are behaviours we should aim to preserve for
the sake of backward compatibility.

And actually, I think that moving these two functions to a strict, space
leak-free implementation would benefit the lazy PL research domain by
showing a good counter-example
of why it is not necessarily suitable for every kind of computation.
I also think, and this is rooted from experience, that we must strive to
empower our users with the power of laziness. Not burden them with it.
Standing on the shoulders of giants is what made Haskell so great, but
this should not prevent us from spreading our wings to go higher.

———

Now, there have been Prelude replacements (such as Relude) and companion
libraries (like `strict`) who have been shipping such alternative
implementations for quite some time now.

A point that can be raised is: Why should we bother? Isn't `strict`
already enough?
To this I answer: `strict` and Relude, ultimately, patches on an tire's
inner tube. We may be able to roll with them for some distance, but
their very existence is a response to an abnormal situation that we have
grown to accept.
However, any bicycle rider who has the means to change their tire should
do so.
I believe we have the means to do so.

Another point that could be raised as well is the fact that this
implementation change would deviate from the 2010 Haskell Report[0].
If we want to stay true to the spirit and letter of the Report, this is
actually a non-issue. Indeed, it is noted that:

> This  report  defines  the  syntax  for Haskell  programs and  an
informal  abstract  semantics  for  the  meaning of such programs.  We
leave as implementation dependent the ways in which Haskell programs are
to be manipulated, interpreted, compiled, etc. This includes such issues
as the nature of programming environments and the error messages
returned for undefined programs (i.e. programs that formally evaluate
to⊥).[1]

As well as in chapter 9:

> In this chapter the entire Haskell Prelude is given. It constitutes a
specification for the Prelude. Many of the definitions are written with
clarity rather than efficiency in mind, and it is not required that the
specification be implemented as shown here.[2]

And finally, regarding the non-strict nature of Haskell, the Report
references strict evaluation to avoid "unneeded laziness."[3]
Thus it was expected that laziness would not be a silver bullet, and it
could harm performance.

———

Regarding the implementation detail, `sum` and `product` would
piggy-back on the already-present `foldMap'` function.


Thank you very much for reading,
I believe we can all go together towards improving the experience of
Haskell developers, starting with this.

[0]: Haskell 2010 Language Report,
https://www.haskell.org/definition/haskell2010.pdf
[1]: Haskell 2010 Language Report, page 3
[2]: Haskell 2010 Language Report, Chapter 9 Standard Prelude, page 105
[3]: Haskell 2010 Language Report, Section 6.2 Strict Evaluation, page 75

--
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

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

Re: [Proposal] Strict `sum` and `product`

Vanessa McHale-2
For my own edification, what happens in actual code? i.e. not GHCi

Cheers,
Vanessa McHale

On 10/18/20 1:13 PM, Hécate wrote:

> My fellow Haskell developers, contributors and maintainers,
>
> I wish to present what is certainly a controversial proposal for the
> `base` library:
>    Making the `sum` and `product` functions from the `base` library
> strict.
>
> This is not a new question, the debate is old, but I am personally
> convinced that the existence of those two lazy functions is something
> that should never have happened.
> One of the first goals that led to the creation of Haskell was to
> enable collaboration and research in the domain of lazy (or
> non-strict) programming languages and techniques.
> While it led to the discovery of new methods and ways to represent
> programs, we also realised that this paradigm has proven to produce
> sub-optimal implementations for
> these functions.
>
> And while maintaining backward compatibility *is* important when
> designing and maintaining a programming language, we have thankfully
> developed deprecation mechanisms
> that can be used to signal that bad, or sub-optimal decisions of the
> past can be corrected.
>
> To refresh our collective memory, here is the current state of things,
> regarding `sum`:
>
> ```
> ❯ ghci +RTS -M1024m
> GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
> λ❯ sum [1..10^9]
> *** Exception: heap overflow
> ```
> Whereas, with an alternative implementation, such as `foldl'`:
> ```
> λ❯ foldl' (+) 0 [1..10^9]
> 500000000500000000
> (31.35 secs, 88,000,076,288 bytes)
> ```
>
> I do not think a heap overflow, and the underlying space leak
> occasioned by the laziness of `foldl`, are behaviours we should aim to
> preserve for the sake of backward compatibility.
>
> And actually, I think that moving these two functions to a strict,
> space leak-free implementation would benefit the lazy PL research
> domain by showing a good counter-example
> of why it is not necessarily suitable for every kind of computation.
> I also think, and this is rooted from experience, that we must strive
> to empower our users with the power of laziness. Not burden them with it.
> Standing on the shoulders of giants is what made Haskell so great, but
> this should not prevent us from spreading our wings to go higher.
>
> ———
>
> Now, there have been Prelude replacements (such as Relude) and
> companion libraries (like `strict`) who have been shipping such
> alternative implementations for quite some time now.
>
> A point that can be raised is: Why should we bother? Isn't `strict`
> already enough?
> To this I answer: `strict` and Relude, ultimately, patches on an
> tire's inner tube. We may be able to roll with them for some distance,
> but their very existence is a response to an abnormal situation that
> we have grown to accept.
> However, any bicycle rider who has the means to change their tire
> should do so.
> I believe we have the means to do so.
>
> Another point that could be raised as well is the fact that this
> implementation change would deviate from the 2010 Haskell Report[0].
> If we want to stay true to the spirit and letter of the Report, this
> is actually a non-issue. Indeed, it is noted that:
>
>> This  report  defines  the  syntax  for Haskell  programs and  an
> informal  abstract  semantics  for  the  meaning of such programs.  We
> leave as implementation dependent the ways in which Haskell programs
> are to be manipulated, interpreted, compiled, etc. This includes such
> issues as the nature of programming environments and the error
> messages returned for undefined programs (i.e. programs that formally
> evaluate to⊥).[1]
>
> As well as in chapter 9:
>
>> In this chapter the entire Haskell Prelude is given. It constitutes a
> specification for the Prelude. Many of the definitions are written
> with clarity rather than efficiency in mind, and it is not required
> that the specification be implemented as shown here.[2]
>
> And finally, regarding the non-strict nature of Haskell, the Report
> references strict evaluation to avoid "unneeded laziness."[3]
> Thus it was expected that laziness would not be a silver bullet, and
> it could harm performance.
>
> ———
>
> Regarding the implementation detail, `sum` and `product` would
> piggy-back on the already-present `foldMap'` function.
>
>
> Thank you very much for reading,
> I believe we can all go together towards improving the experience of
> Haskell developers, starting with this.
>
> [0]: Haskell 2010 Language Report,
> https://www.haskell.org/definition/haskell2010.pdf
> [1]: Haskell 2010 Language Report, page 3
> [2]: Haskell 2010 Language Report, Chapter 9 Standard Prelude, page 105
> [3]: Haskell 2010 Language Report, Section 6.2 Strict Evaluation, page 75
>

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

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

Re: [Proposal] Strict `sum` and `product`

Hécate

Hi Vanessa, thanks for the question.

I compiled the following code:

```
module Main where              
                               
main = do                      
  let result = sum [1..10^9]     
  print result                   
```

with the following command:

ghc -rtsopts -On --make Main.hs

and ran the binary like that:

./Main +RTS -M1024m -RTS

Compiled with -O0, the heap overflows

Starting with -O1, it runs fine.

However:

I am not able to tell you what kind of optimisation is responsible for this,
and to be quite honest, I don't see why we should trust the optimiser to produce behaviours that could be upstreamed; behaviour that  is enabled at the first sign of optimisation.

I am not fundamentally opposed to the concept of having neat optimisations in GHC, but experience tells me that
1. They can (and will) regress
2. They can (and will) interact in weird ways
3. This naked call gets optimised, that's great, but how will it react with other Foldables, with fusion, etc?

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

Cheers!

On 18/10/2020 20:46, Vanessa McHale wrote:
For my own edification, what happens in actual code? i.e. not GHCi

Cheers,
Vanessa McHale

On 10/18/20 1:13 PM, Hécate wrote:
My fellow Haskell developers, contributors and maintainers,

I wish to present what is certainly a controversial proposal for the
`base` library:
   Making the `sum` and `product` functions from the `base` library
strict.

This is not a new question, the debate is old, but I am personally
convinced that the existence of those two lazy functions is something
that should never have happened.
One of the first goals that led to the creation of Haskell was to
enable collaboration and research in the domain of lazy (or
non-strict) programming languages and techniques.
While it led to the discovery of new methods and ways to represent
programs, we also realised that this paradigm has proven to produce
sub-optimal implementations for
these functions.

And while maintaining backward compatibility *is* important when
designing and maintaining a programming language, we have thankfully
developed deprecation mechanisms
that can be used to signal that bad, or sub-optimal decisions of the
past can be corrected.

To refresh our collective memory, here is the current state of things,
regarding `sum`:

```
❯ ghci +RTS -M1024m
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
λ❯ sum [1..10^9]
*** Exception: heap overflow
```
Whereas, with an alternative implementation, such as `foldl'`:
```
λ❯ foldl' (+) 0 [1..10^9]
500000000500000000
(31.35 secs, 88,000,076,288 bytes)
```

I do not think a heap overflow, and the underlying space leak
occasioned by the laziness of `foldl`, are behaviours we should aim to
preserve for the sake of backward compatibility.

And actually, I think that moving these two functions to a strict,
space leak-free implementation would benefit the lazy PL research
domain by showing a good counter-example
of why it is not necessarily suitable for every kind of computation.
I also think, and this is rooted from experience, that we must strive
to empower our users with the power of laziness. Not burden them with it.
Standing on the shoulders of giants is what made Haskell so great, but
this should not prevent us from spreading our wings to go higher.

———

Now, there have been Prelude replacements (such as Relude) and
companion libraries (like `strict`) who have been shipping such
alternative implementations for quite some time now.

A point that can be raised is: Why should we bother? Isn't `strict`
already enough?
To this I answer: `strict` and Relude, ultimately, patches on an
tire's inner tube. We may be able to roll with them for some distance,
but their very existence is a response to an abnormal situation that
we have grown to accept.
However, any bicycle rider who has the means to change their tire
should do so.
I believe we have the means to do so.

Another point that could be raised as well is the fact that this
implementation change would deviate from the 2010 Haskell Report[0].
If we want to stay true to the spirit and letter of the Report, this
is actually a non-issue. Indeed, it is noted that:

This  report  defines  the  syntax  for Haskell  programs and  an 
informal  abstract  semantics  for  the  meaning of such programs.  We
leave as implementation dependent the ways in which Haskell programs
are to be manipulated, interpreted, compiled, etc. This includes such
issues as the nature of programming environments and the error
messages returned for undefined programs (i.e. programs that formally
evaluate to⊥).[1]

As well as in chapter 9:

In this chapter the entire Haskell Prelude is given. It constitutes a 
specification for the Prelude. Many of the definitions are written
with clarity rather than efficiency in mind, and it is not required
that the specification be implemented as shown here.[2]

And finally, regarding the non-strict nature of Haskell, the Report
references strict evaluation to avoid "unneeded laziness."[3]
Thus it was expected that laziness would not be a silver bullet, and
it could harm performance.

———

Regarding the implementation detail, `sum` and `product` would
piggy-back on the already-present `foldMap'` function.


Thank you very much for reading,
I believe we can all go together towards improving the experience of
Haskell developers, starting with this.

[0]: Haskell 2010 Language Report,
https://www.haskell.org/definition/haskell2010.pdf
[1]: Haskell 2010 Language Report, page 3
[2]: Haskell 2010 Language Report, Chapter 9 Standard Prelude, page 105
[3]: Haskell 2010 Language Report, Section 6.2 Strict Evaluation, page 75


      
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

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

Re: [Proposal] Strict `sum` and `product`

Henning Thielemann

On Sun, 18 Oct 2020, Hécate wrote:

> In conclusion, leaving things to the optimiser that could be trivially
> made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a
lazy accumulator type, say a lazy pair type. If at all, sum and product
should be deepseq-strict. So currently, letting the optimiser make a lazy
sum strict is still the smaller hack.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries
Reply | Threaded
Open this post in threaded view
|

Re: [Proposal] Strict `sum` and `product`

Oleg Grenrus

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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: [Proposal] Strict `sum` and `product`

Vanessa McHale-2

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

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

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

Re: [Proposal] Strict `sum` and `product`

Oleg Grenrus
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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: [Proposal] Strict `sum` and `product`

Hécate

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

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

Re: [Proposal] Strict `sum` and `product`

Oleg Grenrus

Sorry I wasn't clear myself. Option C is "add sum'"

For lists:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

For Foldable

    sum  = getSum #. foldMap  Sum
    sum' = getSum #. foldMap' Sum

- Oleg

On 18.10.2020 23.11, Hécate wrote:

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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: [Proposal] Strict `sum` and `product`

Wander Hillen
In reply to this post by Hécate
I think this is a very good idea. Non-strict `foldl` for summing and multiplying introduces undesired space leaking behavior and is a very surprising default both to beginners and even for more experienced Haskellers.

If there was a Num type with lazy structure, something like `product [<some_list_containing_zero>] == 0` would be able to short-circuit as soon as it hits a zero. However since none of the Num types in base have a lazy structure (and both sum and product have a Num constraint), there is not really a way to take advantage of laziness anyway and therefore the best implementation would be Olegs option A.

Best regards,
Wander

Op zo 18 okt. 2020 om 20:14 schreef Hécate <[hidden email]>:
My fellow Haskell developers, contributors and maintainers,

I wish to present what is certainly a controversial proposal for the
`base` library:
    Making the `sum` and `product` functions from the `base` library strict.

This is not a new question, the debate is old, but I am personally
convinced that the existence of those two lazy functions is something
that should never have happened.
One of the first goals that led to the creation of Haskell was to enable
collaboration and research in the domain of lazy (or non-strict)
programming languages and techniques.
While it led to the discovery of new methods and ways to represent
programs, we also realised that this paradigm has proven to produce
sub-optimal implementations for
these functions.

And while maintaining backward compatibility *is* important when
designing and maintaining a programming language, we have thankfully
developed deprecation mechanisms
that can be used to signal that bad, or sub-optimal decisions of the
past can be corrected.

To refresh our collective memory, here is the current state of things,
regarding `sum`:

```
❯ ghci +RTS -M1024m
GHCi, version 8.10.1: https://www.haskell.org/ghc/  :? for help
λ❯ sum [1..10^9]
*** Exception: heap overflow
```
Whereas, with an alternative implementation, such as `foldl'`:
```
λ❯ foldl' (+) 0 [1..10^9]
500000000500000000
(31.35 secs, 88,000,076,288 bytes)
```

I do not think a heap overflow, and the underlying space leak occasioned
by the laziness of `foldl`, are behaviours we should aim to preserve for
the sake of backward compatibility.

And actually, I think that moving these two functions to a strict, space
leak-free implementation would benefit the lazy PL research domain by
showing a good counter-example
of why it is not necessarily suitable for every kind of computation.
I also think, and this is rooted from experience, that we must strive to
empower our users with the power of laziness. Not burden them with it.
Standing on the shoulders of giants is what made Haskell so great, but
this should not prevent us from spreading our wings to go higher.

———

Now, there have been Prelude replacements (such as Relude) and companion
libraries (like `strict`) who have been shipping such alternative
implementations for quite some time now.

A point that can be raised is: Why should we bother? Isn't `strict`
already enough?
To this I answer: `strict` and Relude, ultimately, patches on an tire's
inner tube. We may be able to roll with them for some distance, but
their very existence is a response to an abnormal situation that we have
grown to accept.
However, any bicycle rider who has the means to change their tire should
do so.
I believe we have the means to do so.

Another point that could be raised as well is the fact that this
implementation change would deviate from the 2010 Haskell Report[0].
If we want to stay true to the spirit and letter of the Report, this is
actually a non-issue. Indeed, it is noted that:

> This  report  defines  the  syntax  for Haskell  programs and  an
informal  abstract  semantics  for  the  meaning of such programs.  We
leave as implementation dependent the ways in which Haskell programs are
to be manipulated, interpreted, compiled, etc. This includes such issues
as the nature of programming environments and the error messages
returned for undefined programs (i.e. programs that formally evaluate
to⊥).[1]

As well as in chapter 9:

> In this chapter the entire Haskell Prelude is given. It constitutes a
specification for the Prelude. Many of the definitions are written with
clarity rather than efficiency in mind, and it is not required that the
specification be implemented as shown here.[2]

And finally, regarding the non-strict nature of Haskell, the Report
references strict evaluation to avoid "unneeded laziness."[3]
Thus it was expected that laziness would not be a silver bullet, and it
could harm performance.

———

Regarding the implementation detail, `sum` and `product` would
piggy-back on the already-present `foldMap'` function.


Thank you very much for reading,
I believe we can all go together towards improving the experience of
Haskell developers, starting with this.

[0]: Haskell 2010 Language Report,
https://www.haskell.org/definition/haskell2010.pdf
[1]: Haskell 2010 Language Report, page 3
[2]: Haskell 2010 Language Report, Chapter 9 Standard Prelude, page 105
[3]: Haskell 2010 Language Report, Section 6.2 Strict Evaluation, page 75

--
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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: [Proposal] Strict `sum` and `product`

Sylvain Henry-2
In reply to this post by Oleg Grenrus

Do we have an actual example of the use of a lazy sum in the wild?

If the most common case is the strict one, making `sum` strict would be a better default. If need be we could also provide `lazySum` or something, but is there really a need?

Sylvain


On 18/10/2020 22:16, Oleg Grenrus wrote:

Sorry I wasn't clear myself. Option C is "add sum'"

For lists:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

For Foldable

    sum  = getSum #. foldMap  Sum
    sum' = getSum #. foldMap' Sum

- Oleg

On 18.10.2020 23.11, Hécate wrote:

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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

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

Re: [Proposal] Strict `sum` and `product`

Emily Pillmore
I can't think of an example where a raw lazy `sum` would be preferable to a strict version. If summing over infinite data structures, it will always be prefixed by a `take` or a `drop` prior to summing to make sure we work with finite chunks. In which case, a strict sum is still better. Maybe someone has a more complex, contrived example showing the usefulness of lazy sums.

The fact that no one seems to be able to name one in this or other discussions, or come up with a contrived example, is a good indicator to me that at least the default should be strict in this case. We should offer a lazy variant as a second option, not the first.

I'm in favor of Oleg's `foldMap` implementation. It's really clean. Also thank you Hécate!

Cheers,
Emily


On Tue, Oct 20, 2020 at 12:40 PM, Sylvain Henry <[hidden email]> wrote:

Do we have an actual example of the use of a lazy sum in the wild?

If the most common case is the strict one, making `sum` strict would be a better default. If need be we could also provide `lazySum` or something, but is there really a need?

Sylvain


On 18/10/2020 22:16, Oleg Grenrus wrote:

Sorry I wasn't clear myself. Option C is "add sum'"

For lists:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

For Foldable

    sum  = getSum #. foldMap  Sum
    sum' = getSum #. foldMap' Sum

- Oleg

On 18.10.2020 23.11, Hécate wrote:

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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

_______________________________________________
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: [Proposal] Strict `sum` and `product`

chessai .
I'm pretty strongly in favour of a sum implemented using foldMap'. The status quo is atrocious (cf. Oleg's emails), and the utility of a lazy right fold is low in practise.

On Wed, Oct 21, 2020, 14:38 Emily Pillmore <[hidden email]> wrote:
I can't think of an example where a raw lazy `sum` would be preferable to a strict version. If summing over infinite data structures, it will always be prefixed by a `take` or a `drop` prior to summing to make sure we work with finite chunks. In which case, a strict sum is still better. Maybe someone has a more complex, contrived example showing the usefulness of lazy sums.

The fact that no one seems to be able to name one in this or other discussions, or come up with a contrived example, is a good indicator to me that at least the default should be strict in this case. We should offer a lazy variant as a second option, not the first.

I'm in favor of Oleg's `foldMap` implementation. It's really clean. Also thank you Hécate!

Cheers,
Emily


On Tue, Oct 20, 2020 at 12:40 PM, Sylvain Henry <[hidden email]> wrote:

Do we have an actual example of the use of a lazy sum in the wild?

If the most common case is the strict one, making `sum` strict would be a better default. If need be we could also provide `lazySum` or something, but is there really a need?

Sylvain


On 18/10/2020 22:16, Oleg Grenrus wrote:

Sorry I wasn't clear myself. Option C is "add sum'"

For lists:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

For Foldable

    sum  = getSum #. foldMap  Sum
    sum' = getSum #. foldMap' Sum

- Oleg

On 18.10.2020 23.11, Hécate wrote:

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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

_______________________________________________
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

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

Re: [Proposal] Strict `sum` and `product`

Carter Schonwald
Even worse, it’s using foldl on lists, when, to the best of my knowledge, only foldr and foldl’ ever make sense for finite Haskell lists. Not sure about infinite lists ;)

On Wed, Oct 21, 2020 at 4:11 PM chessai <[hidden email]> wrote:
I'm pretty strongly in favour of a sum implemented using foldMap'. The status quo is atrocious (cf. Oleg's emails), and the utility of a lazy right fold is low in practise.

On Wed, Oct 21, 2020, 14:38 Emily Pillmore <[hidden email]> wrote:
I can't think of an example where a raw lazy `sum` would be preferable to a strict version. If summing over infinite data structures, it will always be prefixed by a `take` or a `drop` prior to summing to make sure we work with finite chunks. In which case, a strict sum is still better. Maybe someone has a more complex, contrived example showing the usefulness of lazy sums.

The fact that no one seems to be able to name one in this or other discussions, or come up with a contrived example, is a good indicator to me that at least the default should be strict in this case. We should offer a lazy variant as a second option, not the first.

I'm in favor of Oleg's `foldMap` implementation. It's really clean. Also thank you Hécate!

Cheers,
Emily


On Tue, Oct 20, 2020 at 12:40 PM, Sylvain Henry <[hidden email]> wrote:

Do we have an actual example of the use of a lazy sum in the wild?

If the most common case is the strict one, making `sum` strict would be a better default. If need be we could also provide `lazySum` or something, but is there really a need?

Sylvain


On 18/10/2020 22:16, Oleg Grenrus wrote:

Sorry I wasn't clear myself. Option C is "add sum'"

For lists:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

For Foldable

    sum  = getSum #. foldMap  Sum
    sum' = getSum #. foldMap' Sum

- Oleg

On 18.10.2020 23.11, Hécate wrote:

Indeed, and I initially went to suggest a `foldMap'`-based implementation to keep with the current implementation of many Foldable functions that are based on `foldMap` rather than a raw `fold`.

On 18/10/2020 22:04, Oleg Grenrus wrote:
For the sake of bigger audience I didn't bother mentioning #. which is a coercion helper. It's essentially better (.) when the first argument is newtype constructor (i.e. coerce).

So with Option A (strict):

    sum = getSum #. foldMap' Sum

Or Option B (lazy)

    sum = getSum #. foldMap Sum

---

There is also third option, Option C:

    sum  = foldr  (+) 0
    sum' = foldl' (+) 0

I don't think this is worthwhile, but it is an option.
(to rehash, I don't consider maintaining status quo to be an option at all).

- Oleg
On 18.10.2020 22.54, Vanessa McHale wrote:

It's

sum = getSum #. foldMap Sum

in base.

On 10/18/20 2:49 PM, Oleg Grenrus wrote:

The problem is the current definition of sum for lists which uses foldl, i.e non-strict left fold

    sum = foldl (+) 0

It's utterly broken. Either we should change it to foldl' to work on some types where addition is strict, Option A:

    sum = foldl' (+) 0

or alternatively (to make people using lazy accumulator types), Option B:

    sum = foldr (+) 0

The current state is no good for anyone or anything.

---

Related issue which Hecate didn't clearly mention, is that Foldable class default implementation has

   class Foldable f where
       ...
       sum = getSum . foldMap Sum -- this is "good" lazy definition

If we select option A, then I argue that for consistency the default `Foldable.sum` should be

       sum = getSum . foldMap' Sum -- strict foldMap'

If we select option B, Foldable definition doesn't need to be changed.

---

I repeat, using non-strict left fold, foldl, for sum and product is not good for anything.
Either foldr or foldl'.

I have no strong preference. Current state is unacceptable.

-  Oleg

On 18.10.2020 22.24, Henning Thielemann wrote:

On Sun, 18 Oct 2020, Hécate wrote:

In conclusion, leaving things to the optimiser that could be trivially made fast every time seems needlessly risky.

`seq` is still a hack. A strict 'sum' and 'product' would still fail on a lazy accumulator type, say a lazy pair type. If at all, sum and product should be deepseq-strict. So currently, letting the optimiser make a lazy sum strict is still the smaller hack.

_______________________________________________
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

_______________________________________________
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
-- 
Hécate ✨
IRC: Uniaika
WWW: https://glitchbra.in
RUN: BSD

_______________________________________________
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

_______________________________________________
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
_______________________________________________
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: [Proposal] Strict `sum` and `product`

Jon Fairbairn
In reply to this post by Sylvain Henry-2
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

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

Re: [Proposal] Strict `sum` and `product`

David Duke
Concur with Jon's point. 
I'm uncomfortable with making foldMap/sum strict.
Haskell was intended to explore a region of the programming design space that had not been well covered. and it remains
if not unique  then at least exemplary in that respect. When  I write in Haskell I do so with the knowledge that I am working with
lazy evaluation with the benefits and risk that comes with that. If I'm desperate to have finer operational control, I  either
swallow that pill and adapt my use of Haskell accordingly, or pick up a different tool from the programming language toolbox.

Now the OP pointed to an issue with one specific use of sum. However, that seems like weak grounds to make library changes:
1. we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.
2. if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
3. Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
So whilst  the post was clearly intended to trigger discussion, in terms on conveying sentiment a strict  foldMap would be a big '-'
for me personally. Whilst there are performance challenges in working  with Haskell. The primary role of the programming notation
is allowing one to think about the problem and obtain a clear, correct solution. Performance tuning comes later if at all, and
her are known techniques for doing so  with Haskell/ghc.
5. OTOH I see little   harm in adding a library that provides a strict foldMap for those
who want to use it after  deliberate thought.

YMMMocV
David







On Thu, Oct 22, 2020 at 10:36 AM Jon Fairbairn <[hidden email]> wrote:
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

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


--
David Duke
Emeritus Professor of Computer Science
School of Computing University of Leeds UK

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

Re: [Proposal] Strict `sum` and `product`

Wander Hillen
In reply to this post by Jon Fairbairn
I don't think this example shows that a lazy fold would be better. Even if the combining argument of the fold is not strict in the second argument, evaluating something like "sum [Infinity, 1, 2, 3]" with the infinity-shorting double will still touch every element in the list. As I understand it, to actually benefit from laziness in these functions they'd need both a lazy combining function AND a lazy accumulator type (which Double is not). For a practical example of where a shortcut might be possible, consider a case like "if (product [1,2,3,0,4,5]) < 20 then f x else g y". Evaluation of the list could theoretically stop after it encounters the zero [0] since after that any further elements in the list will no longer change the value of the outcome. I don't think that this actually occurs however and doubt the various fold functions could be rewritten in such a way as to handle this in the general case as long as the accumulator type is strict. As was mentioned earlier, all of the Num types in base are strict and both `sum` and `product` have a Num constraint. If lazy shortcutting is important, a small custom function that recurses over the list and tests for problem-specific edge cases will still be possible.

I disagree btw with the statement that we should not change this even though nobody can think of a compelling reason not to because we might think of such a reason later. That standpoint in its extreme can only lead to paralysis, since it is not always possible to prove no reasons will be thought of later.

Davids mail came in as I was writing this, I do agree with many of his points regarding laziness but would like to point out that as Haskell was/is intended to explore laziness in programming, we should eventually be able to get the benefits from these explorations as well. Negative results can be as valuable as positive results after all, so if "we-the-library-writers" discover a place where laziness is not ideal it should be possible (encouraged even) to apply this learning and change our language for the better. In this specific case (sum and product only), the use of strict accumulator types results in strict behavior already and therefore we lose nothing by changing from lazy to strict foldl. The proposal is NOT about removing lazy folds in general, just these two particular cases where they do not bring any benefits but do bring space leaks.

Wander

[0]: This is an optimization we see in the implementation of Integer multiplication. It does not work for `product` though, only for `(*)`.

Op do 22 okt. 2020 om 11:36 schreef Jon Fairbairn <[hidden email]>:
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

_______________________________________________
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: [Proposal] Strict `sum` and `product`

Fumiaki Kinoshita
In reply to this post by David Duke
For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


This makes sense only if sum is foldr (+) 0, while the implementation of sum for lists is foldl (+) 0. But hey, we are comparing a hypothetical type with hundreds of real world uses. 

Haskell should remain a lazy language
I'm not sure if I agree. We've been bitten by laziness too much, hence the introduction of BangPatterns, StrictData, deepseq, etc. IMO Haskell ecosystem should be more strict.

I'm uncomfortable with making foldMap/sum strict.

No one is suggesting to change foldMap; what OP wants to change is sum and product, and foldMap _happens to be_ the current default implementation.

> we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.

The context is pretty clear; the status quo (sum = foldl (+) 0) is flat-out wrong. I'd say more than 80% of the uses of sum is supposed to look at all the elements. And even if (+) is short-circuiting in the way Jon suggested, lazy foldl does not take any advantage of it.

if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
I'm not sure which function you are talking about (there's no function called scanAccum in base nor containers). If you mean scanl, lazy accumulator still makes sense because the resulting list can be consumed incrementally. foldl is not.

Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
Again, there's little to be gained from lazy foldl. It's avoided in general and I'd say it's not "uniform" to use the function.

4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
Also from a pedagogical point of view, a number of beginners fall into a trap of lazy foldl. Caveats should be added to the current one if at all, but this danger zone can be removed with one byte change.

I'm seriously worried that the use of foldl in the standard library might make beginners think that it's fine to use foldl.

As far as I remember, the same change has been suggested a while ago but didn't make it. I hope we don't get discouraged this time and go ahead with the change.

2020年10月22日(木) 19:19 David Duke <[hidden email]>:
Concur with Jon's point. 
I'm uncomfortable with making foldMap/sum strict.
Haskell was intended to explore a region of the programming design space that had not been well covered. and it remains
if not unique  then at least exemplary in that respect. When  I write in Haskell I do so with the knowledge that I am working with
lazy evaluation with the benefits and risk that comes with that. If I'm desperate to have finer operational control, I  either
swallow that pill and adapt my use of Haskell accordingly, or pick up a different tool from the programming language toolbox.

Now the OP pointed to an issue with one specific use of sum. However, that seems like weak grounds to make library changes:
1. we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.
2. if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
3. Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
So whilst  the post was clearly intended to trigger discussion, in terms on conveying sentiment a strict  foldMap would be a big '-'
for me personally. Whilst there are performance challenges in working  with Haskell. The primary role of the programming notation
is allowing one to think about the problem and obtain a clear, correct solution. Performance tuning comes later if at all, and
her are known techniques for doing so  with Haskell/ghc.
5. OTOH I see little   harm in adding a library that provides a strict foldMap for those
who want to use it after  deliberate thought.

YMMMocV
David







On Thu, Oct 22, 2020 at 10:36 AM Jon Fairbairn <[hidden email]> wrote:
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

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


--
David Duke
Emeritus Professor of Computer Science
School of Computing University of Leeds UK
_______________________________________________
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: [Proposal] Strict `sum` and `product`

Emily Pillmore
Just to keep this going so it doesn't die out. I'm going to request that Hécate submit a PR to address the composite criticism here, implementing `sum|product` in terms of `foldr`, and providing a strict equivalent `sum'|product'` variant for each as discussed. We'll move the discussion to that PR. 

Cheers,
Emily 


On Thu, Oct 22, 2020 at 7:05 AM, Fumiaki Kinoshita <[hidden email]> wrote:
For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


This makes sense only if sum is foldr (+) 0, while the implementation of sum for lists is foldl (+) 0. But hey, we are comparing a hypothetical type with hundreds of real world uses. 

Haskell should remain a lazy language
I'm not sure if I agree. We've been bitten by laziness too much, hence the introduction of BangPatterns, StrictData, deepseq, etc. IMO Haskell ecosystem should be more strict.

I'm uncomfortable with making foldMap/sum strict.

No one is suggesting to change foldMap; what OP wants to change is sum and product, and foldMap _happens to be_ the current default implementation.

> we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.

The context is pretty clear; the status quo (sum = foldl (+) 0) is flat-out wrong. I'd say more than 80% of the uses of sum is supposed to look at all the elements. And even if (+) is short-circuiting in the way Jon suggested, lazy foldl does not take any advantage of it.

if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
I'm not sure which function you are talking about (there's no function called scanAccum in base nor containers). If you mean scanl, lazy accumulator still makes sense because the resulting list can be consumed incrementally. foldl is not.

Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
Again, there's little to be gained from lazy foldl. It's avoided in general and I'd say it's not "uniform" to use the function.

4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
Also from a pedagogical point of view, a number of beginners fall into a trap of lazy foldl. Caveats should be added to the current one if at all, but this danger zone can be removed with one byte change.

I'm seriously worried that the use of foldl in the standard library might make beginners think that it's fine to use foldl.

As far as I remember, the same change has been suggested a while ago but didn't make it. I hope we don't get discouraged this time and go ahead with the change.

2020年10月22日(木) 19:19 David Duke <[hidden email]>:
Concur with Jon's point. 
I'm uncomfortable with making foldMap/sum strict.
Haskell was intended to explore a region of the programming design space that had not been well covered. and it remains
if not unique  then at least exemplary in that respect. When  I write in Haskell I do so with the knowledge that I am working with
lazy evaluation with the benefits and risk that comes with that. If I'm desperate to have finer operational control, I  either
swallow that pill and adapt my use of Haskell accordingly, or pick up a different tool from the programming language toolbox.

Now the OP pointed to an issue with one specific use of sum. However, that seems like weak grounds to make library changes:
1. we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.
2. if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
3. Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
So whilst  the post was clearly intended to trigger discussion, in terms on conveying sentiment a strict  foldMap would be a big '-'
for me personally. Whilst there are performance challenges in working  with Haskell. The primary role of the programming notation
is allowing one to think about the problem and obtain a clear, correct solution. Performance tuning comes later if at all, and
her are known techniques for doing so  with Haskell/ghc.
5. OTOH I see little   harm in adding a library that provides a strict foldMap for those
who want to use it after  deliberate thought.

YMMMocV
David







On Thu, Oct 22, 2020 at 10:36 AM Jon Fairbairn <[hidden email]> wrote:
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

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


--
David Duke
Emeritus Professor of Computer Science
School of Computing University of Leeds UK
_______________________________________________
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



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

Re: [Proposal] Strict `sum` and `product`

chessai .
Emily, I already put up an MR: https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4355

On Mon, Oct 26, 2020, 20:14 Emily Pillmore <[hidden email]> wrote:
Just to keep this going so it doesn't die out. I'm going to request that Hécate submit a PR to address the composite criticism here, implementing `sum|product` in terms of `foldr`, and providing a strict equivalent `sum'|product'` variant for each as discussed. We'll move the discussion to that PR. 

Cheers,
Emily 


On Thu, Oct 22, 2020 at 7:05 AM, Fumiaki Kinoshita <[hidden email]> wrote:
For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


This makes sense only if sum is foldr (+) 0, while the implementation of sum for lists is foldl (+) 0. But hey, we are comparing a hypothetical type with hundreds of real world uses. 

Haskell should remain a lazy language
I'm not sure if I agree. We've been bitten by laziness too much, hence the introduction of BangPatterns, StrictData, deepseq, etc. IMO Haskell ecosystem should be more strict.

I'm uncomfortable with making foldMap/sum strict.

No one is suggesting to change foldMap; what OP wants to change is sum and product, and foldMap _happens to be_ the current default implementation.

> we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.

The context is pretty clear; the status quo (sum = foldl (+) 0) is flat-out wrong. I'd say more than 80% of the uses of sum is supposed to look at all the elements. And even if (+) is short-circuiting in the way Jon suggested, lazy foldl does not take any advantage of it.

if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
I'm not sure which function you are talking about (there's no function called scanAccum in base nor containers). If you mean scanl, lazy accumulator still makes sense because the resulting list can be consumed incrementally. foldl is not.

Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
Again, there's little to be gained from lazy foldl. It's avoided in general and I'd say it's not "uniform" to use the function.

4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
Also from a pedagogical point of view, a number of beginners fall into a trap of lazy foldl. Caveats should be added to the current one if at all, but this danger zone can be removed with one byte change.

I'm seriously worried that the use of foldl in the standard library might make beginners think that it's fine to use foldl.

As far as I remember, the same change has been suggested a while ago but didn't make it. I hope we don't get discouraged this time and go ahead with the change.

2020年10月22日(木) 19:19 David Duke <[hidden email]>:
Concur with Jon's point. 
I'm uncomfortable with making foldMap/sum strict.
Haskell was intended to explore a region of the programming design space that had not been well covered. and it remains
if not unique  then at least exemplary in that respect. When  I write in Haskell I do so with the knowledge that I am working with
lazy evaluation with the benefits and risk that comes with that. If I'm desperate to have finer operational control, I  either
swallow that pill and adapt my use of Haskell accordingly, or pick up a different tool from the programming language toolbox.

Now the OP pointed to an issue with one specific use of sum. However, that seems like weak grounds to make library changes:
1. we dont knowing the context. the best way to avoid the cost of computation is not to compute it; what alternatives are there
i this s[ecific problem.
2. if one was to make foldMap/sum strict why not also other functions, e.g. scanAccum, where does one stop on the grounds of possibly saving costs in so as yet
unknown application
3. Instead of thinking/programming  in a pure lazy language, you are then in the position of thinking lazily apart from some set of
to be determined exceptional cases. the simplicity and uniformity of the model is gone.
4. As per item 3 but from a pedagogical point of view. I taught UG  FP for years. Complicating the model is not going to help students,
to say nothing of the caveats that would have to be added to existing teaching materials.
So whilst  the post was clearly intended to trigger discussion, in terms on conveying sentiment a strict  foldMap would be a big '-'
for me personally. Whilst there are performance challenges in working  with Haskell. The primary role of the programming notation
is allowing one to think about the problem and obtain a clear, correct solution. Performance tuning comes later if at all, and
her are known techniques for doing so  with Haskell/ghc.
5. OTOH I see little   harm in adding a library that provides a strict foldMap for those
who want to use it after  deliberate thought.

YMMMocV
David







On Thu, Oct 22, 2020 at 10:36 AM Jon Fairbairn <[hidden email]> wrote:
Sylvain Henry <[hidden email]> writes:

> Do we have an actual example of the use of a lazy sum in the
> wild?

That’s not a very good argument, though I’ve seen it used quite
a lot.  The problem is that just because no-one can currently
think of a “real” example it doesn’t mean that there are no
cases where laziness is required.

For a forced example, consider a wrapping of Double with a test
for infinity on the left argument


 a + b | isInfinite a = a


which doesn’t evaluate it’s second argument if the first is
infinite.

> If the most common case is the strict one, making `sum`
> strict would be a better default.

Haskell should remain a lazy language, so the defaults should be
lazy unless they can be proved strict anyway.

> If need be we could also provide `lazySum` or something, but
> is there really a need?

Who can truly say? I’d support sum' as the strict version as
that is consistent with other usages.

  — Jón

>
> Sylvain
>
>
> On 18/10/2020 22:16, Oleg Grenrus wrote:
>>
>> Sorry I wasn't clear myself. Option C is "add sum'"
>>
>> For lists:
>>
>>     sum  = foldr  (+) 0
>>     sum' = foldl' (+) 0
>>
>> For Foldable
>>
>>     sum  = getSum #. foldMap  Sum
>>     sum' = getSum #. foldMap' Sum
>>
>> - Oleg
>>
>> On 18.10.2020 23.11, Hécate wrote:
>>>
>>> Indeed, and I initially went to suggest a
>>> foldMap'`-based implementation to keep with the current
>>> implementation of many Foldable functions that are based
>>> on `foldMap` rather than a raw `fold`.
>>>
>>> On 18/10/2020 22:04, Oleg Grenrus wrote:
>>>> For the sake of bigger audience I didn't bother
>>>> mentioning #. which is a coercion helper. It's
>>>> essentially better (.) when the first argument is
>>>> newtype constructor (i.e. coerce).
>>>>
>>>> So with Option A (strict):
>>>>
>>>>     sum = getSum #. foldMap' Sum
>>>>
>>>> Or Option B (lazy)
>>>>
>>>>     sum = getSum #. foldMap Sum
>>>>
>>>> ---
>>>>
>>>> There is also third option, Option C:
>>>>
>>>>     sum  = foldr  (+) 0
>>>>     sum' = foldl' (+) 0
>>>>
>>>> I don't think this is worthwhile, but it is an option.
>>>> (to rehash, I don't consider maintaining status quo to
>>>> be an option at all).
>>>>
>>>> - Oleg
>>>> On 18.10.2020 22.54, Vanessa McHale wrote:
>>>>>
>>>>> It's
>>>>>
>>>>> sum = getSum #. foldMap Sum
>>>>>
>>>>> in base.
>>>>>
>>>>> On 10/18/20 2:49 PM, Oleg Grenrus wrote:
>>>>>>
>>>>>> The problem is the current definition of sum for lists
>>>>>> which uses foldl, i.e non-strict left fold
>>>>>>
>>>>>>     sum = foldl (+) 0
>>>>>>
>>>>>> It's utterly broken. Either we should change it to
>>>>>> foldl' to work on some types where addition is strict,
>>>>>> Option A:
>>>>>>
>>>>>>     sum = foldl' (+) 0
>>>>>>
>>>>>> or alternatively (to make people using lazy
>>>>>> accumulator types), Option B:
>>>>>>
>>>>>>     sum = foldr (+) 0
>>>>>>
>>>>>> The current state is no good for anyone or anything.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> Related issue which Hecate didn't clearly mention, is
>>>>>> that Foldable class default implementation has
>>>>>>
>>>>>>    class Foldable f where
>>>>>>        ...
>>>>>>        sum = getSum . foldMap Sum -- this is "good" lazy definition
>>>>>>
>>>>>> If we select option A, then I argue that for
>>>>>> consistency the default `Foldable.sum` should be
>>>>>>
>>>>>>        sum = getSum . foldMap' Sum -- strict foldMap'
>>>>>>
>>>>>> If we select option B, Foldable definition doesn't need to be changed.
>>>>>>
>>>>>> ---
>>>>>>
>>>>>> I repeat, using non-strict left fold, foldl, for sum
>>>>>> and product is not good for anything.
>>>>>> Either foldr or foldl'.
>>>>>>
>>>>>> I have no strong preference. Current state is unacceptable.
>>>>>>
>>>>>> -  Oleg
>>>>>>
>>>>>> On 18.10.2020 22.24, Henning Thielemann wrote:
>>>>>>>
>>>>>>> On Sun, 18 Oct 2020, Hécate wrote:
>>>>>>>
>>>>>>>> In conclusion, leaving things to the optimiser that
>>>>>>>> could be trivially made fast every time seems
>>>>>>>> needlessly risky.
>>>>>>>
>>>>>>> `seq` is still a hack. A strict 'sum' and 'product'
>>>>>>> would still fail on a lazy accumulator type, say a
>>>>>>> lazy pair type. If at all, sum and product should be
>>>>>>> deepseq-strict. So currently, letting the optimiser
>>>>>>> make a lazy sum strict is still the smaller hack.
>>>>>>>
>>>>>>> _______________________________________________
>>>>>>> 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
>>>>>
>>>>> _______________________________________________
>>>>> 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
>>> --
>>> Hécate ✨
>>> IRC: Uniaika
>>> WWW:https://glitchbra.in
>>> RUN: BSD
>>>
>>> _______________________________________________
>>> 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
> _______________________________________________
> Libraries mailing list
> [hidden email]
> http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

--
Jón Fairbairn                                 [hidden email]
http://www.chaos.org.uk/~jf/Stuff-I-dont-want.html  (updated 2014-04-05)

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


--
David Duke
Emeritus Professor of Computer Science
School of Computing University of Leeds UK
_______________________________________________
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


_______________________________________________
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
12