Recursive LINQ with Y-combinator

I really enjoyed reading Wes Dyers blog post on the Y-combinator. He shows how you can write recursive lambdas in C#. It's pretty straightforward to use his techniques to write recursive LINQ statements which is great because it allows you to decompose the recursion into a series of extension methods. I was particularly inspired with this example, doing directory recursion, from Mauricio Scheffer.

Lets look at an example. Say we have an interface IComposite:

public interface IComposite<T>
{
    T Parent { get; }
    IList<T> Children { get; }
}

And a class that implements that interface, CompositeThing:

public class Thing : IComposite<Thing>
{
    public Thing(string name, Thing parent, bool isActive)
    {
        Name = name;
        Parent = parent;
        IsActive = isActive;
    }
    public string Name { get; private set; }
    public Thing Parent { get; private set; }
    public bool IsActive { get; private set; }
    private readonly IList<Thing> children = new List<Thing>();
    public IList<Thing> Children
    {
        get { return children; }
    }
}

Here's a method that creates a graph of CompositeThing:

private static CompositeThing BuildComposite()
{
    return new CompositeThing
    {
        Name = "Root",
        IsActive = true,
        Children =
            {
                new CompositeThing
                {
                    Name = "First Child",
                    IsActive = true,
                    Children =
                        {
                            new CompositeThing
                            {
                                Name = "First Grandchild",
                                IsActive = true
                            },
                            new CompositeThing
                            {
                                Name = "Second Grandchild",
                                IsActive = true
                            }
                        }
                },
                new CompositeThing
                {
                    Name = "Inactive Child",
                    IsActive = false
                },
                new CompositeThing
                {
                    Name = "Second Child",
                    IsActive = true,
                    Children =
                        {
                            new CompositeThing
                            {
                                Name = "Third Grandchild",
                                IsActive = true
                            }
                        }
                }
            }
    };
}

Now lets write an extension method that takes an IEnumerable<T>, returns the same and uses an HtmlTextWriter to write an unordered list:

public static IEnumerable<T> WriteHtmlLi<T>(this IEnumerable<T> composites, 
    HtmlTextWriter writer)
{
    writer.RenderBeginTag(HtmlTextWriterTag.Ul);
    foreach (var composite in composites)
    {
        writer.RenderBeginTag(HtmlTextWriterTag.Li);
        writer.Write(composite.ToString());
        yield return composite;
        writer.RenderEndTag();
    }
    writer.RenderEndTag();
}

Here's Wes Dyer's Y-combinator:

public class Functional
{
    private delegate Func<A, R> Recursive<A, R>(Recursive<A, R> r);
    public static Func<A, R> Y<A, R>(Func<Func<A, R>, Func<A, R>> f)
    {
        Recursive<A, R> rec = r => a => f(r(r))(a);
        return rec(rec);
    }
}

Now we can write nested lists of our CompositeThings:

 

public void DemonstrateWritingComposite()
{
    var root = BuildComposite();
    var htmlWriter = new HtmlTextWriter(Console.Out);
    var recurse = Functional.Y<CompositeThing, IEnumerable<CompositeThing>>(
        f => item => item.Children.Where(c => c.IsActive).WriteHtmlLi(htmlWriter).SelectMany(f));
    recurse(root).GetEnumerator().MoveNext();
}

It returns this HTML:

<ul>
	<li>First Child<ul>
		<li>First Grandchild<ul>
		</ul></li><li>Second Grandchild<ul>
		</ul></li>
	</ul></li><li>Second Child<ul>
		<li>Third Grandchild<ul>
		</ul></li>
	</ul></li>
</ul>

The great thing is that we can compose the recursion; in this case we're simply inserting a where clause to exclude non active things. The last line where we say recurse(root).GetEnumerator().MoveNext() is simply to trigger the recursion. There are actually zero elements in the resulting enumerable because the bottom of the recursion is reached when when the final SelectMany(f) calls item.Children and no children are returned.