## digitalmars.D - Function Proposal: std.algorithm.iteration : cumulativeSum

- e-y-e (102/102) Nov 01 2016 ===
- e-y-e (3/21) Nov 01 2016 Apologies to those reading on mobile or in a non-monospace font
- Ivan Kazmenko (4/8) Nov 01 2016 DMD 2.072 just got cumulativeFold:
- e-y-e (2/10) Nov 01 2016 damn, that was a typo [cumulativeFold -> cumulativeSum]
- e-y-e (3/7) Nov 01 2016 similarly, in the first para, cumulativeSum!((a, b) => a + b)(r,
- Ivan Kazmenko (8/16) Nov 01 2016 Ouch, and I completely misread the TL;DR paragraph, sorry for the
- e-y-e (8/16) Nov 01 2016 To be entirely honest, I haven't experienced any _problems_ with
- jmh530 (5/8) Nov 01 2016 I was happy to see that.
- e-y-e (2/3) Nov 02 2016 bump : any more opinions?

=== TL;DR: The proposed function takes an input range and an optional seed and provides an input range containing the intermediate results of the summation of the given range. As of 2.072 this behaviour can be emulated by cumulativeSum!((a, b) => a + b)(r, s), but cumulativeSum involves a specialization for accurate summation of floating point values and redirects to cumulativeFold for non-floating point values. The proposed function would be useful for those doing basic statistical analysis on data sets, but would also have applications in other fields. Please let me know in this thread whether you would have a use for this function (or if you think it should/shouldn't be in phobos) === I'd like to propose the function cumulativeFold as a new addition to std.algorithm.iteration. I have already opened a pull request [1] for this addition so the full implementation is available there. The function signatures are: auto cumulativeSum(Range)(Range r) if (isInputRange!Range && __traits(compiles, r.front + r.front)) auto cumulativeSum(Range, Seed)(Range r, Seed s) if (isInputRange!Range && __traits(compiles, s = s + r.front)) The function returns an input range that contains the intermediate results of a summation on all of the elements of a given range. For more details see Prefix Sum [2]. My motivation for adding this function to phobos was originally that I came across a need for it. I was looking into genetic algorithms and I wanted to implement some variation of the Stochastic Universal Sampling [3] selection method, which requires the fitness values of the population to be sorted and then selected based on the cumulative sum up to that point. Phobos was the first place I looked to for an implementation of cumulativeSum, as I knew that it had an implementation of sum, and cumulativeSum is a great use of D's ranges that I assumed would be in phobos. I couldn't find it, but found cumulativeFold instead. However, from reading the docs on sum, I knew that sum was a specialization of fold for accurate floating point summation, and given that I would be summing floating point values it would be better if the algorithm I used also involved this type of specialization. With the knowledge that cumulativeFold is now in phobos, I realized that this presented quite an obvious gap in this area of summation and reduction. This gap is best illustrated by this table: | Provides no intermediate results | Provides intermediate results -------------|----------------------------------|------------------------------- Not | | specialized | fold | cumulativeFold for accurate | | summation | | -------------|----------------------------------|------------------------------- Specialized | | for accurate | sum | X summation | | So now what would people other than me use this function for, or in other words, why should it be in phobos? Firstly, from a purely logical point of view, cumulative sums can be a useful way of analysing data. Once the data can be converted into a cumulative sum, then it is trivial to know what the current running total is when consuming the data. IE rather than keeping state like so [trivial example]: void displayDataset(Data)(Data d, double total) { double sum = 0.0; while (true) { if (d.empty) break; sum += d.front; if (sum > total) break; writeln("Data point: ", d.front, ", sum: ", sum); d.popFront; } } Range based code can now be written with ease to perform the same job: void displayDataset(Data)(Data d, double total) { d .zip(d.cumulativeSum) .until!(t => t[1] > total) .each!(t => writeln("Data point: ", t[0], ", sum:", t[1])); } Some other useful applications are: - Graphing an integral of a range of y values without calculating the actual integral. - Computing a series summation with increasing accuracy (a la Fourier). - Keeping a running mean of incoming data. Thanks for reading if you got this far, let me know whether you love/hate the idea. P.S: its late here so I may only be able to read/respond tomorrow. === [1] https://github.com/dlang/phobos/pull/4881 [2] https://en.wikipedia.org/wiki/Prefix_sum [3] https://en.wikipedia.org/wiki/Stochastic_universal_sampling

Nov 01 2016

On Tuesday, 1 November 2016 at 21:52:40 UTC, e-y-e wrote:... this table: | Provides no intermediate results | Provides intermediate results -------------|----------------------------------|------------------------------- Not | | specialized | fold | cumulativeFold for accurate | | summation | | -------------|----------------------------------|------------------------------- Specialized | | for accurate | sum | X summation | | ...Apologies to those reading on mobile or in a non-monospace font for this table.

Nov 01 2016

On Tuesday, 1 November 2016 at 21:52:40 UTC, e-y-e wrote:I'd like to propose the function cumulativeFold as a new addition to std.algorithm.iteration. I have already opened a pull request [1] for this addition so the full implementation is available there. The function signatures are:DMD 2.072 just got cumulativeFold: https://dlang.org/changelog/2.072.0.html#std-algorithm-iteration-cumulativeFold https://dlang.org/phobos/std_algorithm_iteration.html#cumulativeFold

Nov 01 2016

On Tuesday, 1 November 2016 at 22:06:36 UTC, Ivan Kazmenko wrote:On Tuesday, 1 November 2016 at 21:52:40 UTC, e-y-e wrote:damn, that was a typo [cumulativeFold -> cumulativeSum]I'd like to propose the function cumulativeFold as a new addition to std.algorithm.iteration. I have already opened a pull request [1] for this addition so the full implementation is available there. The function signatures are:DMD 2.072 just got cumulativeFold: https://dlang.org/changelog/2.072.0.html#std-algorithm-iteration-cumulativeFold https://dlang.org/phobos/std_algorithm_iteration.html#cumulativeFold

Nov 01 2016

On Tuesday, 1 November 2016 at 22:09:50 UTC, e-y-e wrote:On Tuesday, 1 November 2016 at 22:06:36 UTC, Ivan Kazmenko wrote:similarly, in the first para, cumulativeSum!((a, b) => a + b)(r, s) -> cumulativeFold!((a, b) => a + b)(r, s)...damn, that was a typo [cumulativeFold -> cumulativeSum]

Nov 01 2016

On Tuesday, 1 November 2016 at 22:13:29 UTC, e-y-e wrote:On Tuesday, 1 November 2016 at 22:09:50 UTC, e-y-e wrote:Ouch, and I completely misread the TL;DR paragraph, sorry for the noise! It's logical to have cumulativeSum specialized from cumulativeFold when sum is a specialization of fold. I have yet to write a program which relies on Kahan summation, but I can imagine that being useful. Ivan Kazmenko.On Tuesday, 1 November 2016 at 22:06:36 UTC, Ivan Kazmenko wrote:similarly, in the first para, cumulativeSum!((a, b) => a + b)(r, s) -> cumulativeFold!((a, b) => a + b)(r, s)...damn, that was a typo [cumulativeFold -> cumulativeSum]

Nov 01 2016

On Tuesday, 1 November 2016 at 22:22:17 UTC, Ivan Kazmenko wrote:On Tuesday, 1 November 2016 at 22:13:29 UTC, e-y-e wrote:My fault, note to self: always re-read everything....Ouch, and I completely misread the TL;DR paragraph, sorry for the noise!It's logical to have cumulativeSum specialized from cumulativeFold when sum is a specialization of fold. I have yet to write a program which relies on Kahan summation, but I can imagine that being useful.To be entirely honest, I haven't experienced any _problems_ with the accuracy of naive summation. But Kahan summation does improve accuracy in some cases and I want that assurance. It does have its own inaccuracies though and I think (may be wrong, again, its late) a flag like -ffastmath would probably eliminate any accuracy gain.

Nov 01 2016

On Tuesday, 1 November 2016 at 22:06:36 UTC, Ivan Kazmenko wrote:DMD 2.072 just got cumulativeFold: https://dlang.org/changelog/2.072.0.html#std-algorithm-iteration-cumulativeFold https://dlang.org/phobos/std_algorithm_iteration.html#cumulativeFoldI was happy to see that. I'm surprised there wasn't more angst about the name. cumulativeSum should be cumsum, which implies that cumulativeFold should be cumfold, IMO.

Nov 01 2016

On Wednesday, 2 November 2016 at 00:41:38 UTC, jmh530 wrote:On Tuesday, 1 November 2016 at 22:06:36 UTC, Ivan Kazmenko wrote:I think there's an obvious reason as to why they're not called that.DMD 2.072 just got cumulativeFold: https://dlang.org/changelog/2.072.0.html#std-algorithm-iteration-cumulativeFold https://dlang.org/phobos/std_algorithm_iteration.html#cumulativeFoldI was happy to see that. I'm surprised there wasn't more angst about the name. cumulativeSum should be cumsum, which implies that cumulativeFold should be cumfold, IMO.

Nov 02 2016

On Wednesday, 2 November 2016 at 20:03:59 UTC, Meta wrote:I think there's an obvious reason as to why they're not called that.I almost always see languages call it cumsum rather than cumulativeSum. R - https://stat.ethz.ch/R-manual/R-devel/library/base/html/cumsum.html Matlab - https://www.mathworks.com/help/matlab/ref/cumsum.html Python - https://docs.scipy.org/doc/numpy/reference/generated/numpy.cumsum.html The only exceptions I could find were languages that called it something else, like Accumulate in Mathematica or the scan functions noted in the cumulativeFold function doc. In practice, I would probably just create an alias.

Nov 02 2016

On Tuesday, 1 November 2016 at 21:52:40 UTC, e-y-e wrote:...bump : any more opinions?

Nov 02 2016