Flatten IEnumerable<IEnumerable<>>; understanding generics

Question

I wrote this extension method (which compiles):

public static IEnumerable<J> Flatten<T, J>(this IEnumerable<T> @this) 
                                           where T : IEnumerable<J>
{
    foreach (T t in @this)
        foreach (J j in t)
            yield return j;
}

The code below causes a compile time error (no suitable method found), why?:

IEnumerable<IEnumerable<int>> foo = new int[2][];
var bar = foo.Flatten();

If I implement the extension like below, I get no compile time error:

public static IEnumerable<J> Flatten<J>(this IEnumerable<IEnumerable<J>> @this)
{
    foreach (IEnumerable<J> js in @this)
        foreach (J j in js)
            yield return j;
}

Edit(2): This question I consider answered, but it raised another question regarding overload resolution and type constraints. This question I put here: Why aren't type constraints part of the method signature?

Villada

Your edit doesn't work because you have too many surrounding enumerable. foo.Flatten<IEnumerable<int>, int>(); should work. – Permeate

Answer 1

First, you don't need Flatten(); that method already exists, and is called SelectMany(). You can use it like this:

IEnumerable<IEnumerable<int>> foo = new [] { new[] {1, 2}, new[] {3, 4} };
var bar = foo.SelectMany(x => x); // bar is {1, 2, 3, 4}

Second, your first attempt doesn't work because generic type inference works only based on the arguments to the method, not generic constraints associated with the method. Since there is no argument that directly uses the J generic parameter, the type inference engine can't guess what J should be, and thus doesn't think that your method is a candidate.

It's edifying to see how SelectMany() gets around this: it requires an additional Func<TSource, TResult> argument. That allows the type inference engine to determine both generic types, since they are both available based solely on the arguments provided to the method.

Permeate

@Daryl: Because it should be Flatten<IEnumerable<int>,int>(foo) – Indignity

@Villada Generic constraints are not considered part of a method signature; for way more, see this link: blogs.msdn.com/b/ericlippert/archive/2009/12/10/… – Permeate

@Daryl: Don't - there is definitely a learning curve here, this is by far not the easiest aspect of C# to understand. Just trying to master it puts you ahead of 95% of the rest already ;-) – Indignity

I have written something like that Flatten method for various projects in the course of the past years, and I've always called it Flatten as well. Even now that I know it exists, I think that SelectMany is an incredibly misleading choice for the name of that method, as it is quite counterintuitive to assume that something called SelectMany would flatten a hierarchy. +1 for pointing out that it actually does. – Bonn

Answer 2

dlev's answer is fine; I just thought I'd add a little more information.

Specifically, I note that you are attempting to use generics to implement a sort of covariance on IEnumerable<T>. In C# 4 and above, IEnumerable<T> already is covariant.

Your second example illustrates this. If you have

List<List<int>> lists = whatever;
foreach(int x in lists.Flatten()) { ... }

then type inference will reason that List<List<int>> is convertible to IE<List<int>>, List<int> is convertible to IE<int>, and therefore, because of covariance, IE<List<int>> is convertible to IE<IE<int>>. That gives type inference something to go on; it can infer that T is int, and everything is good.

This doesn't work in C# 3. Life is a bit harder in a world without covariance but you can get by with judicious use of the Cast<T> extension method.

Bulter