Sum of hierarchical data using LINQ?

Question

Is it possible to sum hierarchical data using .NET's LINQ?

My data class looks like this:

class Node
{
    public decimal Amount;
    public IEnumerable<Node> Children { get; set; }
}

So I would have some data looks like this, but the tree could of course be arbitrarily deep.

var amounts = new Node
{
    Amount = 10;
    Children = new[]
    {
        new Node
        {
            Amount = 20
        },
        new Node
        {
            Amount = 30
        }
    }
};

It is possible sum all the amounts and get the result 60 with one simple LINQ query?

Answer 1

You can do it with a higher order function:

Func<Node, decimal> summer = null;
summer = node => node.Amount + 
                 (node.Children == null ? 0m : node.Children.Sum(summer));
decimal total = summer(amounts);

Note that if you can ensure that node.Children will never be null, summer can be simpler:

summer = node => node.Amount + node.Children.Sum(summer);

Alternatively, you could use the null coalescing operator:

summer = node => node.Amount + 
                 (node.Children ?? Enumerable.Empty<Node>()).Sum(summer);

Of course you could put this into a separate method instead:

static decimal SumNodes(Node node)
{
    return node.Amount + 
        (node.Children ?? Enumerable.Empty<Node>())
            .Sum((Func<Node, decimal>)SumNodes);
}

Note the ugliness here is due to an ambiguity in method group conversions. Method groups don't get much love in type inference.

and then call SumNodes(amount). Lots of options :)

Full example of the first form:

using System;
using System.Collections.Generic;
using System.Linq;

class Node
{
    public decimal Amount;
    public IEnumerable<Node> Children { get; set; }
}

public class Test
{
    static void Main()
    {
        var amounts = new Node {
            Amount = 10, Children = new[] {
                new Node { Amount = 20 },
                new Node { Amount = 30 }
            }
        };

        Func<Node, decimal> summer = null;
        summer = node => node.Amount + 
            (node.Children == null ? 0m : node.Children.Sum(summer));

        decimal total = summer(amounts);

        Console.WriteLine(total);
    }
}

I'm not sure I'd call any of these a "simple" LINQ query, mind you...

Answer 2

Technically you can write recursive lambda expressions, but you need to be insane or insanely bright to try (I haven't figured out which). But you can cheat:

    Func<Node, decimal> nodeSum = null;
    nodeSum = node => {
        decimal result = node.Amount;
        if (node.Children != null) {
            result = result + node.Children.Sum(nodeSum);
        }
        return result;
    };
    var value = nodeSum(amounts);