cumulativeFold

Similar to fold, but returns a range containing the successive reduced values. The call cumulativeFold!(fun)(range, seed) first assigns seed to an internal variable result, also called the accumulator. The returned range contains the values result = fun(result, x) lazily evaluated for each element x in range. Finally, the last element has the same value as fold!(fun)(seed, range). The one-argument version cumulativeFold!(fun)(range) works similarly, but it returns the first element unchanged and uses it as seed for the next elements. This function is also known as partial_sum, accumulate, scan, Cumulative Sum.

  1. auto cumulativeFold(R range)
    template cumulativeFold(fun...)
    cumulativeFold
    (
    R
    )
    ()
    if (
    isInputRange!(Unqual!R)
    )
    if (
    fun.length >= 1
    )
  2. auto cumulativeFold(R range, S seed)

Members

Functions

cumulativeFold
auto cumulativeFold(R range)

No-seed version. The first element of r is used as the seed's value. For each function f in fun, the corresponding seed type S is Unqual!(typeof(f(e, e))), where e is an element of r: ElementType!R. Once S has been determined, then S s = e; and s = f(s, e); must both be legal.

cumulativeFold
auto cumulativeFold(R range, S seed)

Seed version. The seed should be a single value if fun is a single function. If fun is multiple functions, then seed should be a std.typecons.Tuple, with one field per function in f. For convenience, if the seed is const, or has qualified fields, then cumulativeFold will operate on an unqualified copy. If this happens then the returned type will not perfectly match S.

Parameters

fun

one or more functions to use as fold operation

Return Value

The function returns a range containing the consecutive reduced values. If there is more than one fun, the element type will be std.typecons.Tuple containing one element for each fun.

Examples

1 import std.algorithm.comparison : max, min;
2 import std.array : array;
3 import std.math : approxEqual;
4 import std.range : chain;
5 
6 int[] arr = [1, 2, 3, 4, 5];
7 // Partial sum of all elements
8 auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
9 assert(sum.array == [1, 3, 6, 10, 15]);
10 
11 // Partial sum again, using a string predicate with "a" and "b"
12 auto sum2 = cumulativeFold!"a + b"(arr, 0);
13 assert(sum2.array == [1, 3, 6, 10, 15]);
14 
15 // Compute the partial maximum of all elements
16 auto largest = cumulativeFold!max(arr);
17 assert(largest.array == [1, 2, 3, 4, 5]);
18 
19 // Partial max again, but with Uniform Function Call Syntax (UFCS)
20 largest = arr.cumulativeFold!max;
21 assert(largest.array == [1, 2, 3, 4, 5]);
22 
23 // Partial count of odd elements
24 auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
25 assert(odds.array == [1, 1, 2, 2, 3]);
26 
27 // Compute the partial sum of squares
28 auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
29 assert(ssquares.array == [1, 5, 14, 30, 55]);
30 
31 // Chain multiple ranges into seed
32 int[] a = [3, 4];
33 int[] b = [100];
34 auto r = cumulativeFold!"a + b"(chain(a, b));
35 assert(r.array == [3, 7, 107]);
36 
37 // Mixing convertible types is fair game, too
38 double[] c = [2.5, 3.0];
39 auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
40 assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5]));
41 
42 // To minimize nesting of parentheses, Uniform Function Call Syntax can be used
43 auto r2 = chain(a, b, c).cumulativeFold!"a + b";
44 assert(approxEqual(r2, [3, 7, 107, 109.5, 112.5]));

Sometimes it is very useful to compute multiple aggregates in one pass. One advantage is that the computation is faster because the looping overhead is shared. That's why cumulativeFold accepts multiple functions. If two or more functions are passed, cumulativeFold returns a std.typecons.Tuple object with one member per passed-in function. The number of seeds must be correspondingly increased.

1 import std.algorithm.comparison : max, min;
2 import std.algorithm.iteration : map;
3 import std.math : approxEqual;
4 import std.typecons : tuple;
5 
6 double[] a = [3.0, 4, 7, 11, 3, 2, 5];
7 // Compute minimum and maximum in one pass
8 auto r = a.cumulativeFold!(min, max);
9 // The type of r is Tuple!(int, int)
10 assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // minimum
11 assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // maximum
12 
13 // Compute sum and sum of squares in one pass
14 auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
15 assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // sum
16 assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // sum of squares

See Also

Meta