Date: Tue, 25 Jun 2019 12:45:20 -0400

Chris,

If you're doing design work on <numeric>, then I EXTREMELY strongly

recommend watching Conor Hoekstra's talk "Algorithm Intuition"

<https://www.youtube.com/watch?v=48gV1SNm3WA> (from this year's C++Now)

first. Some design takeaways:

- Having "default" functors causes more confusion than help. The fact that

some numeric algorithms default to std::plus (std::reduce) and others to

std::minus (std::adjacent_difference) adds to the difficulty in developing

intuition about these algorithms.

- The historical naming of these algorithms is asymmetric and inconsistent

(just like their placement outside of <algorithm>). New "modern" versions

should go in <algorithm> so that learners of algorithms don't have to worry

about numerics.

- As pointed out in the Q&A, <numeric> is a misnomer for these abstract

algorithms anyway. For example,`std::inner_product` over doubles does not

compute a mathematically precise answer; "transform-reduce with std::plus

and std::times" is an unrealistically naïve way to compute "inner product."

The name of the algorithm should reflect its purpose, and the placement of

the algorithm should reflect its level of numeric sophistication.

- Having a 1-range version of `transform` and a 2-range version of

`transform`, sharing the same overload set, is a source of confusion.

Having 1- and 2-range versions but no 3- or 4-range versions (that is: the

original `std::transform` pre-dates variadic templates) is also a source of

confusion for programmers used to variadic `zip`.

Procedural issue: Your original message would have been clearer if you

could list not only the 7 algorithms you did, but also the (N??) algorithms

that are on your list of "all of the numeric algorithms."

HTH,

Arthur

On Tue, Jun 25, 2019 at 10:46 AM Christopher Di Bella <cjdb.ns_at_[hidden]>

wrote:

> I'm researching what is necessary to bring the numeric algorithms into

> namespace std::ranges (for those wondering why it's non-trivial: they

> require close study like those in <algorithm> got from N3351 + ranges

> work). Part of this research involves me consistently scratching my head

> over whether or not all of the numeric algorithms should be imported into

> std::ranges, or if it's possible to get away with just reduce,

> transform_reduce, exclusive_scan, inclusive_scan, transform_exclusive_scan,

> transform_inclusive_scan, and adjacent_difference. iota is deliberately

> not in that list, but that's also not relevant to the discussion I'm

> wanting to have.

>

> Note that I'm only considering the overloads without an ExecutionPolicy.

>

> Are there any practical reasons for reduce(begin(v), end(v), 0, plus{})

> to permit out-of-order computation? For example, is this allowed as an

> implementation?

>

> ```

> template<class InputIterator, class T, class BOp>

> T reduce(InputIterator first, InputIterator last, T init, BOp bop)

> {

> #if NDEBUG

> return reduce(execution::par_unseq, first, last, init, bop);

> #else

> return accumulate(first, last, init, bop);

> #endif // NDEBUG

> }

> ```

>

> If either question can be answered with "yes", then forgetting accumulate

> is a non-starter, and I'll work on nailing down all of the numeric

> algorithms. I suspect this is the case, but lack the experience to answer

> them myself, and am yet to find a proposal or minutes detailing this

> discussion.

>

> If there aren't advantages for this overload of reduce, et al. to

> co-exist with their C++98 counterparts, then I'm inclined to propose that

> only the C++17 names be ported (plus adjacent_difference), because:

>

> 1. It seems redundant for us to have two algorithms that are specified

> differently, but produce equivalent results.

> 1. The ExecutionPolicy numeric algorithms can still have formal

> requirements for associativity and commutativity.

> 2. I've had a teacher pass on a question to me from a student

> asking if they should be using accumulate or reduce, so I have

> teachability concerns.

> 1. It's likely that there are more than two people in the situation

> of 'Curious Student Reading the C++ Reference' and 'Hesitant Teacher'.

> 2. If there's only one name in namespace std::ranges, then advice

> boils down to "prefer what's in namespace std::ranges; the rest are

> historical".

>

> Cheers,

>

> Chris

>

>

If you're doing design work on <numeric>, then I EXTREMELY strongly

recommend watching Conor Hoekstra's talk "Algorithm Intuition"

<https://www.youtube.com/watch?v=48gV1SNm3WA> (from this year's C++Now)

first. Some design takeaways:

- Having "default" functors causes more confusion than help. The fact that

some numeric algorithms default to std::plus (std::reduce) and others to

std::minus (std::adjacent_difference) adds to the difficulty in developing

intuition about these algorithms.

- The historical naming of these algorithms is asymmetric and inconsistent

(just like their placement outside of <algorithm>). New "modern" versions

should go in <algorithm> so that learners of algorithms don't have to worry

about numerics.

- As pointed out in the Q&A, <numeric> is a misnomer for these abstract

algorithms anyway. For example,`std::inner_product` over doubles does not

compute a mathematically precise answer; "transform-reduce with std::plus

and std::times" is an unrealistically naïve way to compute "inner product."

The name of the algorithm should reflect its purpose, and the placement of

the algorithm should reflect its level of numeric sophistication.

- Having a 1-range version of `transform` and a 2-range version of

`transform`, sharing the same overload set, is a source of confusion.

Having 1- and 2-range versions but no 3- or 4-range versions (that is: the

original `std::transform` pre-dates variadic templates) is also a source of

confusion for programmers used to variadic `zip`.

Procedural issue: Your original message would have been clearer if you

could list not only the 7 algorithms you did, but also the (N??) algorithms

that are on your list of "all of the numeric algorithms."

HTH,

Arthur

On Tue, Jun 25, 2019 at 10:46 AM Christopher Di Bella <cjdb.ns_at_[hidden]>

wrote:

> I'm researching what is necessary to bring the numeric algorithms into

> namespace std::ranges (for those wondering why it's non-trivial: they

> require close study like those in <algorithm> got from N3351 + ranges

> work). Part of this research involves me consistently scratching my head

> over whether or not all of the numeric algorithms should be imported into

> std::ranges, or if it's possible to get away with just reduce,

> transform_reduce, exclusive_scan, inclusive_scan, transform_exclusive_scan,

> transform_inclusive_scan, and adjacent_difference. iota is deliberately

> not in that list, but that's also not relevant to the discussion I'm

> wanting to have.

>

> Note that I'm only considering the overloads without an ExecutionPolicy.

>

> Are there any practical reasons for reduce(begin(v), end(v), 0, plus{})

> to permit out-of-order computation? For example, is this allowed as an

> implementation?

>

> ```

> template<class InputIterator, class T, class BOp>

> T reduce(InputIterator first, InputIterator last, T init, BOp bop)

> {

> #if NDEBUG

> return reduce(execution::par_unseq, first, last, init, bop);

> #else

> return accumulate(first, last, init, bop);

> #endif // NDEBUG

> }

> ```

>

> If either question can be answered with "yes", then forgetting accumulate

> is a non-starter, and I'll work on nailing down all of the numeric

> algorithms. I suspect this is the case, but lack the experience to answer

> them myself, and am yet to find a proposal or minutes detailing this

> discussion.

>

> If there aren't advantages for this overload of reduce, et al. to

> co-exist with their C++98 counterparts, then I'm inclined to propose that

> only the C++17 names be ported (plus adjacent_difference), because:

>

> 1. It seems redundant for us to have two algorithms that are specified

> differently, but produce equivalent results.

> 1. The ExecutionPolicy numeric algorithms can still have formal

> requirements for associativity and commutativity.

> 2. I've had a teacher pass on a question to me from a student

> asking if they should be using accumulate or reduce, so I have

> teachability concerns.

> 1. It's likely that there are more than two people in the situation

> of 'Curious Student Reading the C++ Reference' and 'Hesitant Teacher'.

> 2. If there's only one name in namespace std::ranges, then advice

> boils down to "prefer what's in namespace std::ranges; the rest are

> historical".

>

> Cheers,

>

> Chris

>

>

Received on 2019-06-25 11:47:20