Recursive Linq

I’ve been using Common Table Expressions a lot lately. Particularly when populating SQL Databases with test data. I recommend checking them out if you write slightly more than a modicum of SQL.

Just briefly – if you’re not familiar with CTE’s or their uses – imagine needing to populate a table like this: Months(Id int, MonthNo int, Year int) – with values between say Jan 2000 and Jan 2010. You might do something like this…

    WITH months(id, mnth, yr) 
     AS (SELECT 1, 
         UNION ALL 
         SELECT id + 1, 
                ( mnth % 12 ) + 1, 
                yr + ( mnth / 12 ) 
         FROM   months 
         WHERE  yr < 2010) 
FROM   months 
OPTION(maxrecursion 500)

Now onto the Recursive Linq bit (not to be confused with a Recursive Link.)

Just recently, I was building a Schedule class that required functionality similar to the above SQL. That is, I needed to split some span of time up into N DateTimes based on some function.

While this could be accomplished easily enough with a for or do/while/until loop, after using CTE’s this felt unsatisfying. I knew of Enumerable.Range(n,i) and went searching for some similar ‘recursive’ equivalent.

As it turns out, there is no such beast so I came up with the below.

    public class Linq
        /// <summary>
        /// Builds an <see cref="IEnumerable{T}"/> representing the set of values, 
        /// starting at <paramref name="seed"/>, over the <see cref="Func{T,T}"/>  while <paramref name="@while"/> returns true
        /// </summary>
        /// <typeparam name="T">The type of the <see cref="IEnumerable{T}"/> to build</typeparam>
        /// <param name="seed">The seed value</param>
        /// <param name="recurseUsing">The function used to build the set</param>
        /// <param name="while">A predicate describing the upper bounds of the returned set</param>
        /// <returns>An <see cref="IEnumerable{T}"/> representing the set</returns>
        public static IEnumerable<T> Recurse<T>(T seed, Func<T, T> recurseUsing, Predicate<T> @while)
            var last = seed;
            if (@while(last))

                yield return last;
                while (@while((last = recurseUsing(last))))
                    yield return last;

And it is used thusly.

   var oneToTwenty = Linq.Recurse(1, n => ++n, n => n <= 20); // Same as Enumerable.Range(1,20);

Or in the problem stated above…

  var seed = new DateTime(2000, 1, 1);
  var maxDate = new DateTime(2010, 1, 1);
  var noughtyMonths = Linq.Recurse(seed, d => d.AddMonths(1), d => d.Date < maxDate);

Hope it helps someone, sometime..


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s