How to get list of intermediate sums in a functional way? Using LINQ?

Question

Given a list of objects i need to return a list consisting of the objects and the sum of a property of the objects for all objects in the list seen so far.

More generally given

var input = new int[] {1,2,3}

I would like to have the output of

// does not compile but did not want to include extra classes.
var output = { (1,1), (2,3), (3,6) };

What is the "right" functional way to do this? I can do it in a standard iterative approach of course but I am looking for how this would be done in a functional, lazy way.

Thanks

Answer 1

var output = input.Select((i, indexI) => 
    new {
           Element = i,
           RunningSum = input.Where((j, indexJ) => indexJ <= indexI).Sum()
        });

This will yield a collection of an anonymous type with the two properties Element and RunningSum.

UPDTAE

Here is another solution using just the LINQ Aggregate extension method. And yes, it is ugly.

var output = input.Aggregate(
   new List<KeyValuePair<Int32, Int32>>(),
   (result, element) =>
   {
      result.Add(new KeyValuePair<Int32, Int32>(
         element,
         element + result.LastOrDefault().Value));
      return result;
   });

Answer 2

var input = new int[] {1,2,3}
var output = new List<KeyValuePair<int,int>>();
int runningTotal = 0;

foreach (int current in input)
{
  runningTotal += current;
  output.Add(new KeyValuePair(current, runningTotal);
}

It would be easy to convert this to the Linq .Foreach() function instead if you really want. the problem would be if you don't want a seperate running total.

the functional version :

intput.Foreach(current=>
{
    runningTotal += current;
      output.Add(new KeyValuePair(current, runningTotal);

}
);

Answer 3

    int runningTotal=0;
    var p = input.Select((l)=>
        {
            runningTotal+=l;
            return new {l,Total=runningTotal};
        });

Edit

Foreach will always be in order. Open up reflector and look at ForEach on the List (ForEach doesn't exist on an array) But all ForEach does is a for loop over the elements.

I'm not sure about the select, as far as I know it is but I've never dug into it.

Answer 4

I think this is the shortest approach:

int sum = 0;
var result = input.Select(i => new { i, S = sum += i });

Answer 5

in functional terms this is a combination of :

zip

take two sequences and create a sequence of tuples of the elements

and

map

Take a function f and a sequence and return a new sequence which is f(x) for each x in the original sequence

The zip is trivial in c# 4.0 Taking the simplistic implementation from there we have

static class Enumerable 
{ 
    public static IEnumerable<TResult> Zip<TFirst, TSecond, TResult>(
        this IEnumerable<TFirst> first, 
        IEnumerable<TSecond> second, 
        Func<TFirst, TSecond, TResult> func) 
    { 
        var ie1 = first.GetEnumerator(); 
        var ie2 = second.GetEnumerator();

        while (ie1.MoveNext() && ie2.MoveNext()) 
            yield return func(ie1.Current, ie2.Current); 
    } 
}

We then need the map. We already have it, it's what we call Select in c#

IEnumerable<int> input = { 1,2,3,4 };
int a = 0;
var accumulate = input.Select(x => 
    {
         a += x; 
         return a;
    });

But it is safer to bake this into it's own method (no currying in c#) and allow support for arbitrary types/accumulations.

static class Enumerable 
{ 
    public static IEnumerable<T> SelectAccumulate<T>(
        this IEnumerable<T> seq,
        Func<T,T,T> accumulator) 
    { 
        var e = seq.GetEnumerator(); 
        T t = default(T);             
        while (e.MoveNext()) 
        {
            t = accumulator(t, e.Current);
            yield return t;
        } 
    } 
}

Then we can put them together like so

var input = new int[] {1,2,3};
var mapsum = input.Zip(
    input.SelectAccumulate((x,y) => x+y), 
    (a,b) => new {a,b});

This will iterate over the sequence twice, but is more general. You could choose to do the accumulator yourself within a standard select and a simple closure but it is no longer so useful as a 'building block' which is one of the driving forces behind functional programming.

Tuple support is a pain except within a method as the anonymous types don't traverse method boundaries without quite a bit of hassle. A few basic tuples should be included in c# 4.0. assuming a tuple class/struct called Pair<T,U> you could do:

public static IEnumerable<Pair<T,T>> ZipMapAccumulate<T>(
    this IEnumerable<T> input,
    Func<T,T,T> accumulator)
{
    return input.Zip(
        input.SelectAccumulate((x,y) => accumulator (x,y)), 
        (a,b) => new Pair<T,T>(a,b));
}

//get an int specific one
public static Func<IEnumerable<int>, IEnumerable<Pair<int,int>>> 
    ZipMapSum()
{
    return input => Enumerable.ZipMapAccumulate(
        input, 
        (i,j) => i + j);
}

Where c# linq becomes much more cumbersome than languages like f# is the poor support for operators, currying and tuples unless you keep everything inside one function and 'reconstruct it' each and every time for each type.

Answer 6

Functional implementation (no side effects) and no extensions:

internal struct Tuple<T> {
    public T A;
    public T B;
}

internal class Program {
    private static void Main(string[] args) {
        var ints = new[] { 5, 7, 11, 13 };
        IEnumerable<Tuple<int>> result = ints.Aggregate<int, IEnumerable<Tuple<int>>>(new List<Tuple<int>>(),
                (sum, item) => sum.Concat(new[] { new Tuple<int> { A = sum.LastOrDefault().A + item, B = item } }));

        Console.WriteLine(string.Join(" ", result.Select(item => "(" + item.A + "," + item.B + ")").ToArray()));
    }
}

Though can't figure out how to make it with anonymous type instead of Tuple. Also could be simplified if there would be:

IEnumerable<T> Append(this IEnumerable<T> @this, T item);

Answer 7

Just for fun, here it is in F#, using the built-in Seq.scan function:

> let input = [1;2;3];;

val input : int list

> input |> Seq.scan (fun (_, acc) x -> (x, acc + x)) (0,0) |> Seq.skip 1;;

val it : seq<int * int> = seq [(1, 1); (2, 3); (3, 6)]