Forum Discussion

LBROWN7's avatar
LBROWN7
Brass Contributor
Oct 09, 2023

Recursive LAMBDA implementation of Excel's REDUCE function.

Not a question -- just sharing some interesting code. Out of curiosity, I decided to develop an implementation of Excel's REDUCE function as a recursive Excel LAMDA function.  I was truly amazed how...
excel
Formulas and Functions
lori_m's avatar
lori_m
Steel Contributor
Oct 12, 2023

LBROWN7 

Interesting method using LET recursively like that - thanks for posting.
One way to work around stack limits could be to use a binary tree method:

REDUCE2 = LAMBDA(initial_value, array, function,
    IF(
        COLUMNS(array) = 1,
        function(initial_value, array),
        REDUCE2(
            REDUCE2(
                initial_value,
                TAKE(array, , COLUMNS(array) / 2),
                function
            ),
            DROP(array, , COLUMNS(array) / 2),
            function
        )
    )
)

 

For a 2D version of BYROW (faster than REDUCE/VSTACK alternative):

BYROW2 = LAMBDA(array, function,
    IF(
        ROWS(array) = 1,
        function(array),
        VSTACK(
            BYROW2(TAKE(array, ROWS(array) / 2), function),
            BYROW2(DROP(array, ROWS(array) / 2), function)
        )
    )
)


These are both based on examples shared by PeterBartholomew1 

PeterBartholomew1's avatar
PeterBartholomew1
Silver Contributor
Oct 12, 2023

lori_m 

OwenPrice posted a discussion as an article

(2) Excel LAMBDA Spotlight: Bisected Map with BMAPλ | LinkedIn

The focus there is to stack mapped arrays but with minor changes one can apply a closely-related function to a SCAN with array outputs.  All that is needed is to pass a term from the prior stack to initialize the following one.

 

Now as we can get around the unfortunate 'nested array' and 'array of array' issues with recursion, perhaps it is time to go back to Microsoft with the request that they implement such functionality as native formulas.  As I travel in the direction of building ever larger elements of any solution within a single Lambda function, hitting these limitations is becoming the norm rather than the exception.

 

 

 

  • lori_m's avatar
    lori_m
    Steel Contributor
    Oct 12, 2023

    PeterBartholomew1 

    I was vaguely aware of a recommendation for a lambda spotlight article 🙂 A modification for SCAN allowing for column vectors might be,

    SCAN2=LAMBDA(initial_value, array, function,
    IF(COLUMNS(array) = 1,
        function(initial_value, array),
        LET(
            acc, SCAN2(initial_value, DROP(array, , -COLUMNS(array)/2), function),
            HSTACK(acc, 
                SCAN2(TAKE(acc, , -1), TAKE(array, , -COLUMNS(array)/2), function)
            )
        )
    )
)

    Then the formula in the other LBROWN7 thread returns expected results (with NAs),
    =SCAN2({1},{2,3,4},LAMBDA(a,b,VSTACK(a,b)))


    I'd think requesting array versions of map and scan functions would be sufficient for a majority of use cases. Going with current trends XMAP and XSCAN might be sufficient if able to accommodate 2D input arrays in row major order. 


    An advantage of the anonymous recursion implementation is that unchanged variables may be moved outside the recursive definition as in the 'vec' definition in the original post. Additionally, perhaps we can remove the 'func' definition and just use function(array) in the first SergeiBaklan  ByRow2 definition.

    • SergeiBaklan's avatar
      SergeiBaklan
      MVP
      Oct 13, 2023

      lori_m 

      That could be great workaround. However, performance with SCAN is still not good. Tried poor thunking

      SCAN3 = LAMBDA(initial_value, array, function,
    LET(
        sc, SCAN(LAMBDA(initial_value), array, LAMBDA(a, v, LAMBDA(function(a(), v)))),
        n, COLUMNS(sc),
        res, LAMBDA(ME, k,
            IF( k = 1,
                INDEX(sc, 1, 1)(),
                HSTACK(ME(ME, k - 1), INDEX(sc, 1, k)() ))),
        res(res, n)
    )
)

      but that gives nothing.

      Native function is required. Not sure Microsoft will do it, it looks like all efforts now are concentrated on Python.

       

      • LBROWN7's avatar
        LBROWN7
        Brass Contributor
        Oct 13, 2023

        HI SergeiBaklan

        I added an explicit stack parameter to the recursive scan and that seems to do the trick.

         

        =LAMBDA(initial_value, array, CLAMBDA,
    LET(
        _00, "Implementation of SCAN in Excel Lambda",
        _01, "accumulator must be a scalar or  column vector"
        vec, TOROW(array),
        rec_L, LAMBDA(stack, acc, cindex, rec_LL,
            LET(
                cvalue, INDEX(vec, 0, cindex),
                new_acc, CLAMBDA(acc, cvalue),
                new_stack, HSTACK(stack, new_acc),
                IF(
                    cindex = COLUMNS(vec),
                    new_stack,
                    rec_LL(new_stack, new_acc, cindex + 1, rec_LL)
                )
            )
        ),
        tresult, (rec_L(initial_value, initial_value, 1, rec_L)),
        MAP(tresult, LAMBDA(v, IF(ISERROR(v), "", v)))
    )
)({1}, {2, 3, 4}, LAMBDA(a, b, VSTACK(a, b)))

         


        Probably need to add code to drop the 1st column - but above seems to be moving in the right direction.

        1111
         222
          33
           4



Resources