reduce に cannot modify ... with immutable members って怒られる #dlang

登録日は 12/22 ですが、22 == 0x16 なので 12/16 の記事ということにしましょう。

これがコンパイル通らない。

struct M
{
    immutable int value;
}

auto f(M[] xs)
{
    import std.algorithm : reduce;
    return xs.reduce!((x, y) => M(x.value + y.value));
}

phobos\std\algorithm.d(763): Error: cannot modify struct result M with immutable members
phobos\std\algorithm.d(784): Error: template instance reduce.f.reduce!((x, y) => M(x.value + y.value)).reduce!(M, M[]) error instantiating
main.d(9):        instantiated from here: reduce!(M[])
main.d(9): Error: template instance reduce.f.reduce!((x, y) => M(x.value + y.value)).reduce!(M[]) error instantiating

いくつかの手段がありうると思う。以下、簡単のために reduce のパラメータとして関数は1個に限り、seed なし・empty チェックなしの例を示す。

まず、reduce を再帰に直す方法。

auto reduce(alias f, R)(R xs)
{
    if (xs.length == 1)
        return xs[0];
    return f(reduce!f(xs[0..$-1]), xs[$-1]);
}

より range っぽさを残した再帰を行うには reduce の定義を f(x[0], f(x[1], f(x[2], ...))) に変更した方がいいかもしれないが、大した差ではないだろう。

しかし再帰が深くなりすぎて良くない気がする。たとえば f が結合的なものに限れば (この制限はいらない気がしているが、簡単のため残してある)、以下のようにして再帰深度を lg(n) にすることができる。

auto reduce(alias f, R)(R xs)
{
    if (xs.length == 1)
        return xs[0];
    return f(reduce!f(xs[0..$/2]), reduce!f(xs[$/2..$]));
}

状態を保持してループを使い、かつ cannot modify with immutable members が出ないようにするには、例えば動的配列の唯一の要素とすればできるが、気持ち悪い。

auto reduce(alias f, R)(R xs)
{
    auto res = [xs[0]];
    foreach (i, x; xs)
    {
        if (i == 0)
            continue;
        res = [f(res[0], x)];
    }
    return res[0];
}

どうしよう。いずれにせよ Phobos の実装は、f(x[0], x[1]), f(f(x[0], x[1]), x[2]), ... を同じ変数に入れているせいで immutable member modification が起きているので、改善されるべきではないかと思う。