How to compute a running sum of a series of ints in a Linq query?

Question

I am trying to come up with a linq query to convert an IEnumerable<int> to another IEnumerable<int>, where each int in the result is the sum of all the ints up to that position from the initial list:

Given int[] a
I need int[] b
Where b[0] = a[0], b[1] = a[0] + a[1], b[2] = a[0] + a[1] + a[2] and so on

Alternatively, the sums above can be written as b[1] = b[0] + a[1], b[2] = b[1] + a[2] and so on, but I don't see how that would help.

I can, of course, do this with a for loop, but I obtain the a[] sequence from a query and I thought it would look nicer if I continue that query instead of suddenly adding a for there :)

Answer 1

Well, you can do it with side effects easily enough, although it's pretty icky...

int sum = 0;
int[] b = a.Select(x => (sum += x)).ToArray();

It would be nice if the framework provided a sort of "running aggregate" to encapsulate this, but it doesn't as far as I'm aware.

Answer 2

I wrote a function to do this a while ago. It's similar to Haskell's scanl function.

public static IEnumerable<TResult> Scan<T, TResult>(
    this IEnumerable<T> source, 
    Func<T, T, TResult> combine)
{
    using (IEnumerator<T> data = source.GetEnumerator())
        if (data.MoveNext())
        {
            T first = data.Current;

            yield return first;

            while (data.MoveNext())
            {
                first = combine(first, data.Current);
                yield return first;
            }
        }
}

int[] b = a
    .Scan((running, current) => running + current)
    .ToArray();

Answer 3

An alternative to Mr. Skeet's solution: If we drop the requirement for a linq query and more literally address "convert an IEnumerable<int> to another IEnumerable<int>" we can use this:

    static IEnumerable<int> Sum(IEnumerable<int> a)
    {
        int sum = 0;
        foreach (int i in a)
        {
            sum += i;
            yield return sum;
        }
    }

which we can apply to an infinite series:

    foreach (int i in Sum(MyMath.NaturalNumbers))
        Console.WriteLine(i);

This is also useful if you don't want to create the whole array at once.