可変個の集合から、直積の集合を作る

集合の個数が固定ならば、[C#]forever for(のコメント欄)のようにすれば簡単だけど、可変個の場合ちょっとややこしいなぁーとか思いつつググってたら、こんなん見つけた。
id:youkoso_guest:20081212:1229089595
reduceってなんぞ?ってな感じだったので、さらにググってみたらSchemeのfoldじゃあーりませんか。
ってことで、これをC#でやってみた。(っていうか単なる翻訳だけど)

// 直積の集合を列挙
static public IEnumerable<IEnumerable<T>>
EnumerateDirectProduct<T>(IEnumerable<IEnumerable<T>> sets)
{
  return
    sets.Fold(
      (list, prod) =>
        from x in prod
        from y in list
        select x.Concat(Enumerable.Repeat(y, 1)),
      Enumerable.Repeat(Enumerable.Empty<T>(), 1));
}

// reduce的なもの
static public IEnumerable<T>
Fold<T>(this IEnumerable<T> source,
  Func<T, IEnumerable<T>, IEnumerable<T>> proc,
  IEnumerable<T> init)
{
  return
    !source.GetEnumerator().MoveNext() ?
    init :
    source.Skip(1).Fold(proc, proc(source.ElementAt(0), init));
}

LINQはリスト内包表記なんだな。しかし読みにくい...。否!澄んだ心で見れば大丈夫。
Foldもひどい。効率とかいろいろ無視で無理矢理再帰。完全にSchemeに毒されております。イテレータ生成しないとコレクションが空かどうか判断できないのかなぁ。Schemeのnull?に相当することがもっと簡単にできればいいのにな。
で、EnumerateDirectProductを使ってみると

// sets は {{1,2}, {3,4}, {5,6}}
IEnumerable<IEnumerable<int>> sets =
  new List<IEnumerable<int>>
    { Enumerable.Range(1, 2), Enumerable.Range(3, 2), Enumerable.Range(5, 2) };

// result は 
//  {{1,3,5}
//   {1,3,6}
//   {1,4,5}
//   {1,4,6}
//   {2,3,5}
//   {2,3,6}
//   {2,4,5}
//   {2,4,6}}
var result = EnumerateDirectProduct(sets);

型関連でややこしく感じるのは、静的型のせいなのか、自分のスキルが不足なのか。特にFold内のproc。
あと、可変個の集合の要素の静的型は全て同じじゃないとだめ。例えば、上で挙げたブログのように、IEnumerableとIEnumerableとIEnumerableを食わせようとしたら、IEnumerable>として渡さなくちゃいけない。IEnumerable<サブクラス>はIEnumerable<スーパークラス>として見てくれないので、あーもう面倒くさい!