LINQ の世界: deferred query evaluation と immediate query evaluation

.NET

C# のイテレータの振る舞いを理解したところで，次のコードを見てみましょう．

static IEnumerable<int> Rand()
{
    Trace.WriteLine("Generated");
    Random rand = new Random();
    while (true)
    {
        yield return rand.Next();
    }
}

このイテレータは，見ての通り無限に疑似乱数列を返すというものです．先ほど述べたように，"Generated" と表示されるのは初めて MoveNext() が実行されたときであることに注意しておきましょう．
さて，C# 3.0 LINQ の Take メソッドを使用し，この疑似乱数列から 10 個の要素を取り出してみます．と，ここでクイズです．

static void Main(string[] args)
{
    var seq = Rand().Take(10);
    // Q1: ここで "Generated" と表示されているか？
    var x = seq.First();
    var y = seq.First();
    // Q2: ここで何回 "Generated" と表示されているか？
    // Q3: x == y は成り立つか？
    int i = 0;
    foreach (var val in seq)
    {
        ++i;
    }
    // Q4: i の値はいくら？
}

結果はこうなります．

  1. "Generated" は表示されていない．
  2. "Generated" は 2 回表示されている．
  3. x == y は必ずしも成り立たない
  4. i は 10

LINQ の用語*1で言えば，Rand().Take(10) は deferred query evaluation (遅延クエリ評価) に該当し，First() や foreach などで評価されるたびに「疑似乱数列から 10 回取り出し，それを出力する数列」が新しく生成されています．Q1 で "Generated" が出力されていないのも，First() の結果が一致しないのも，seq が評価されるたびに新しい列 (シーケンス) を返すためです．
deferred query evaluation と対になる形で，即座に値を確定させるクエリは immediate query evaluation と呼ばれています．
結局この手の話になるということは，関数型言語の使用経験がある方ならまあ予想はついていたかと思います．
個人的な意見ですが，enumerate することで deferred query evaluation が起きるような変数は，それをハンガリアン記法で明記しておくのもアリだと思います．


次のコードは，評価するたびに「疑似乱数列から 1000 回取り出し，それを昇順ソートした結果を出力する数列」を返すようなクエリです．

var seq2 = from n in Rand().Take(1000) orderby n select n;

ソートといえば，関数型言語の記述の簡潔さを示すために qsort の実装例がしばしば示されます．IList<T> に対する qsort を LINQ で書いてみました．(変更: List<T> → IList<T>)

using System.Linq;
public static IList<T> qsort<T>(IList<T> list)
    where T : IComparable<T>
{
    if (list.Count < 2)
    {
        return list;
    }
    T pivot = list.First();
    var rest = list.Skip(1);
    var first = from x in rest
                where Comparer<T>.Default.Compare(pivot, x) >= 0 select x;
    var second = from x in rest
                 where Comparer<T>.Default.Compare(pivot, x) < 0 select x;
    return qsort(first.ToList())
        .Concat(Enumerable.Repeat<T>(pivot, 1))
        .Concat(qsort(second.ToList()))
        .ToList();
}
var seq3 = qsort( Rand().Take(10).ToList() );

上のクエリは即時評価が行われ，seq3 には List<int> が入ります．これを遅延クエリ評価の形に書き直すとしたら，例えばこういう感じでしょうか？

public static IEnumerable<T> queryQsort<T>(IEnumerable<T> source)
    where T : IComparable<T>
{
    List<T> list = source.ToList();
    foreach (T t in qsort(list))
    {
        yield return t;
    }
}
var seq4 = queryQsort( Rand().Take(10) );

*1:CTP 付属のヘルプの LINQ Glossary 参照のこと