One LINQ operator to rule them all

SelectMany is a fascinating operator in LINQ to Objects. For one thing, it is not as intuitive as most other LINQ operators. MSDN says that SelectMany “projects each element of a sequence to an IEnumerable(T) and flattens the resulting sequences into one sequence.” I still remember reading this description of SelectMany for the first time, and wondering why that would that be useful.

Of course, SelectMany is not only incredibly useful, but also surprisingly powerful. In fact, a variety of LINQ operators are really just constrained versions SelectMany. Select, Concat, Where, Take, Skip, TakeWhile, SkipWhile and Distinct can all be easily rewritten using a single SelectMany.

To get started, let’s compare SelectMany with Select. SelectMany projects each element into some number of elements. In comparison, Select projects each element into exactly one element. Since SelectMany is more general than Select, it can be used to implement Select:

public static IEnumerable<U> Select<T, U>(
    this IEnumerable<T> source,
    Func<T, U> func)
{
    return source.SelectMany(x => Enumerable.Repeat(func(x), 1));
}

But, Select is not the only operator less general SelectMany. Similarly, you can think of the Where operator as producing zero or one element for each element in the sequence. So, Where can also be easily implemented using SelectMany:

public static IEnumerable<T> Where<T>(
    this IEnumerable<T> source,
    Func<T, bool> filter)
{
    return source.SelectMany(x => Enumerable.Repeat(x, filter(x) ? 1 : 0));
}

Another operator that can be easily implemented with SelectMany is Concat:

public static IEnumerable<T> Concat<T>(
    this IEnumerable<T> source1,
    IEnumerable<T> source2)
{
    return new int[] { 0, 1 }
        .SelectMany(
            x => x == 0 ? source1 : source2);
}

Take and Skip can be implemented using the SelectMany variant that passes indices into the user delegate:

public static IEnumerable<T> Take<T>(
    this IEnumerable<T> source,
    int toTake)
{
    return source.SelectMany((x, i) => Enumerable.Repeat(x, i < toTake ? 1 : 0));
}

public static IEnumerable<T> Skip<T>(
    this IEnumerable<T> source,
    int toSkip)
{
    return source.SelectMany((x, i) => Enumerable.Repeat(x, i >= toSkip ? 1 : 0));
}

And finally, with a few closure tricks, we can even implement TakeWhile, SkipWhile and Distinct:

public static IEnumerable<T> TakeWhile<T>(
    this IEnumerable<T> source,
    Func<T, bool> func)
{
    bool stopped = false;
    return source.SelectMany((x, i) => Enumerable.Repeat(x, (!stopped && (stopped = !func(x))) ? 1 : 0));
}

public static IEnumerable<T> SkipWhile<T>(
    this IEnumerable<T> source,
    Func<T, bool> func)
{
    bool started = false;
    return source.SelectMany((x, i) => Enumerable.Repeat(x, (started || (started = func(x))) ? 1 : 0));
}

public static IEnumerable<T> Distinct<T>(
    this IEnumerable<T> source)
{
    var dict = new Dictionary<T, int>();
    return source.SelectMany((x) => {
        if (!dict.ContainsKey(x))
        {
            dict.Add(x, 0);
            return new T[] { x };
        }
        return new T[] { };
    });
}

If you enjoyed this article, check out these LINQ puzzles. Also, read my article on the 7 tricks to simplify your programs with LINQ.

Tags: LINQ