• via Digitalmars-d-bugs (49/49) Apr 26 2014 https://issues.dlang.org/show_bug.cgi?id=12655

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

https://issues.dlang.org/show_bug.cgi?id=12655

          Issue ID: 12655
           Summary: foldRange
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: enhancement
          Priority: P1
         Component: Phobos
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

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]

--