13

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.

VMAtm
  • 27,943
  • 17
  • 79
  • 125
Asik
  • 21,506
  • 6
  • 72
  • 131
  • 1
    Maybe use the Y combinator? That would find the fixed point (i.e. completely flattened list) – Mike Bailey Nov 16 '12 at 01:46
  • 2
    possible duplicate of [Recursive List Flattening](http://stackoverflow.com/questions/141467/recursive-list-flattening) – Cyril Gandon Nov 16 '12 at 02:57
  • 2
    @Scorpi0: Very similar, but not exact duplicates. This question asks for answers in C# or F# (according to the tags) or other .net languages (from the question). The other question was specific to C#. – Joh Nov 16 '12 at 08:22

2 Answers2

18

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

horgh
  • 17,918
  • 22
  • 68
  • 123
7

This is trivial in F# with recursive sequence expressions.

let rec flatten (items: IEnumerable) =
  seq {
    for x in items do
      match x with
      | :? 'T as v -> yield v
      | :? IEnumerable as e -> yield! flatten e
      | _ -> failwithf "Expected IEnumerable or %A" typeof<'T>
  }

A test:

// forces 'T list to obj list
let (!) (l: obj list) = l
let y = ![["1";"2"];"3";[!["4";["5"];["6"]];["7"]];"8"]
let z : string list = flatten y |> Seq.toList
// val z : string list = ["1"; "2"; "3"; "4"; "5"; "6"; "7"; "8"]
Daniel
  • 47,404
  • 11
  • 101
  • 179
  • 1
    I must say I don't understand the casting to 'T trickery... 'T isn't mentioned anywhere but there, and it could be anything, including IEnumerable, no? How is writing 'T here any different from writing obj? – Asik Nov 16 '12 at 06:51
  • @Dr_Asik Daniel's code is wrong in its current shape. If you try to type it, the compiler gives a warning that the second rule will never be matched. – Joh Nov 16 '12 at 08:35
  • @Dr_Asik: `'T` is a type arg and `match x with :? 'T` is a type test (`x is T` in C#). Type args are not required to be explicit in F#, due to type inference. – Daniel Nov 16 '12 at 15:14
  • 2
    @Joh: The function compiles (without warnings) and works perfectly, as my test demonstrates. You can [try it out on ideone](http://ideone.com/OAcXKl). – Daniel Nov 16 '12 at 15:31
  • @Daniel I know what the syntax means, but I don't understand why 'T doesn't include IEnumerable so the second clause can be matched. – Asik Nov 16 '12 at 18:37
  • `'T` is a concrete type at run-time, which may or may not implement `IEnumerable`. If you called it like this (in C#): `flatten` (i.e. `'T` is `string`) then it does `if (x is string) { yield x; } else if (x is IEnumerable) ...`. – Daniel Nov 16 '12 at 19:25
  • @Daniel but if 'T can be an IEnumerable, then 'T includes IEnumerable, and the second branch is redundant, no? – Asik Nov 16 '12 at 21:05
  • The only case in which it would work as you've described is if you passed in `IEnumerable` for `T` (`flatten`). In that case, it wouldn't hit the second branch and therefore would have no effect. – Daniel Nov 16 '12 at 22:55
  • Weird, I tried it at work in VS2010 and it failed. Tried it at home in VS2010 and 2012 and it worked. There is btw another case where the second branch is dead: if 'T is obj. – Joh Nov 17 '12 at 10:27