IanG on Tap

This is part four in a series of blogs:

• Simple but Too Specialized
• Moving Away from Anonymous Types
• LINQ to LINQ
• The Missing LINQ: IEnumerable<T> and Scalars (this entry)
• Other Languages
• Closing Thoughts

Part 4 – The Missing LINQ: IEnumerable<T> and Scalars

Last time, I turned LINQ on itself: I used a LINQ query to build a LINQ query. This worked, but the result wasn’t quite as neat as it could have been. I can improve matters by adding a couple of helpers to the world of LINQ. I’ve often found it slightly odd that these don’t seem to be built into LINQ, but they’re easily added.

LINQ offers no built in clean way to take a single scalar item and convert it into a sequence with that single item in it. The usual approach is just to build a single-element array. This works, but it's rather clunky, and I often run into situations where this curious omission makes code more awkward than it needs to be. It has led to a rather ugly first argument to Aggregate:

        (IEnumerable<IEnumerable<T>>) new T[][] { new T[0] },

What I’m actually saying here is that I want to take an single element—an empty sequence of T (new T[0])—and turn it into a sequence that contains just that one element. (I’m building a sequence of sequences here, remember.) The Enumerable class does actually provide a helper for building an empty sequence, so I can make this code say what it does slightly better by writing this:

(IEnumerable<IEnumerable<T>>) new IEnumerable<T>[] { Enumerable.Empty<T>() },

I think it’s now slightly more obvious that an empty sequence is involved here. But I’ve ended up building an array to get my one-element sequence, and I think it’s ugly. What really I’d like to write is this:

Enumerable.From(Enumerable.Empty<T>()),

I’m imagining a From method here that returns a single-element sequence containing whatever element you pass as the argument. Sadly, this method doesn’t appear to exist. That seems weird to me—we have the Empty<T> method, so it would seem natural also to have a method that wraps a single item as an enumerable. (Moreover, LINQ draws heavily from the concepts behind monadic types such as those offered in Haskell. One of the fundamental operations of a monad is the ability to construct one from any underlying type. There are only two fundamental operations, so this is a particularly striking omission.) It’s easy enough to write our own though:

private static IEnumerable<T> EnumerableFrom<T>(T item)
{
    return new T[] { item };
}

Other implementations are possible of course—this might be a more expressive idiom:

private static IEnumerable<T> EnumerableFrom<T>(T item)
{
    yield return item;
}

That’s prettier, and appeals much more to my language geek tendencies, but it generates a lot more code under the covers. So I’ll stick with the first one.

A similar problem exists with concatenation. On this line here:

select prevProductItem.Concat(new T[] { item }));

I have an IEnumerable<T> (prevProductItem), and a single value of type T (item), and I want to append that to the original enumeration. The Concat operator is only able to combine two enumerations, so I’m obliged to turn that single item into a sequence by wrapping it in an array. This is essentially another instance of the previous problem, so I could just use my new EnumerableFrom method:

select prevProductItem.Concat(EnumerableFrom(item)));

But that feels a bit heavy handed. I’d love it if there were an overload of Concat that accepted singular values, in which case I could write:

select prevProductItem.Concat(item); // Won't compile

Although that might cause ambiguity, so perhaps it’d be better to have a distinct operator for appending just one item:

select prevProductItem.Append(item)); // Won't compile without help

As far as I can tell, that doesn’t exist. (Although it’s always possible that it does exist under a less obvious name, and I’ve simply missed it. Wouldn’t be the first time…) But I can write an extension method to provide it:

static class AppendExtension
{
    public static IEnumerable<T> Append<T>(this IEnumerable<T> that, T item)
    {
        IEnumerable<T> itemAsSequence = new T[] { item };
        return that.Concat(itemAsSequence);
    }
}

With this and my EnumerableFrom helper method in place, I can simplify our CartesianProduct method a little:

public static IEnumerable<IEnumerable<T>> CartesianProduct<T>(
    IEnumerable<IEnumerable<T>> inputs)
{
    return inputs.Aggregate(
        EnumerableFrom(Enumerable.Empty<T>()),
        (soFar, input) =>
            from prevProductItem in soFar
            from item in input
            select prevProductItem.Append(item));
}

That’s looking a lot calmer to me.

I fear it may be write-only code—I’m not convinced that if I were to come across that finished product 6 months after writing it that I’d be able to work out how it works without first referring back to this blog series… However, because I know what an n-ary Cartesian product is, I’ll find it pretty easy to read code that uses this method.

Next time we’ll look at some solutions to this problem in other programming languages, to see how C# compares.

[Update, 5th August 2010: A few people have emailed me to mention that the Reactive Extensions for .NET (Rx) offer the missing features I add. So if these ever make it out of the labs into the full .NET Framework, I'll get my wish. The monad influence is clear - they've given their version of what I called EnumerableFrom the name return (yes, that's a blank web page - there doesn't seem to be much online documentation, and that's the only reference I could find - you'll need to download Rx to see the actual docs). Haskell also calls it return.]