Thursday, March 05, 2009

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.

9 comments:

Anonymous said...

Wow! If I ever followed you on a project where you'd used that, I'd be chasing after you with a big stick! ;) It's a fun excercise, but it doesn't exactly help describe your intent.

Mike Hadlow said...

emq3, Glad you liked it :) It is a fun exercise and it's really just me begining to climb the foothills of functional programming. I'm sure there must be a better way of factoring this.. anyone?

Paul said...

I wrote a series of blog posts that illustrate how the y combinator can be derived in C# by performing many simple refactorings. Perhaps you will find it interesting:

http://www.paulbatum.com/2009/01/refactoring-towards-y-combinator-part-1.html

Mike Hadlow said...

Thanks for that Paul, I haven't had time to read it in detail yet, but looks like a very interesting series.

D. Patrick Caldwell said...

Heh, that's really cool. I agree that it's a fun exercise, but I'm not sure there's a reason for a Y Cobminator in C# though. The language supports recursion natively.

In fact, I think F# also supports recursion natively. There's a recurse or recursive keyword or something like that.

Mike Hadlow said...

Hi Patrick,

Yes, of course you can write recursive functions with C#, the problem is always factoring different parts of the recursive operation. The Y-combinator allows you to write (or use) non recursive functions, such as LINQ extension methods and combine them in a recursive operation.

Anonymous said...

Is it possible to get a enumerable with the elements?

Mike Hadlow said...

Hi Anonymous,

In this example the enumerator has zero elements because the recursion bottoms out when there no children left to recurse. If you look at Mauricio Scheffer's example I mentioned, he recurses on directories but outputs files, so there are items in the enumerator. It just depeneds on what you are trying to do.

Viiktor blog said...

I would like to ask how recursively populate that class (with children), which was used for traversing?