One of the best new features of .NET 3.5 is LINQ. It's great for accessing data from databases like SQL Server but it's far more useful than just that. LINQ to objects is the killer feature in .NET 3.5 and it can change the way you write code for the better.

I am finding more cases where I can use LINQ for general data manipulation to simplify the code that I write. Coupled with Extension Methods it's a really powerful new way to write algorithms over your data types.

One of my favorite new tricks is to use LINQ to make recursion over a tree of objects simpler. There are many cases where this type of pattern is possible. For instance when working with controls in ASP.NET or Windows Forms each Control has a property named Controls, which is a collection of its child controls. If you need to perform some operation over all of them you can gather them all in just one LINQ statement similar to this:

ChildControls = from nested in 
                myform.Controls.Cast<System.Web.UI.Control>().Descendants(
                    c => c.Controls.Cast<System.Web.UI.Control>())
                select nested;

 The above code is a lot simpler to express than the recursion code that would have been necessary to work with each of the nested controls. And if you need to filter the child controls returned you can just add a LINQ Where clause (or any of the other LINQ operators).

Note: The Cast<T> function above is necessary since the Controls property return a non-generic IEnumerable. Cast<T> simple wraps the non-generic IEnumerable and returns a typed IEnumerable<T>.

The trick that makes this work is a function called Descendants, which is an extension method that I wrote. You can use it with any IEnumerable<T> collection to descend into those collections. It will descend into those collections by way of a Func<T, IEnumerable<T>> lambda that you supply. In the above example I pass it a lambda function that tells it how to retrieve the nested child controls.

Here is that extension method:

static public class LinqExtensions
{
    static public IEnumerable<T> Descendants<T>(this IEnumerable<T> source, 
                                                Func<T, IEnumerable<T>> DescendBy)
    {
        foreach (T value in source)
        {
            yield return value;

            foreach (T child in DescendBy(value).Descendants<T>(DescendBy))
            {
                yield return child;
            }
        }
    }
}

 

You could just as easily write a lambda function to descend into a tree structure or any other data structure as long as it supports implemented IEnumerable<T>. Since you can supply the function you need to descend into the data structures, it makes Descendants a generic way to traverse into nested data structures.


Comments (10) -

Damon Wilder Carr
5/30/2008 8:41:21 AM #

Thank you so much for this. It immediately solved my problem.

I keep waiting for Linq to turn a corner and run out of steam but man it is quite compelling stuff!

I remember I used to urge teams back when delegates came around to think about reusing them and adding them to their libraries, as often the simple things like the 'foreach' custom logic (on say an Array or List<T>) would be used over and over and often it was rather domain specific.

I didn;t know to call it 'Functional Programming', I just knew it made sense. Now that it is SO compelling as an amazing value-add to OO best practices, I am just stoked!

Anyway thanks again.

You can see this in action on:

http://www.domaindotnet.com/

If you view the Framework Browser sample (menu) this is a preview of a project we are getting ready to release.

It provides uttter transparency in the manner of 'Reflector' and ReSharper but across :

1) The web, by treating all code assets, metrics and derivable qualitative and quant items as elements of a data warehouse

2) A DSL for Visual Studio that allows a much higher level of abstraction on the first deliverable: Configuration of IoC/Dependency Injection using a GUI/DSL Model and real-time code involvement, but seamless meta-add to (1) above as well as a plug in model to support the 3-4 major IoC Containers..

Fun!

Thanks,

Damon Wilder Carr, CTO
agilefactor
Senior Editor, .Domain.Dot.Net

René
7/19/2008 3:12:00 AM #

Great stuff! Thanks a lot.

René

xmlspy
8/26/2008 5:17:07 AM #

About mutable.net/.../...q-to-objects-for-recursion.aspx

throws System.NullReferenceException

below is code:
============== User Class ======================
    public class User {
        public User() { }

        public User(string id) {
            Id = id;
        }

        public User(int age) {
            Age = age;
        }

        public User(string id, int age) {
            Id = id;
            Age = age;
        }
        public User(string id, int age,List<User> userList) {
            Id = id;
            Age = age;
            UserList = userList;
        }

        public string Id { set; get; }
        public int Age { set; get; }
        public List<User> UserList { set; get; }

        override public string ToString() {
            string str = String.Empty;

            str = String.Concat(str, "Id = ", Id, "\r\n");
            str = String.Concat(str, "Age = ", Age, "\r\n");
            str = String.Concat(str, "UserList = ", UserList, "\r\n");

            return str;
        }
    }

================ Entry Class==================
  public class MyClass{

        public static void RunSnippet(){
            List<User> users = new List<User>
                               {
                                   new User("jack", 1),
                                   new User("mick", 2),
                                   new User("www", 9),
                                   new User("www2", 2),
                                   new User("www", 5)
                               };

            User[] users2 = {
                                new User("jack", 1,users),
                                new User("mick", 2,users),
                                new User("www", 9,users),
                                new User("www2", 2,users),
                                new User("www", 5,users)
                            };
            if (log.IsDebugEnabled){
                log.Error(users2);
            }

            test.test t = new TestConsole.test.test();

            var results = from user in users
                          group user by user.Id
                          into grp
                              select new {grp.Key, Count = grp.Count()};

            foreach (var r in results){
                Console.WriteLine(r);
            }

            var xx = from u in users2.Descendants(user => user.UserList)
                     select u;
            
            foreach (var user  in xx){
                System.Console.WriteLine(user);
            }

            Console.ReadLine();
        }

        #region Helper methods

        public static void Main(){
            try{
                RunSnippet();
            }
            catch (Exception e){
                string error = string.Format("---\nThe following error occurred while executing the snippet:\n{0}\n---",
                                             e.ToString());
                Console.WriteLine(error);
            }
            finally{
                Console.Write("Press any key to continue...");
                Console.ReadKey();
            }
        }

        private static void WL(object text, params object[] args){
            Console.WriteLine(text.ToString(), args);
        }

        private static void RL(){
            Console.ReadLine();
        }

        private static void Break(){
            System.Diagnostics.Debugger.Break();
        }

        #endregion
    }

martin
4/19/2009 12:06:05 AM #

Hello,

thanks for the greatful code. Your Extension put all Controls in one list. Is there a way, that the hierarchy /struct of the class model wouldnt be destroyed?

Bill Woodruff
12/18/2009 9:03:58 PM #

Excellent ! Thanks so much for this, David.

I'm using it to "harvest" all the Controls on a Form like this :

// input parameter requires a valid Control.ControlCollection object
// returns a List<Control>
// code from David Jade
// mutable.net/.../...q-to-objects-for-recursion.aspx
private List<Control> getControls(Control.ControlCollection rootControls)
{
    var ChildControls =

        from eachControl in
        
            rootControls.Cast<System.Windows.Forms.Control>().Descendants
            (
                c => c.Controls.Cast<System.Windows.Forms.Control>()
            )
            
            select eachControl;

    return ChildControls.ToList<Control>();
}

Colin E.
3/2/2010 5:56:32 AM #

Hi,

Greta article. In answer to martin's question, I have developed a method for applying Linq to tree structures, which maintains the tree structure:

http://www.codeproject.com/KB/linq/LinqToTree.aspx

Colin E.

Tim
3/8/2010 8:10:24 PM #

So this essentially takes hierarchical data and transforms it into a flat list?  Is it also possible to use self-referencing data (each object has an Id, ParentId) and return an anonymous type as a flat list (which it already is) but also return each item's nesting level?

David Jade
3/11/2010 9:28:17 PM #

@Tim

If you take a look at the comment above yours, it references another project on codeproject.com which does something like this.

david

Dave Jellison
5/4/2010 3:34:09 AM #

I did something very similar but a bit more generic I think since it allows traversing any tree by something other than an IEnumerable property.

Check it out and let me know what you think...
www.experts-exchange.com/.../...INQ-Extension.html

Martin Capodici
9/1/2011 11:19:53 AM #

I found this very useful thanks, it went straight into one of my projects.

I have done a bit of Haskell and F# so having something like this seems natural.

Comments are closed

Flux and Mutability

The mutable notebook of David Jade