iterator block to LINQ

Question

I'm having a hard time finding the right LINQ syntax to use for the following iterator block:

class Program
{
    class Operation
    {
        public IEnumerable<Operation> NextOperations { get; private set; }
    }
    class Item { }

    static Item GetItem(Operation operation)
    {
        return new Item();
    }

    static IEnumerable<Item> GetItems(IEnumerable<Operation> operations)
    {
        foreach (var operation in operations)
        {
            yield return GetItem(operation);

            foreach (var item in GetItems(operation.NextOperations))  // recursive
                yield return item;
        }
    }

    static void Main(string[] args)
    {
        var operations = new List<Operation>();
        foreach (var item in GetItems(operations))
        {
        }
    }
}

Maybe what I have is as good as it gets? For this particular code, yield return inside an explicit foreach is indeed the right solution?

Answer 1

I think that your implementation is good. However, if you want to use LINQ (and make it a little bit - but not significantly - shorter), then you can implement GetItems using a query that iterates over all operations and returns current item followed by all other recursively generated items:

static IEnumerable<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return from op in operations
           from itm in (new[] { GetItem(op) }).Concat
                       (GetItems(op.NextOperations));
           select itm;
} 

For each operation, we generate a sequence containing the item for the current one followed by all recursively generated items. By using a nested from clause, you can iterate over this collection to get a "flat" structure.

I think you could make it a bit nicer by using a functional (immutable) list which supports operation for "appending an element to the front" - which is exactly what we're doing in the nested from. Using FuncList from my functional programming book (this is no longer lazy sequence though):

static FuncList<Item> GetItems(IEnumerable<Operation> operations) 
{ 
    return (from op in operations
            from itm in FuncList.Cons(GetItem(op), GetItems(op.NextOperations));
            select itm).AsFuncList();
} 

As Jon mentioned, there is no good way of writing the recursive aspect using query (you can write recursive query using lambda functions instead of methods - but that's not much better).

Answer 2

LINQ isn't generally good at recursion, using the standard query operators. You could write a more general purpose form of the above, but you won't find a neat standard LINQ way of doing this traversal.

Answer 3

Maybe what I have is as good as it gets?

It's pretty good. We can make it slightly better.

For this particular code, yield return inside an explicit foreach is indeed the right solution?

It's a reasonable solution. It's easy to read and clearly correct. The down side is, as I mentioned earlier, that the performance is potentially not good if the tree is extremely deep.

Here's how I would do this:

static IEnumerable<T> AllNodes(this T root, Func<T, IEnumerable<T>> getChildren) 
{
    var stack = new Stack<T>();
    stack.Push(root);
    while(stack.Count > 0)
    {
        var current = stack.Pop();
        yield return current;
        foreach(var child in getChildren(current).Reverse())
            stack.Push(child);
    }
} 

static void Main()      
{      
    var operation = whatever;
    var items = from op in operation.AllNodes(x=>x.NextOperations)
                select GetItem(op);
    foreach (var item in items)      
    {      
    }      
} 

Note that the call to Reverse() is necessary only if you care that the iteration go "in order". For example, suppose operation Alpha has child operations Beta, Gamma and Delta, and Delta has children Zeta and Omega. The traversal goes like this:

push Alpha
pop Alpha
yield Alpha
push Delta
push Gamma 
push Beta
pop Beta
yield Beta
pop Gamma
yield Gamma
pop Delta
yield Delta
push Omega
push Zeta
pop Zeta
yield Zeta
pop Omega
yield Omega

and now the stack is empty so we're done, and we get the items in "preorder traversal" order. If you don't care about the order, if all you need is to make sure you get all of them, then don't bother to Reverse the children, and you'll get them in the order Alpha, Delta, Omega, Zeta, Gamma, Beta.

Make sense?