CODEWITHSUNDEEP
c#linqrecursion
Spook
Spook

Reputation: 25927

How to do a recursive LINQ query?

I have a recursive data structure, such as linked list:

class Node
{
    private Node next;
    private int data;

    // (...)
    public Node Next
    {
        get
        {
            return next;
        }
    }

    public int Data
    {
        get
        {
            return data;
        }
    }
}

I'd like to make a LINQ query, which starts from the head of the list and then goes through the elements, collecting data on the fly. How to do that?

Upvotes: 4

Views: 2480

Answers (3)

Spook
Spook

Reputation: 25927

Mostly probably it is not possible using regular LINQ extensions, but one can use the following extension method:

public static IEnumerable<U> For<T, U>(this T obj, Func<T, U> extract, Func<T, bool> continueCondition, Func<T, T> step)
{
    while (!continueCondition(obj))
    {
        yield return extract(obj);
        obj = step(obj);
    }
}

And from now on, you can write cool queries, like:

head.For(n => n.SomeData, n => n != null, n => n.Next)
    .Select(n => n.Data)
    // More LINQ here

For instance, let's sum up all even numbers from 1 to 20 (in the fancy linq-maniac way)

int sum = 1.For(n => n, n => n <= 20, n => n + 1)
    .Where(n => n % 2 == 0)
    .Aggregate((a, b) => a + b);

Upvotes: 2

Ani
Ani

Reputation: 113402

It's difficult to traverse arbitrary complex data-structures with just simple LINQ queries. At some point, you'll have to 'cut your losses' and write iterator blocks yourself - possibly only for the parts that are hard to express with standard LINQ.

That said, for your linked list example, with moreLinq, you can do:

MoreEnumerable.Generate(head, node => node.Next)
              .TakeWhile(node => node != null)

If you want recursive LINQ tree traversal (or similar), it would be quite different, but here's a sample (depth-first):

private static IEnumerable<Node> GetNodeAndDescendants(Node node)
{
   return new[] { node }.Concat(node.Children.SelectMany(GetNodeAndDescendants));
}

Upvotes: 2

Larry
Larry

Reputation: 18031

Here are two helper classes I us to parse all the nodes in a TreeView control.

You might be inspired by how the yield keyword is used to adapt it for your needs.

internal static IEnumerable<TreeNode> Descendants(this TreeNodeCollection c)
{
    foreach (var node in c.OfType<TreeNode>())
    {
        yield return node;

        foreach (var child in node.Nodes.Descendants())
        {
            yield return child;
        }
    }
}

For example:

var allCheckedNodes = myTreeView.Nodes.Descendants().Where(c => c.Checked);

Upvotes: 3

Related Questions