Adding partial foldl1' to Foldable?

[Viktor Dukhovni]

Given that Foldable currently has:

    - foldr and foldr'
    - foldl and foldl'
    - foldMap and foldMap'

and also has only:

    - foldr1
    - foldl1

it seems natural to ask whether there it should also have a strict
variant of at least foldl1, since the non-strict variant has rather
limited applicability, and users would/should in most cases want/use
the strict `foldl1'` instead.

--
    Viktor.

P.S.  I just joined the list today, but noticed that coincidentally, there's
already a recent dicussion of Foldable1, which rather overlaps with this
question, and perhaps the partial `foldr1` and `foldl1` should be seen
as deprecated, once a suitable class of non-empty containers provides
total variants.  But perhaps on the other hand, given that the partial
functions already exist, perhaps adding the strict companions is
warranted?

I am asking because I am writing some expository prose for
Data.Foldable, to go at the bottom of the document, structurally along
the lines of what I contributed for Data.Traversable, but with a fairly
different focus.  The goal is draw careful distinctions between
strict recursive and lazy corecursive reductions, explaining their
proper usage and typical implementations.  The "missing" `foldl1'`
was something I ran into while working on part of the writeup.
_______________________________________________
Libraries mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/libraries

[Viktor Dukhovni]

> On Dec 20, 2020, at 8:15 PM, Viktor Dukhovni <[hidden email]> wrote:
>
> I am asking because I am writing some expository prose for
> Data.Foldable, to go at the bottom of the document, structurally along
> the lines of what I contributed for Data.Traversable, but with a fairly
> different focus.  The goal is draw careful distinctions between
> strict recursive and lazy corecursive reductions, explaining their
> proper usage and typical implementations.

The draft version can be seen at:

  https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html

along with a pre-formatted Data.Traversable (already merged some
months back, but may not yet be easy to found in formatted form):

  https://imrryr.org/~viktor/haskell/foldable-doc/Data-Traversable.html

Any feedback appreciated... Is this roughly ready for an MR, or are there
any changes that are needed first and best discussed on the list rather
than via Gitlab?

--
        Viktor.

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

[Haskell - Libraries mailing list]

Hi Victor!

Thanks for this initiative! I think it would be great to have some
good, in-depth documentation on Foldable and Traversable in base!

So far I've made a pass over the Foldable docs. Here are some random comments:

* I think the docs at the bottom of the page are easy to miss. Maybe
add a reference to them at the top of the page.

* I think the documentation might be more accessible and inviting if
it would use slightly simpler language. For example the first sentence
of the overview section:

  The Foldable class encompasses structures that support element-wise
reduction to a summary value.

  With words like "encompass" and "summary" (as an adjective) the
sentence sounds slightly off-putting to me – this might be a matter of
taste though.

* In the code example for computing an average, a proper declaration
might be easier to follow:

  average :: (Foldable f, Fractional a) => f a -> a

* A clearer name for the "Construction" section might be "Defining instances"

* The distinction between recursive and corecursive reduction looks
very valuable IMHO!

Cheers!
Simon

Am Mi., 23. Dez. 2020 um 09:20 Uhr schrieb Viktor Dukhovni
<[hidden email]>:

>
> > On Dec 20, 2020, at 8:15 PM, Viktor Dukhovni <[hidden email]> wrote:
> >
> > I am asking because I am writing some expository prose for
> > Data.Foldable, to go at the bottom of the document, structurally along
> > the lines of what I contributed for Data.Traversable, but with a fairly
> > different focus.  The goal is draw careful distinctions between
> > strict recursive and lazy corecursive reductions, explaining their
> > proper usage and typical implementations.
>
> The draft version can be seen at:
>
>   https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html
>
> along with a pre-formatted Data.Traversable (already merged some
> months back, but may not yet be easy to found in formatted form):
>
>   https://imrryr.org/~viktor/haskell/foldable-doc/Data-Traversable.html
>
> Any feedback appreciated... Is this roughly ready for an MR, or are there
> any changes that are needed first and best discussed on the list rather
> than via Gitlab?
>
> --
>         Viktor.
>
> _______________________________________________
> 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

[Viktor Dukhovni]

On Thu, Dec 24, 2020 at 05:25:34AM +0100, Simon Jakobi via Libraries wrote:

> Hi Victor!
>
> Thanks for this initiative! I think it would be great to have some
> good, in-depth documentation on Foldable and Traversable in base!

Thanks for the encouragement.  FWIW, the Traversable writeup (module a
reference URL update), is already in base (for 9.0), but if you find
things worth fixing, there may yet be time to get some of those done.

> * I think the docs at the bottom of the page are easy to miss. Maybe
> add a reference to them at the top of the page.

Done.

> * I think the documentation might be more accessible and inviting if
> it would use slightly simpler language. For example the first sentence
> of the overview section:

I made some effort to simplify the language.  I hope it is better.

> * In the code example for computing an average, a proper declaration
> might be easier to follow:
>
>   average :: (Foldable f, Fractional a) => f a -> a

Done.

> * A clearer name for the "Construction" section might be "Defining instances"

Done.  Thanks.

> * The distinction between recursive and corecursive reduction looks
> very valuable IMHO!

I'm glad you like it.  For me, writing this down was actually the main
motivation for the new text.  I wanted to understand it better, and this
seemed like the best way. :-)

Let me know when you think this is close enough to being ready to move
the final polish discussion to Gitlab.

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

[Georgi Lyubenov]

In the "lazy corecursive" section from your original links, you mention a "flatten" function, but then the next function is named "toList". I think this might be an oversight.

=======

Georgi

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

[Viktor Dukhovni]

On Wed, Dec 23, 2020 at 06:19:51AM -0200, Viktor Dukhovni wrote:

> The draft version can be seen at:
>
>   https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html
>
> along with a pre-formatted Data.Traversable (already merged some
> months back, but may not yet be easy to found in formatted form):
>
>   https://imrryr.org/~viktor/haskell/foldable-doc/Data-Traversable.html
>
> Any feedback appreciated... Is this roughly ready for an MR, or are there
> any changes that are needed first and best discussed on the list rather
> than via Gitlab?

I've integrated the suggestions posted so far, and added sections that
list all the strict and all the lazy functions together describing
briefly their common features.

If the overall approach is sound, it might perhaps now make sense to add
some brief text also in each function synopsis that classifies it as
strict recursive, lazy corecursive, or some hybrid.  But perhaps just
having that level of detail at the bottom is sufficient?

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

[Viktor Dukhovni]

> On Dec 24, 2020, at 7:22 PM, Viktor Dukhovni <[hidden email]> wrote:
>
> If the overall approach is sound, it might perhaps now make sense to add
> some brief text also in each function synopsis that classifies it as
> strict recursive, lazy corecursive, or some hybrid.  But perhaps just
> having that level of detail at the bottom is sufficient?

I've forked the document to explore carving out a third-class
of folds, the *short-circuit* folds, that though they also
are based on `foldr`, are not really corecursive, they just
might terminate early, but produce only a single final result.

This variant is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable-v2.html
The original is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html>

Is the new version heading in the right direction?  Is anyone interested
in helping out to get the initial draft in good enough shape for an MR?

--
        Viktor.

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

[Ben Franksen]

Am 25.12.20 um 09:04 schrieb Viktor Dukhovni:

>> On Dec 24, 2020, at 7:22 PM, Viktor Dukhovni <[hidden email]> wrote:
>>
>> If the overall approach is sound, it might perhaps now make sense to add
>> some brief text also in each function synopsis that classifies it as
>> strict recursive, lazy corecursive, or some hybrid.  But perhaps just
>> having that level of detail at the bottom is sufficient?
>
> I've forked the document to explore carving out a third-class
> of folds, the *short-circuit* folds, that though they also
> are based on `foldr`, are not really corecursive, they just
> might terminate early, but produce only a single final result.
>
> This variant is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable-v2.html
> The original is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html>
>
> Is the new version heading in the right direction?  Is anyone interested
> in helping out to get the initial draft in good enough shape for an MR?

One minor nitpick:

Short-circuit reduction, which examines some initial sequence of the
input elements, but stops once a termination condition is met, returning
a final result based only on the elements considered to that point. The
                                                    ^ up

This one should really be fixed:

remaining elements are not considered. The input should generally be
finite, because the termination condition but otherwise be never met.
        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
        hard to understand because of grammar mistakes

Otherwise: very well written.

Why are the class laws part of the Overview and not of the class
documentation proper as usual?

Cheers
Ben

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

[Viktor Dukhovni]

On Sun, Dec 27, 2020 at 11:20:00AM +0100, Ben Franksen wrote:

> > This variant is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable-v2.html
> > The original is at: <https://imrryr.org/~viktor/haskell/foldable-doc/Data-Foldable.html>
> >
> > Is the new version heading in the right direction?  Is anyone interested
> > in helping out to get the initial draft in good enough shape for an MR?
>
> One minor nitpick:
>
> Short-circuit reduction, which examines some initial sequence of the
> input elements, but stops once a termination condition is met, returning
> a final result based only on the elements considered to that point. The
>                                                     ^ up
>
> This one should really be fixed:
>
> remaining elements are not considered. The input should generally be
> finite, because the termination condition but otherwise be never met.
>         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>         hard to understand because of grammar mistakes
>
> Otherwise: very well written.

Thanks, while reworking it, some things gone mangled, and I haven't
finished the proofreading yet.  I'll fix these pronto.

> Why are the class laws part of the Overview and not of the class
> documentation proper as usual?

Good question.  My take is that the typical *user* of the library is not
generally immediately interested in the laws, and so I prefer to present
the function synopses as quickly as possible up front.

For the more sophisticated users who'll be implementing instances, the
laws are are in their own section, with a link from the index at the
top, an not buried in the middle of the topmatter.

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

[Viktor Dukhovni]

On Sun, Dec 27, 2020 at 05:31:31AM -0500, Viktor Dukhovni wrote:

> > Otherwise: very well written.
>
> Thanks, while reworking it, some things gone mangled, and I haven't
> finished the proofreading yet.  I'll fix these pronto.

Done.  I'd be really great if someone were interested in stepping
forward to take turns iterating on the document once or twice before
we posting an MR on Gitlab.  But if nobody has the cycles, or what
I has is deemed close enogh as-is, then I'll just proof read some
more and file an MR, probably before the year is out.

With a bit of luck (for this MR), given the delay in GHC 9.0, perhaps it
could even make it into the GHC 9.0 release.

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

[Viktor Dukhovni]

On Sun, Dec 27, 2020 at 05:47:46AM -0500, Viktor Dukhovni wrote:

> With a bit of luck (for this MR), given the delay in GHC 9.0, perhaps it
> could even make it into the GHC 9.0 release.

I went ahead and opened in MR:

    https://gitlab.haskell.org/ghc/ghc/-/merge_requests/4689

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

[George Wilson]

I am sympathetic to the completeness argument, but I would prefer that
we not add more partial functions to base. Having foldl1 and foldr1 in
Foldable in the first place is something I consider a wart. Hopefully
we can remove them in the future.
Would it make sense to omit foldl1/foldr1/foldl1'/foldr1' entirely
from your explanation? Then it would be future-proofed against such
removal :)

Cheers,
George

On Mon, 21 Dec 2020 at 08:16, Viktor Dukhovni <[hidden email]> wrote:

>
>
> Given that Foldable currently has:
>
>     - foldr and foldr'
>     - foldl and foldl'
>     - foldMap and foldMap'
>
> and also has only:
>
>     - foldr1
>     - foldl1
>
> it seems natural to ask whether there it should also have a strict
> variant of at least foldl1, since the non-strict variant has rather
> limited applicability, and users would/should in most cases want/use
> the strict `foldl1'` instead.
>
> --
>     Viktor.
>
> P.S.  I just joined the list today, but noticed that coincidentally, there's
> already a recent dicussion of Foldable1, which rather overlaps with this
> question, and perhaps the partial `foldr1` and `foldl1` should be seen
> as deprecated, once a suitable class of non-empty containers provides
> total variants.  But perhaps on the other hand, given that the partial
> functions already exist, perhaps adding the strict companions is
> warranted?
>
> I am asking because I am writing some expository prose for
> Data.Foldable, to go at the bottom of the document, structurally along
> the lines of what I contributed for Data.Traversable, but with a fairly
> different focus.  The goal is draw careful distinctions between
> strict recursive and lazy corecursive reductions, explaining their
> proper usage and typical implementations.  The "missing" `foldl1'`
> was something I ran into while working on part of the writeup.
> _______________________________________________
> 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