是否可能实现递归的“SelectMany”？（这是一个提问标题，无需回答）

Question

众所周知，Enumerable.SelectMany将一个序列的序列平铺成一个单一的序列。那么如果我们想要一个可以递归地将序列的序列的序列进行平铺的方法呢？

我快速想出了一种使用ICollection<T>（即急切求值）的实现方式，但是我仍然不知道如何使用yield关键字来创建一种惰性求值的实现方式。

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);
        }
    }
}

有任何想法吗？欢迎使用任何 .NET 语言的示例。

- Asik

---

也许可以使用 Y 组合子？这将找到固定点（即完全扁平化的列表）。 - Mike Bailey

可能是递归列表展平的重复问题。 - Cyril Gandon

@Scorpi0：非常相似，但不是完全重复的问题。这个问题要求使用C#或F#（根据标签）或其他.NET语言（来自问题）。另一个问题是特定于C#的。 - Joh

Answer 1

据我理解，您的想法是这样的：

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;
    }
}

并检查它

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();

显然，它缺乏一些类型有效性检查（如果集合不包含T，则会出现InvalidCastException和其他一些缺点）...... 好吧，至少它是按需惰性评估的。 添加了 !(o is T) 以防止将字符串展开为字符数组。

- horgh

---

!(o is T)是个很巧妙的发现！ - Benjol

Answer 2

使用递归序列表达式在F#中实现此操作非常简单。

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>
  }

一个测试：

// 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

---

我必须说，我不理解将'T'转换的诡计......除了那里没有提到'T'，它可以是任何东西，包括IEnumerable，对吗？在这里写'T'与写obj有什么不同呢？ - Asik

@Dr_Asik 的代码在当前形式下是错误的。如果您尝试输入它，编译器会发出警告，第二条规则将永远不会匹配。 - Joh

@Dr_Asik: 'T 是一个类型参数，而 match x with :? 'T 则是一个类型测试（在 C# 中表示 x is T）。由于 F# 具有类型推断功能，因此不需要在类型参数上显式指定。 - Daniel

@Joh：该函数编译无误（没有警告），并且完美地工作，正如我的测试所证明的那样。您可以在ideone上尝试它（http://ideone.com/OAcXKl）。 - Daniel

@Daniel 我知道语法的意思，但我不明白为什么 'T 不包括 IEnumerable，所以第二个子句可以匹配。 - Asik