※現在、ブログ記事を移行中のため一部表示が崩れる場合がございます。
順次修正対応にあたっておりますので何卒ご了承いただけますよう、お願い致します。

遅延評価とメモ化は別物(LINQ編)


2011年 10月 15日

問題

以下のC#のコードに含まれる誤りを指摘しなさい:

Send()
{
    var xs = (
        GatherItems()
        .SelectMany(i => i.SubItems)
        .Select(i => i.MakeLocation())
    );

    SendLocations(xs);
}

SendLocations(IEnumerable<Location> ls)
{
    var now = DateTime.Now;

    foreach (var l in ls)
        l.UpdatedAt = now;

    foreach (var l in ls)
        l.Send();
}

解答

上記の SendLocations を実行過程が分かり易くなるよう書き換えると以下のようになります:

SendLocations(IEnumerable<Item> items)
{
    var now = DateTime.Now;

    foreach (var l in items
                      .SelectMany(i => i.SubItems)
                      .Select(i => i.MakeLocation()))
        l.UpdatedAt = now;

    foreach (var l in items
                      .SelectMany(i => i.SubItems)
                      .Select(i => i.MakeLocation()))
        l.Send();
}

このように書き換えると何が問題かは一目瞭然でしょう。
SendLocationsSelect の結果をあたかも普通の配列と同じように扱っているのですが、
実際には新しいデータを作っては捨て、作っては捨て、作っては捨て……ということを繰り返しているのです。
結果として l.UpdatedAt に対する更新が全て無駄になり、誤った結果が l.Send されていいます。

この場合、以下のように Select の結果を実体化し、その結果を使いまわす形に変更すれば、
期待通りに動くようになります:

SendLocations(IEnumerable<Location> ls)
{
    var now = DateTime.Now;
    var _ls = ls.ToArray();

    foreach (var l in _ls)
        l.UpdatedAt = now;

    foreach (var l in _ls)
        l.Send();
}

補足

Select 等の
LINQ の大抵のメソッドは遅延評価です。
より正確には、
メソッドの戻り値(何らかのシーケンスが生成される)が列挙されるまで
実際の処理(Select ならば値の写像)は遅延されます。
逆に言えば、Select 等の戻り値は列挙される度に遅延されている処理が実行されるのです。

つまり、実際の処理が遅延されるだけであって、
結果としてできあがる値のシーケンスがメモ化されることはありません。
遅延評価とメモ化は直交する概念なのですが、
Scheme (R5RS) の delay 等のように
遅延評価とメモ化をセットで取り扱っているライブラリもあるため、
最初にこのようなライブラリに触れていると「遅延評価された結果はメモ化されるものだ」と勘違いされる場合があります
(具体的に言うと筆者のことです)。

遅延評価とメモ化をセットで考えていると今回問題にしたようなコードを書いてしまいがちです。
注意しましょう。

また、解答では Select の結果を実体化するために ToArray を使っていますが、
本当に配列が欲しい訳ではなく、結果が実体化されていれば十分です。
なのに ToArray を使っていると一体何がしたいのかコードをぱっと見て判別できません。
ですので以下のような拡張メソッドを用意しておいた方が良いかも知れません:

public static IEnumerable<T> ToInstance(this IEnumerable<T> xs)
{
    return xs.ToArray();
}