図解 SelectMany - NyaRuRuが地球にいたころ

元ネタ『SelectMany - R.Tanaka.Ichiro's Blog』
LINQ のオペレータは絵で描いてみると分かりやすいことがありますね．
私が持っている SelectMany のイメージ．

(上の図，最後の 2 つは f(a[4])[0], f(a[4])[1] が正しいのですが，修正面倒なので読み替えて下さい)
ただ，この絵だと肝心のポイントがきちんと表現できていなくて，本当は入力列も出力列も無限に続く感を出したいんですよね．このイラストでは有限長のリストのみを相手にしているように見えますが，SelectMany はドキュメントに書かれているように遅延実行メソッドです．実際にできあがるのはあくまで読み取り駆動で無限に入出力できるパイプラインであって，このイラストは単にできあがったパイプラインの性質の一端を示すもの，と考えてください．
SelectMany の面白いところは，その柔軟性の高さです．Select も Where も SelectMany で書けますよと．上の図では f(a[3]) のように 1 要素を 1 要素にマップするのが Select，f(a[2]) のように 1 要素を空リストにマップできるのが Where ですもんね．

// Select
var s1 = q.Select( item => item );
var s2 = from tmp in q
         from item in Enumerable.Repeat(tmp, 1)
         select item;
var s3 = q.SelectMany( item => Enumerable.Repeat(item, 1) );

// Where
var w1 = q.Where(item => false);
var w2 = from tmp in q
         from item in Enumerable.Repeat(tmp, 0)
         select item;
var w3 = q.SelectMany( item => Enumerable.Repeat(item, 0) );

さらに SelectMany は，そのどちらでもない，1 要素を複数要素に増やすも可能と．

// Double
var d2 = from tmp in q
         from item in Enumerable.Repeat(tmp, 2)
         select item;
var d3 = q.SelectMany( item => Enumerable.Repeat(item, 2) );

このように，要素の内容を見てシーケンスを伸縮させ，さらに Map した上で Concat するのが SelectMany のイメージです．
まあ慣れないうちは，「これは from x in xs from y in ys(x) で書ける問題かな？」を常に考えてみるだけでも良いでしょう．
SelectMany の使いどころのひとつに，再帰構造を一段ときほぐす，というものがあります．例えば「ディレクトリの列」に「子ディレクトリの列挙関数」を適用した結果を連結すると，再び「ディレクトリの列」に戻りますよね？この手は以前 ToLookup について紹介したときに使いました．

// "Object" の子要素を列挙
lookup["Object"].ForEach(s => Console.WriteLine(s));

// "Object" の孫要素を列挙
lookup["Object"].SelectMany(item => lookup[item])
                .ForEach(s => Console.WriteLine(s));

// "Object" のひ孫素を列挙
lookup["Object"].SelectMany(item => lookup[item])
                .SelectMany(item => lookup[item])
                .ForEach(s => Console.WriteLine(s));

もちろん，多段の from 〜 in で書いても構いません．
別の使用場面としては，一見複雑な周期の構造が，単純なループと部分構造を作る関数の組み合わせに分解できるときでしょうか．例えば

Q = black, white, black, white, black, white, ...

上のシーケンス Q は

Q' = (black, white), (black, white), (black, white), (black, white), ...

上のような同じ要素を繰り返すシーケンス Q' と，

pair => pair[0], pair[1]

という分解関数を組み合わせて作ることができます．前回，菊池さんのコードの書き換えで使ったのはこの手ですね．

using System;
using System.Linq;

using Achiral;
using Achiral.Extension;

static class Program
{
    static void Main(string[] args)
    {
        const byte black = 1;
        const byte white = 2;
        var players = Make.Repeat(new[] { black, white })
                          .SelectMany(pair => pair);

        players.Take(10).ConsoleWriteLine();
    }
}

これも多段の from 〜 in で書けますね．