LINQ: Folding Left, Right And The LINQ Aggregation Operator

A few days ago I blogged about Curry for Dummies, outlining one of the typical techniques employed in functional programming. What I didn't say back then is I'm about to reuse the "Curry" function with formal substitution mechanism for this subsequent blog post. Just as a quick refresher:

LambdaExpression Curry(LambdaExpression func, params Expression[] parameters);

used like this:

LambdaExpression add1 = Curry((int a, int b) => Add(a, b), Expression.Constant(1));

produces this:

b => Add(1, b)

But what's up this time? Today we're going to look at a few notable functions from the realm of functional programming: folds. A fold is a higher-order function that knows how to "fold" a given data structure (typically a sequence of elements) into a single return value. There are two sorts of folds, a left fold and a (surprisingly) right fold. The difference is the way the data is "folded", as will become apparent in a minute. Assume you have some sequence of numbers:

source = { 1, 2, 3, 4, 5, 6 }
source :: IEnumerable<TSource>

To be able to do folding one needs a base value, also known as the seed. Let's assume it's 1, thus:

seed = 1
seed :: TAccumulate

Folding proceeds as follows. It takes the seed and combines it with an element from the source to produce a new value in the same value domain as the seed. For instance, it could multiply the two numbers:

fold = (acc, val) => acc * val
fold :: Func<TAccumulate, TSource, TAccumulate>

This function is called repeatedly to combine all the values to come up with a single resulting value in the TAccumulate value domain, e.g.:

fold(fold(fold(fold(fold(fold(1,1),2),3),4),5),6) = 120
                              ^
^ = seed

Actually the statement above is underspecified:

It takes the seed and combines it with an element from the source to produce a new value in the same value domain as the seed.

The sample I gave above is one that does a left fold: the an in the sentence above is determined in a left-to-right fashion. If we define an in a right-to-left order we end up with a right fold:

fold(fold(fold(fold(fold(fold(1,6),5),4),3),2),1) = 120
                                  ^
^ = seed

Obviously both calculate factorial but in a different order. In Haskell both uses of the fold look like this:

facl n = foldl (*) 1 [1..n]
facr n = foldr (*) 1 [1..n]

where (*) is the infix multiplication operator and .. is the range operator. In LINQ, we actually do have the left folding operator, named Aggregate. It's defined like this (one of the three overloads):

public static TAccumulate Aggregate<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> func
)
{
    TAccumulate result = seed;
    foreach (var item in source)
    result = func(result, item);
    return result;
}

I didn't care about exception throwing conditions here, feel free to add those yourself. It should be apparent that this definition is a left fold. The fact we iterate over the source "from left to right" and accumulate with the current result value (that's initialized to the seed value initially) reveals this fact.

To test your understanding of folds so far, write a sum function for values 1..n by filling in the... below:

using System;
using System.Linq;

class Program
{
    static void Main()
    {
        Console.Write("Specify upper limit for sum: ");
        int n = int.Parse(Console.ReadLine());

        Console.WriteLine("Sum = " + Enumerable.Range(1, n).Aggregate(...));
    }
}

Tip: use a lambda expression for the second argument.

Playing with folds

Time to make things a little more complex. Would it be possible to express a right fold in terms of a left fold? This is the sort of question that keeps functional programmers awake at night :-). There's a solution to this problem indeed. Let's reason a bit about it.

First, notice we can't change the order in which we iterate over the source sequence, we still have to walk through it from left to right. However, to make things evaluate from right to left we first need to get all the way to the rightmost element in order to combine it with the seed. Once we're there, we can go back all the way to left, accumulating values from right to left.

The question now becomes how we can keep track of all the values we've already seen while walking from left to right so that "on the way back" we can apply the aggregation function? The answer is to use a function as the accumulator value. Why? In a nutshell because a function has the potential of deferring some execution, think about the following:

int one = 1;
int oneIfYouAskForIt = () => 1;
int oneIAskedFor = oneIfYouAskForIt();

What we need to do in this particular case is to build a function that tracks the entire history of sequence numbers, also knowing how to aggregate them, so that ultimately we can ask for the result simply by calling it. This call would put all the machinery inside the function to work, consuming all the tracked data.

Let's analyze the signature of Aggregate a bit further:

public static TAccumulate Aggregate<TSource, TAccumulate>(
    this IEnumerable<TSource> source,
    TAccumulate seed,
    Func<TAccumulate, TSource, TAccumulate> func
);

To concretize this generic function a bit more, let's substitute TSource for int and assume we'll deal with integers:

public static TAccumulate Aggregate<TAccumulate>(
    this IEnumerable<int> source,
    TAccumulate seed,
    Func<TAccumulate, int, TAccumulate> func
);

Now look at the third parameter: we need a function taking in an accumulator value and an integer, returning a new accumulator. Assume TAccumulate is some kind of function "f" and the integer is represented as "c" (for constant), the lambda we'd supply would look like:

(f, c) => ...

where the ellipsis needs to be filled in with something of the same type as f, i.e. a function with the same signature.

To go a little further in our analysis, let's look at the result we want to get. Accumulating a sequence of integers could result in many things, e.g. we could generate a string consisting of the comma-separating list of integers in their string representation. To make things easy though, assume the accumulation value will be an integer too, e.g. the sum or product of the sequence. It would be tempting to say that TAccumulate therefore needs to be an integer too. However, we already said we want TAccumulate to be a function and moreover, it should be one that "if we ask for it" gives us the result, which is an integer, back. So what about:

TAccumulate := Func<..., int>

which means our function will return an integer "if we ask for it". In other words, we can already call Aggregate like this:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => ...)(...);

Notice the extra function call at the end. Since Aggregate returns a function type with one argument, we'll have to call through it in order to get the integer result value back. We're still missing a few pieces though. What should be the type of the parameter to our accumulator? Well, what's the real seed we want to use? We already said, for simplification, we were going to aggregate a list of integers to another integer, so it's fairly reasonable to assume the seed value will be an integer too:

fold(fold(fold(fold(fold(fold(1,6),5),4),3),2),1) = 120
                                       ^
^ = seed

Based on this it definitely makes sense to define TAccumulate as:

TAccumulate := Func<int, int>

We're coming close now. With the substitution for TAccumulate the Aggregate signature now looks like:

public static Func<int, int> Aggregate<TAccumulate>(
    this IEnumerable<int> source,
    Func<int, int> seed,
    Func<Func<int, int>, int, Func<int, int>> func
);

Aggregate returns some function with this type, hence we need to call the result of Aggregate with some integer argument. The value we'll pass in here is the seed:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => ...)(1);

Next is to infer how the function argument should look like. Here's the type:

Func<Func<int, int>, int, Func<int, int>> func

so our lambda is really:

(Func<int, int> f, int c) => ...

where ... is also of type Func<int, int>. A quick analysis:

• What's the value of c? If you analyze the loop body of Aggregate you'll come to the conclusion it follows the input values from left to right.
• What's f supposed to be? This is our time-traveling device: it keeps track of all that needs to be calculated before we can process c in our aggregation journey.
• The result we need to give back is something that "when asked to do so" calls f "aggregating in" c but still being lazy since it has to be a Func<int, int>.

Assuming we want to create a factorial function, our aggregation operator will be *. So we have a Func<int, int> called f, an integer called c and another function * of type Func<int,int,int>. We're missing one integer in order to be able to call our * aggregator: let's call it x. Now we can write:

(Func<int, int> f, int c) => x => f(x * c)

Notice the lambda arrow is right associative, so in reality this is:

(Func<int, int> f, int c) => (x => f(x * c))

Analyzing the type of the result: x * c is an integer, calling f with an integer returns and integer, so f(x * c) is an integer too. Since x is an integer and f(x * c) is an integer, the lambda ought to be a Func<int, int>. Bingo! Almost there:

int res = Enumerable.Range(1, n).Aggregate(..., (f, c) => x => f(x * c))(1);

Remaining is the seed argument to the aggregate call. Again, it needs to be of type Func<int, int>. When and where does it kick in during the evaluation? Looking at the implementation of the Aggregate method:

Func<int, int> result = seed;
    foreach (var item in source)
        result = func(result, item);
    return result;

The seed is used the first time we call through the function and becomes part of the function's aggregated history for the subsequent iterations. We already are processing all the values of the source sequence, the multiplicative aggregation, so the only function that makes sense here is the identity function:

int res = Enumerable.Range(1, n).Aggregate(x => x, (f, c) => x => f(x * c))(1);

Phew, we're done. But can we figure out how does all this hocus pocus really works now? Let's trace it down a bit, with an input sequence { 1, 2, 3 }. Unfold the loop of the Aggregate implementation:

Func<int, int> result = x => x;
result = ((f, c) => x => f(x * c))(result, 1);
result = ((f, c) => x => f(x * c))(result, 2);
result = ((f, c) => x => f(x * c))(result, 3);
return result;

Here I'm using pseudo-syntax where calling through a lambda is directly supported. It's left as an exercise to the reader to find out whether this works in C# 3.0 and why (not). We already know from the Curry for Dummies post that "calling through a lambda" is beta-reduction which is carried out by means of formal substitution. To make things not mutate state, let's turn to single-assignment form, and to avoid confusing letters let's do an alpha-conversion too (i.e. renaming variables - or refactoring in geeky terms):

Func<int, int> result0 = x => x;
Func<int, int> result1 = ((f, c) => u => f(u * c))(result0, 1);
Func<int, int> result2 = ((g, d) => v => g(v * d))(result1, 2);
Func<int, int> result3 = ((h, e) => w => h(w * e))(result2, 3);
return result3;

Time to do the first substitution:

Func<int, int> result1 = ((f, c) => u => f(u * c))(x => x, 1);
Func<int, int> result1 = u => (x => x)(u * 1);

Next,

Func<int, int> result2 = ((g, d) => v => g(v * d))(u => (x => x)(u * 1), 2);
Func<int, int> result2 = v => (u => (x => x)(u * 1))(v * 2);

And finally:

Func<int, int> result3 = ((h, e) => w => h(w * e))(v => (u => (x => x)(u * 1))(v * 2), 3);
Func<int, int> result3 = w => (v => (u => (x => x)(u * 1))(v * 2))(w * 3);

Now to evaluate, we call result3 with argument 1:

result3(1)
= (w => (v => (u => (x => x)(u * 1))(v * 2))(w * 3))(1)
= (v => (u => (x => x)(u * 1))(v * 2))(1 * 3)
= (u => (x => x)(u * 1))((1 * 3) * 2)
= (x => x)(((1 * 3) * 2) * 1)
= ((1 * 3) * 2) * 1
= 6

And indeed, the evaluation order is 3 * 2 * 1. Magic! Who ever said lambda calculus and functional programming are boring?

Say it with code

To provide all of this works, let's talk LINQ for a bit first:

    int n = 5;

    //
    // Left fold == Aggregate in LINQ.
    //
    Console.WriteLine("LFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));

    Console.WriteLine();
    Console.WriteLine();

    //
    // Right fold in terms of left fold.
    //
    Console.WriteLine("RFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));

Not surprisingly this will print 120 twice. But can we go a bit further? What about putting expression trees to work and print how those would look like. As we know by know, lambdas can either represent anonymous methods or expression trees, which are code as data. Leaving the implementation of AggregateE as a trivial exercise to the reader, here's how we're about to call the two folds:

var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

    var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
        var x = Expression.Parameter(typeof(int), "x");
        return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
    });

As you can see, those definitions are identical to the ones used in the previous sample, but expressed in terms of expression trees. The fact we're creating aggregation functions that accumulate expression trees is the ultimate sample of function composition, even more, in a dynamic fashion. What can we do with such expression trees? Both folds above are lambda expressions (actually there are two AggregateE functions in use here, exercise for the reader), so we can dynamically compile them, producing a delegate, through which we can call at runtime to invoke the compiled expression trees:

int n = 5;

    var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

    var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
        var x = Expression.Parameter(typeof(int), "x");
        return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
    });

    //
    // Left fold == Aggregate in LINQ.
    //
    Console.WriteLine("LFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));
    Console.WriteLine("Expression: " + foldL.Body);
    Console.WriteLine("Invocation: " + foldL.Compile().DynamicInvoke());

    Console.WriteLine();
    Console.WriteLine();

    //
    // Right fold in terms of left fold.
    //
    Console.WriteLine("RFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));
    Console.WriteLine("Expression: " + foldR);
    Console.WriteLine("Invocation: " + foldR.Compile().DynamicInvoke(1));

Again, it will print 120 two more times. What's more interesting though is the ToString output of the expression trees:

[img_assist|nid=4568|title=|desc=|link=none|align=none|width=640|height=151]

For the right fold, one can read Invoke(_, args) as the equivalent for _(args). Rewriting the output string based on that makes it a little more "readable":

x => (x => (x => (x => (x => (x => x)(x * 1))(x * 2))(x * 3))(x * 4))(x * 5)

Actually all of the x variables have separate scopes, so we can apply alpha conversion:

a => (b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(a * 5)

Let's do the reduction exercise one more time manually:

   (a => (b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(a * 5))(1)
          (b => (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))(b * 4))(1 * 5)
                (c => (d => (e => (f => f)(e * 1))(d * 2))(c * 3))((1 * 5) * 4)
                      (d => (e => (f => f)(e * 1))(d * 2))(((1 * 5) * 4) * 3)
                            (e => (f => f)(e * 1))((((1 * 5) * 4) * 3) * 2)
                                  (f => f)(((((1 * 5) * 4) * 3) * 2) * 1)
                                        (((((1 * 5) * 4) * 3) * 2) * 1)

An interpretive-based approach to expression tree evaluation

Did I say we were going to do the reduction only one more time by hand? Smells like a promise you say? Yes. Let's make the computer do the work. In Curry for Dummies I provided a primitive method called Curry that can do (partial) function application. We could really have called this method Beta, it simply applies a function to its arguments, which can be done partially or complete. In this case, we want to evaluate our right fold function completely, which we can do by just passing in a single value, the constant expression for 1 in our case. The Curry method will carry out identically the same substitution as the transition between the first and second line above; to go all the way with the substitution we'll have to continue calling the Curry function till we run out of juice, something screaming for a recursion-driven approach. Here's a Curry wrapper that does this job (code for Curry can be found in Curry for Dummies):

static Expression Evaluate(LambdaExpression ex, params Expression[] parameters)
    {
        LambdaExpression l = Curry(ex, parameters);
        Expression res = l;

        if (l.Parameters.Count == 0)
        {
            res = l.Body;
        }

        var invoke = res as InvocationExpression;
        if (invoke != null)
        {
            LambdaExpression l2 = invoke.Expression as LambdaExpression;
            if (l2 != null && l2.Parameters.Count == invoke.Arguments.Count)
            {
                res = Evaluate(l2, invoke.Arguments.ToArray());
            }
        }

        return res;
    }

It basically applies the parameters to the current lambda expression, eliminates the remaining empty "() => Body" to Body and continues by "unwrapping" the embedded InvocationExpression (after all, invocation is just a form that can be reduced through beta conversion, hence the recursion). Finally our code looks like:

int n = 5;

    var foldL = Expression.Lambda<Func<int>>(Enumerable.Range(1, n).AggregateE(Expression.Constant(1), (a, c) => Expression.Multiply(a, Expression.Constant(c))));

    var foldR = Enumerable.Range(1, n).AggregateE(x => x, (f, c) => {
        var x = Expression.Parameter(typeof(int), "x");
        return Expression.Lambda<Func<int,int>>(Expression.Invoke(f, Expression.Multiply(x, Expression.Constant(c))), x);
    });

    //
    // Left fold == Aggregate in LINQ.
    //
    Console.WriteLine("LFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate(1, (a, c) => a * c));
    Console.WriteLine("Expression: " + foldL.Body);
    Console.WriteLine("Invocation: " + foldL.Compile().DynamicInvoke());
    Console.WriteLine("Reduction:  " + Evaluate(foldL));

    Console.WriteLine();
    Console.WriteLine();

    //
    // Right fold in terms of left fold.
    //
    Console.WriteLine("RFOLD");
    Console.WriteLine("-----\n");

    Console.WriteLine("Value:      " + Enumerable.Range(1, n).Aggregate<int,Func<int,int>>(x => x, (f, c) => x => f(x * c))(1));
    Console.WriteLine("Expression: " + foldR);
    Console.WriteLine("Invocation: " + foldR.Compile().DynamicInvoke(1));
    Console.WriteLine("Reduction:  " + Evaluate(foldR));

And yes, it works as expected:

[img_assist|nid=4570|title=|desc=|link=none|align=none|width=640|height=165]

Conclusion

Really just for fun although the left-fold accumulation operator is quite useful in different cases. For samples like factorial, agreed, it's overkill but nevertheless an interesting journey through the wonderful world of functions and their applications. To get our feet back on the ground, our lfold sample really is equivalent to (the generalized case of):

int res = 1;
for (int i = 1; i <= n; i++)
    res *= i;

Have (functional) fun!

Original Author

Original Article Written By Bart De Smet