Bug 12655 – foldRange

In the C++ STL there is an useful algorithm, that is not well named: http://en.cppreference.com/w/cpp/algorithm/partial_sum An usage example (it does more than just sums): int main() { std::vector<int> v = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}; std::cout << "The first 10 even numbers are: "; std::partial_sum(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, " ")); std::cout << '\n'; std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>()); std::cout << "The first 10 powers of 2 are: "; for (auto n : v) { std::cout << n << " "; } std::cout << '\n'; } The first 10 even numbers are: 2 4 6 8 10 12 14 16 18 20 The first 10 powers of 2 are: 2 4 8 16 32 64 128 256 512 1024 I suggest to add to std.algorithm a related algorithm (with a better name), a lazy range like a reduce/fold that yields all the intermediate results. It is the function present in Mathematica here, named FoldList, but the D version is a lazy range, so a name for the D version is "foldRange" (or "reduceReange"): http://reference.wolfram.com/mathematica/ref/FoldList.html [a, b, ...].foldRange!f(seed) ==> [seed, f(seed, a), f(f(seed, a), b), ...] So given a range of length N it yields a range of length N + 1. A version without seed could also be available. Cumulative sums of the elements of an array: [10, 20, 30, 40].foldRange!q{a + b}(0) ==> [0, 10, 30, 60, 100] [2, 2, 2, 2, 2, 2, 2, 2, 2, 2].foldRange!q{a + b}(0) ==> [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

Optionally the a+b could be the default operation, like in C++: [10, 20, 30, 40].foldRange(0) ==> [0, 10, 30, 60, 100]

*** Issue 13029 has been marked as a duplicate of this issue. ***

A cumulate returning the same number elements can be written using map. auto cumulate(alias f, R, T)(R r, T seed) if (isInputRange!R && is(T == ElementType!R)) { import std.algorithm : map; return r.map!(a => a = seed = f(seed, a)); } I leave this here for reference and others to decide whether such a function should be added to Phobos.

(In reply to jens.k.mueller from comment #3) > A cumulate returning the same number elements can be written using map. > ... > I leave this here for reference and others to decide whether such a function > should be added to Phobos. It's often a bad idea to define *basic* ranges in terms of others. Because they lose performance. You get short sexy elegant code that dooms all the user code to be slow (sometimes even if you compile with optimizations on).

I just added a github repository that includes this functionality. I named it scan instead of foldRange because I found scan in more languages. Any feedback is welcome. https://github.com/jmh530/scan

This can probably be closed now that D 2.072.0 adds cumulativeFold.