Is it possible to implement a recursive "SelectMany"?

Question

As we all know, Enumerable.SelectMany flattens a sequence of sequences into a single sequence. What if we wanted a method that could flatten sequences of sequences of sequences, and so on recursively?

I came up quickly with an implementation using an ICollection<T>, i.e. eagerly evaluated, but I'm still scratching my head as to how to make a lazily-evaluated one, say, using the yield keyword.

static List<T> Flatten<T>(IEnumerable list)  {
    var rv = new List<T>();
    InnerFlatten(list, rv);
    return rv;
}

static void InnerFlatten<T>(IEnumerable list, ICollection<T> acc) {
    foreach (var elem in list) {
        var collection = elem as IEnumerable;
        if (collection != null) {
            InnerFlatten(collection, acc);
        }
        else {
            acc.Add((T)elem);
        }
    }
}

Any ideas? Examples in any .NET language welcome.

Answer 1

As far as I understood your idea, this is my variant:

static IEnumerable<T> Flatten<T>(IEnumerable collection)
{
    foreach (var o in collection)
    {
        if (o is IEnumerable && !(o is T))
        {
            foreach (T t in Flatten<T>((IEnumerable)o))
                yield return t;
        }
        else
            yield return (T)o;
    }
}

and check it

List<object> s = new List<object>
    {
        "1",
        new string[] {"2","3"},
        "4",
        new object[] {new string[] {"5","6"},new string[] {"7","8"},},
    };
var fs = Flatten<string>(s);
foreach (string str in fs)
    Console.WriteLine(str);
Console.ReadLine();

Obviously, it does lack some type validity checks (an InvalidCastExcpetion if collection contains not T, and probably some other drawbacks)...well, at least it's lazy-evaluated, as desired.

!(o is T) was added to prevent flattenning of string to char array