2
\$\begingroup\$

Background

I found myself needing some M equivalent of cumsum() from R. After some frustrating research, I discovered that there is little support for cumulative operations in PowerQuery.

I set out to implement a function for cumulative summation, but I soon realized this approach could be generalized to any list function like List.Sum(). Borrowing function factories from R, I propose a convenient and extensible solution in M.

Solution

Function_AsCumulative()

This is a function factory, and it generates the cumulative version of a function.

let Function_AsCumulative = (
    // The function itself, of the form 'function(list, ...)'.
    function as function
) as function =>
    // Generate the cumulative function.
    (
        // The list over which to cumulatively invoke the function.
        list as list,
        
        // Further arguments ('...') passed to 'function(list, ...)'.
        optional args as nullable list
    ) as list =>
        let
            // Default to no arguments.
            args = if args = null then
                {}
            else
                args,
            
            // Short-circuit for an empty list... 
            result = if List.IsEmpty(list) then
                {}
                
            // ...and otherwise accumulate the values for each subset.
            else
                let
                    // Take every subset S_k = {l_1, 1_2, ..., l_k}
                    // of the list L = {l_1, l_2, ..., l_k, ..., l_n}...
                    count = List.Count(list),
                    indices = List.Numbers(1, count, 1),
                    accumulation = List.Transform(indices, each Function.Invoke(
                        
                    // ...and compile its return value x_k = function(S_k, ...).
                        function, List.Combine({{List.FirstN(list, _)}, args})
                    //  ^^^^^^^^                 ^^^^^^^^^^^^^^^^^^^^   ^^^^
                    //  function (                        S_k         ,  ... )
                    ))
                in
                    accumulation
        in
            result
in
    Function_AsCumulative

Function_InvokeCumulative()

This invokes a function cumulatively over a list.

let Function_InvokeCumulative = (
    // The list over which to cumulatively invoke the function.
    list as list,
    
    // The function itself, of the form 'function(list, ...)'.
    function as function,
    
    // Further arguments ('...') passed to 'function(list, ...)'.
    optional args as nullable list
) as list =>
    let
        // Generate the cumulative version of the function.
        cFun = Function_AsCumulative(function),
        
        // Invoke the cumulative function to obtain the cumulative result.
        result = cFun(list, args)
    in
        result
in
    Function_InvokeCumulative

Note

If the original function accepts further arguments (...) beyond the list, then those further arguments may be passed as a list ({...}) to the args parameter. This args parameter is found both in Function_InvokeCumulative() itself, and also in any cumulative function generated by Function_AsCumulative().

Application

One can generate the function List_CumulativeSum() by invoking Function_AsCumulative() on List.Sum():

List_CumulativeSum = Function_AsCumulative(List.Sum)

So calling

List_CumulativeSum({1..10})

is equivalent to calling

Function_InvokeCumulative(List.Sum, {1..10})

and it returns the following list:

{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}

Alternative

Some time ago I posted an alternative solution, which should run in 𝑂(𝑛) rather than 𝑂(𝑛²) time, but which is restricted to binary operations (β—¦) that obey the generalized associative law:

(((β‹―((π‘₯₁ β—¦ π‘₯β‚‚) β—¦ π‘₯₃) β—¦ β‹―) β—¦ π‘₯β‚™β‚‹β‚‚) β—¦ π‘₯ₙ₋₁) β—¦ π‘₯β‚™

= (π‘₯₁ β—¦ π‘₯β‚‚ β—¦ π‘₯₃ β—¦ β‹― β—¦ π‘₯β‚™β‚‹β‚‚ β—¦ π‘₯ₙ₋₁) β—¦ π‘₯β‚™

= π‘₯₁ β—¦ π‘₯β‚‚ β—¦ π‘₯₃ β—¦ β‹― β—¦ π‘₯β‚™β‚‹β‚‚ β—¦ π‘₯ₙ₋₁ β—¦ π‘₯β‚™.

Workhorses

The function Function_MakeCumulative() is a function factory. It accepts a function as input, and returns a cumulative version of that function, of the form Fun(list, args, skip):

Function_MakeCumulative = (
    // The function itself, of the form 'Fun(x, y, ...)'.
    function as function,

    // The default seed for when we do not skip.
    optional default as nullable any
) as function =>
    // Generate the cumulative function.
    (
        list as list,
        optional skip as nullable logical,
        optional args as nullable list
    ) as list =>
        let
            // Default 'skip' to positive ('true').
            skip = if skip = null then
                true
            else
                skip,
            
            // Default 'args' to none ('{}').
            args = if args = null then
                {}
            else
                args,
            
            // Assemble a list with the running values.
            result = if skip = true then
                // When skipping, use the first element and accumulate afterwards.
                List.Accumulate(
                    List.RemoveFirstN(list, 1),
                    {List.First(list, {})},
                    (state, current) => List.Combine({
                        state, {
                        Function.Invoke(function, List.Combine({
                            {List.Last(state, {})},
                            {current},
                            args
                        }))
                    }})
                )
            else
                // When not skipping, start with the default and accumulate everything.
                List.Accumulate(
                    list,
                    {},
                    (state, current) => List.Combine({state, {
                        Function.Invoke(function, List.Combine({
                            {List.Last(state, default)},
                            {current},
                            args
                        }))
                    }})
                )
        in
            result

The function Function_InvokeCumulative() accepts a function and a list as input, and invokes that function cumulatively over the list.

Function_InvokeCumulative = (
    // The list over which to cumulatively invoke the function.
    list as list,

    // The function itself, of the form 'Fun(x, y, ...)'.
    function as function,

    // Should the first value be the first element ('true') in the list, as is; or should
    // we generate it ('false') by calling the function on that element and some seed?
    optional skip as nullable logical,

    // The default seed for when we do not skip.
    optional default as nullable any,
    
    // Further arguments ('...') passed to 'Fun(x, y, ...)'.
    optional args as nullable list
) as list =>
    let
        // Default 'skip' to affirmative ('true').
        skip = if skip = null then
            true
        else
            skip,
        
        // Default 'args' to none ('{}').
        args = if args = null then
            {}
        else
            args,
        
        // Generate the cumulative version of the function.
        cFun = Function_MakeCumulative(function, default),

        // Invoke the cumulative function to obtain the cumulative result.
        result = cFun(list, skip, args)
    in
        result

Note

The first element of the output list may be generated in one of two ways.

  • When skip is true by default, then the first element is simply taken "as is" from the input list.
  • When skip is false, then the first element is taken from the
    input list, and next the function is invoked with that element and the default as its operands.

When cumulatively performing + on a list {1,2,3}, the former approach will use 1 as the first element; while the latter will use 0 + 1, where 0 is the identity element for +.

Application

Here I define a function Op_Sum(), which functionally implements the summation operation (+). More generally, Op_Sum() hails from the Op_*() family, which functionally implements various binary operations.

Op_Sum = (x, y) =>
    x + y

I complement Op_Sum() with Id_Sum, which defines the identity element (0) for summation. More generally, Id_Sum hails from the Id_* family, which defines the identity elements for various operations.

Id_Sum = 0

Finally, I generate a function Cumulative_Sum() by invoking Function_MakeCumulative() on Op_Sum() with Id_Sum:

Cumulative_Sum = Function_MakeCumulative(Op_Sum, Id_Sum)

So calling

Cumulative_Sum({1..10})

is equivalent to calling

Function_InvokeCumulative((x, y) => x + y, {1..10})

and it returns the following list:

{1, 3, 6, 10, 15, 21, 28, 36, 45, 55}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ In excel this is called SCAN() which takes a lambda and an array to reduce using an accumulator, but unlike the REDUCE function it will output intermediate steps like you have. So maybe stick with that naming convention for consistency. My worry with this is that PQ is not "meant" to perform row-wise functions as they can't be vectorised so it will probably be quite slow and most usecases you should prefer some other approach that is more idiomatic \$\endgroup\$
    – Greedo
    Commented Dec 19, 2023 at 15:26
  • \$\begingroup\$ @Greedo I actually found a specialized solution with List.Accumulate() that should run in 𝑂(𝑛) time, rather than the 𝑂(𝑛²) here. Unfortunately, it only works for a binary operation β—¦ (like +) that obeys the generalized associative law: (((β‹―((π‘₯₁ β—¦ π‘₯β‚‚) β—¦ π‘₯₃) β—¦ β‹―) β—¦ π‘₯β‚™β‚‹β‚‚) β—¦ π‘₯ₙ₋₁) β—¦ π‘₯β‚™ = (π‘₯₁ β—¦ π‘₯β‚‚ β—¦ π‘₯₃ β—¦ β‹― β—¦ π‘₯β‚™β‚‹β‚‚ β—¦ π‘₯ₙ₋₁) β—¦ π‘₯β‚™ = π‘₯₁ β—¦ π‘₯β‚‚ β—¦ π‘₯₃ β—¦ β‹― β—¦ π‘₯β‚™β‚‹β‚‚ β—¦ π‘₯ₙ₋₁ β—¦ π‘₯β‚™. It obviously fails when (say) you wish to take a cumulative average. \$\endgroup\$
    – Greg
    Commented Dec 19, 2023 at 18:17
  • \$\begingroup\$ @Greedo I have appended that older, specialized solution. \$\endgroup\$
    – Greg
    Commented Dec 19, 2023 at 18:36

0

Your Answer

By clicking β€œPost Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.