Recursive List Flattening

Question

I could probably write this myself, but the specific way I'm trying to accomplish it is throwing me off. I'm trying to write a generic extension method similar to the others introduced in .NET 3.5 that will take a nested IEnumerable of IEnumerables (and so on) and flatten it into one IEnumerable. Anyone have any ideas?

Specifically, I'm having trouble with the syntax of the extension method itself so that I can work on a flattening algorithm.

Solution 1

Hmm... I'm not sure exactly what you want here, but here's a "one level" option:

public static IEnumerable<TElement> Flatten<TElement,TSequence> (this IEnumerable<TSequence> sequences)
    where TSequence : IEnumerable<TElement> 
{
    foreach (TSequence sequence in sequences)
    {
        foreach(TElement element in sequence)
        {
            yield return element;
        }
    }
}

If that's not what you want, could you provide the signature of what you do want? If you don't need a generic form, and you just want to do the kind of thing that LINQ to XML constructors do, that's reasonably simple - although the recursive use of iterator blocks is relatively inefficient. Something like:

static IEnumerable Flatten(params object[] objects)
{
    // Can't easily get varargs behaviour with IEnumerable
    return Flatten((IEnumerable) objects);
}

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in candidate)
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

Note that that will treat a string as a sequence of chars, however - you may want to special-case strings to be individual elements instead of flattening them, depending on your use case.

Does that help?

Solution 2

I thought I'd share a complete example with error handling and a single-logic apporoach.

Recursive flattening is as simple as:

LINQ version

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        return !source.Any() ? source :
            source.Concat(
                source
                .SelectMany(i => selector(i).EmptyIfNull())
                .SelectManyRecursive(selector)
            );
    }

    public static IEnumerable<T> EmptyIfNull<T>(this IEnumerable<T> source)
    {
        return source ?? Enumerable.Empty<T>();
    }
}

Non-LINQ version

public static class IEnumerableExtensions
{
    public static IEnumerable<T> SelectManyRecursive<T>(this IEnumerable<T> source, Func<T, IEnumerable<T>> selector)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (selector == null) throw new ArgumentNullException("selector");

        foreach (T item in source)
        {
            yield return item;

            var children = selector(item);
            if (children == null)
                continue;

            foreach (T descendant in children.SelectManyRecursive(selector))
            {
                yield return descendant;
            }
        }
    }
}

Design decisions

I decided to:

• disallow flattening of a null IEnumerable, this can be changed by removing exception throwing and:
  • adding source = source.EmptyIfNull(); before return in the 1st version
  • adding if (source != null) before foreach in the 2nd version
• allow returning of a null collection by the selector - this way I'm removing responsibility from the caller to assure the children list isn't empty, this can be changed by:
  • removing .EmptyIfNull() in the first version - note that SelectMany will fail if null is returned by selector
  • removing if (children == null) continue; in the second version - note that foreach will fail on a null IEnumerable parameter
• allow filtering children with .Where clause on the caller side or within the children selector rather than passing a children filter selector parameter:
  • it won't impact the efficiency because in both versions it is a deferred call
  • it would be mixing another logic with the method and I prefer to keep the logic separated

Sample use

I'm using this extension method in LightSwitch to obtain all controls on the screen:

public static class ScreenObjectExtensions
{
    public static IEnumerable<IContentItemProxy> FindControls(this IScreenObject screen)
    {
        var model = screen.Details.GetModel();

        return model.GetChildItems()
            .SelectManyRecursive(c => c.GetChildItems())
            .OfType<IContentItemDefinition>()
            .Select(c => screen.FindControl(c.Name));
    }
}

Solution 3

Here is a modified Jon Skeet's answer to allow more than "one level":

static IEnumerable Flatten(IEnumerable enumerable)
{
    foreach (object element in enumerable)
    {
        IEnumerable candidate = element as IEnumerable;
        if (candidate != null)
        {
            foreach (object nested in Flatten(candidate))
            {
                yield return nested;
            }
        }
        else
        {
            yield return element;
        }
    }
}

disclaimer: I don't know C#.

The same in Python:

#!/usr/bin/env python

def flatten(iterable):
    for item in iterable:
        if hasattr(item, '__iter__'):
            for nested in flatten(item):
                yield nested
        else:
            yield item

if __name__ == '__main__':
    for item in flatten([1,[2, 3, [[4], 5]], 6, [[[7]]], [8]]):
        print(item, end=" ")

It prints:

1 2 3 4 5 6 7 8 

Solution 4

Isn't that what [SelectMany][1] is for?

enum1.SelectMany(
    a => a.SelectMany(
        b => b.SelectMany(
            c => c.Select(
                d => d.Name
            )
        )
    )
);

Solution 5

Function:

public static class MyExtentions
{
    public static IEnumerable<T> RecursiveSelector<T>(this IEnumerable<T> nodes, Func<T, IEnumerable<T>> selector)
    {
        if(nodes.Any() == false)
        {
            return nodes; 
        }

        var descendants = nodes
                            .SelectMany(selector)
                            .RecursiveSelector(selector);

        return nodes.Concat(descendants);
    } 
}

Usage:

var ar = new[]
{
    new Node
    {
        Name = "1",
        Chilren = new[]
        {
            new Node
            {
                Name = "11",
                Children = new[]
                {
                    new Node
                    {
                        Name = "111",
                        
                    }
                }
            }
        }
    }
};

var flattened = ar.RecursiveSelector(x => x.Children).ToList();

View more solutions