D言語Advent Calendar 2016の11日目の記事です。

D言語erのみなさんが大好きなRangeの中から比較的マイナーと思われるOutputRangeについて最近調べた使い方などの内容をまとめたいと思います。

ただまぁOutputRangeという名前からして抽象的というかコンセプトの話なので、この記事自体はあまり実用的ではないです。（ハードル下げ
利用例や応用に関してはもう1日枠をいただいてるのでもうちょっと待ってください。（ハードル戻す

そして以下色々書いていますが、Programming in D - Ranges(英語)などでちゃんと学ばれている方は斜め読みで良いと思います！

OutputRangeとは？

そもそものRangeの話をすると長くなるので、概要は先日@umariderさんに書いていただいた記事や英語の解説記事に譲りたいと思います。

というわけで、この記事ではざっくり以下のようなニュアンスで進めていきます。

Rangeとは値が並んだ構造を表したもの（類似の概念としてIteratorがある）
Rangeには、大きく分けてInputRangeとOutputRangeの2種類がある
- InputRangeは「値を取り出すもの」
- OutputRangeは「値を入れていくもの」
「取り出す」操作はrange.frontというプロパティの値を使うイメージ
「入れる」操作はrangeにputで値を渡してrangeが何か処理するイメージ

定義

さて、今回はOutputRangeについてちゃんと知るために、まずは定義から見ていきます。
Phobosのstd.rangeには、isOutputRangeというOutputRangeかどうか判定するためのテンプレートがあるので、そのまま拝借してきます。以下の通りです。

isOutputRangeの定義

template isOutputRange(R, E)
{
    enum bool isOutputRange = is(typeof(
    (inout int = 0)
    {
        R r = R.init;
        E e = E.init;
        put(r, e);
    }));
}

使用例

import std.range;

static if (isOutputRange!(OutputRange!int, int)) { }

例の通り、isOutputRange!(R, E)という使い方をすることで、「型Rは、型Eの要素を受け取ることが可能なOutputRangeである」という判定ができます。

色々気になるところはあると思いますが、ここでputの書き方を見て「ん？」となる人は、調べる前の私と同じような状態と思われます。

動作

templateの書き方だけ見るとD言語でよくある書き方なのですが、とりあえずput関数で処理できる型なら何でもいいよ、という感じのゆるふわチェックをする定義だと思ってもらえれば良いです。
※そろそろこのイディオムに名前をつけてほしい…

実はこのさらっと使われている「put関数」が曲者で、結構色々やってくれちゃうすごいやつです。

実装はちょっと見づらいので省きますが、ざっくり言うと「以下の呼び出しを順に試して呼び出せるものを使う」という動作になります。

r.put(e);
r(e);
r.front = e; r.popFront();
r[0 .. e.length] = e[]; r = r[e.length .. $];
r.put([e]);
eがInputRangeでput(r, e.front)できる場合、eの全要素をput(r, e.front)する

具体例

と、putは色々難しいので、とりあえずどんなものがOutputRangeなのか例を挙げます。

unittest
{
    import std.range : isOutputRange;
    
    //関数
    void print(int value) { }

    //関数呼び出しができる構造体、クラスでも同じ
    struct TestCall
    {
        void opCall(int value) { }
    }

    //以下すべてOutputRangeである例
    import std.array : Appender;
    static assert(isOutputRange!(Appender!string, char)); //みんな大好きAppender。putを実装している。

    static assert(isOutputRange!(int[], int)); //普通の配列もOutputRange
    static assert(isOutputRange!(int[], int[]));

    import std.range : iota;
    static assert(isOutputRange!(int[], typeof(iota(10)))); //iotaで生成したInputRangeもputできる

    static assert(isOutputRange!(typeof(&print), int)); //関数も
    static assert(isOutputRange!(void delegate(int), int)); //delegateも
    static assert(isOutputRange!(TestCall, int)); //opCallの関数呼び出しも対応

    static assert(isOutputRange!(void delegate(int), int[])); //1要素受け取れれば配列も受け取れる

    //受け取り側が配列を期待してるところにiotaを渡すのも可
    //実際には[0],[1]と1要素ずつ配列にされる
    //上のルールで言うと、6 -> 5の順で評価されているが、ちょっとやりすぎ感がある…
    static assert(isOutputRange!(void delegate(int[]), typeof(iota(10))));
}

と色々なものがOutputRangeと判定されることがわかりました。

簡単にまとめるとOutputRangeは大きく4種あります。

要素が書き換え可能な配列
1引数で呼び出せる関数、delegateやfunction
1引数で関数呼び出しが可能な構造体やクラス
1引数で呼び出せるputメソッドを実装した構造体やクラス

これにputのルールを考慮すると以下のような特徴が増えてきます。

1要素を受け取るOutputRangeにはInputRangeがputできる
配列を受け取るOutputRangeには配列の要素1つをputできる
配列を受け取るOutputRangeには同様のInputRangeがputできる（ただし少し不思議な動き）

と、ここまでがおおむねOutputRangeの正体になります。

OutputRangeの使い方

OutputRangeはコンセプトであって、要はisOutputRangeの定義通り put(range, value) という使い方を保証するものです。

Phobosでは、ポリモーフィズムのために任意のOutputRangeを共通のinterfaceにラップするoutputRangeObjectという関数がありますが、実際put関数で値を渡すように実装しています。

というわけで先ほどisOutputRangeで判定した色々な型で、実際にputして動きを確認してみます。

配列の場合

何はともあれstd.rangeからputをimportして配列に使ってみます。

unittest
{
    import std.range : put;

    auto array = new int[10]; //10要素入れられるOutputRange

    put(array, 10); //1要素入れる
    put(array, iota(9)); //9要素いれて満タンになるかな？

    assert(array.length == 0); //!!!
}

とまぁこれは個人的にあるあるなハマり方なのですが、putは対象のRangeを参照で受け取り、かつInputRangeの場合に要素数に合わせてr.front=value; r.popFront();するので長さがどんどん減っていきます。

結果元の配列に触れなくなってしまうので、対象が配列ならスライスを処理するのが大体お決まりのパターンになります。

unittest
{
    import std.algorithm, std.range;

    auto array = new int[10];
    auto temp = array[]; //これが大事

    put(temp, 10);
    put(temp, iota(9));

    assert(equal(array, [10, 0, 1, 2, 3, 4, 5, 6, 7, 8]));
}

関数呼び出しの場合

関数やdelegateもOutputRangeでした。関数呼び出し可能なオブジェクトも同様です。
この場合lengthなどの概念がないので「要素を無限に入れられるOutputRange」と解釈できます。(結構重要)

というわけでこれにもputしてみます。

unittest
{
    import std.range : put, iota;
    import std.stdio : write;

    void function(int) op = &write!int; //intで特殊化してintのOutputRangeに
    put(op, iota(10)); //0123456789
}

と、これで0から9までのwriteが流れます。

ちなみにwrite自体はテンプレートなので、そのままputとかはできませんでした。
仮にできてもiotaの結果であるResultを丸ごと受け取れてしまうので面白い表示は期待できないんですけどね。

putを実装したオブジェクトの場合

putを実装しているオブジェクトの場合も今までとまったく同じです。
比較的よく使う標準ライブラリのstd.arrayのAppenderの例ですが、以下のようになります。

unittest
{
    import std.range : put;
    import std.algorithm : equal;
    import std.array : appender;

    auto buf = appender!(int[]);
    put(buf, 1);
    put(buf, [2, 3]);
    put(buf, iota(2));

    assert(equal(buf.data, [1, 2, 3, 0, 1]));
}

さて、Appenderを使ったことがある方は流石に違和感があるでしょうか？

そう。実際のところAppenderはstd.rangeをimportしなくてもputできるんですよね。

unittest
{
    import std.algorithm : equal;
    import std.array : appender;

    auto buf = appender!(int[]);
    buf.put(1);
    buf.put([2, 3]);
    buf.put(iota(2));

    assert(equal(buf.data, [1, 2, 3, 0, 1]));
}

これは見た通りですが、Appenderが最適化のために色々なputを実装しているからできています。
InputRangeをそのまま渡してくれればlengthの有無などからメモリを事前に確保できますし、Appenderからすればそれこそが命題ですしね。

しかしこのstd.rangeをimportしていない例を学習ソースとしてしまった私には、「putを実装しているオブジェクトこそがOutputRangeである」という誤解をして最近まで生きてきました。
Appenderが最強すぎるのが悪い（ほめてる）。そしてみんなちゃんとput関数使って！

put関数に関する教訓

というわけで、put関数を使うのがOutputRangeの基本だぞ、というのが今回定義などを読んで得られた教訓その１です。最初からちゃんと定義を読んでいる人には当たり前なんですけど。

ということで、みなさんぜひput関数でOutputRangeに値を入れていきましょう。

ただまぁ実装読んでちゃんと理解するのは難しく、理解したなーと思えるまで結構かかりました。

実際自分がハマった例や意義を挙げておきます。

正しい使い方とハマりどころ

まず正しく使わないと「isOutputRangeの判定とズレる」という当たり前ですが割と致命的な問題があります。特にAppenderで同じような誤解を持たれていた方や、UFCS大好き人間の方は気を付けてもらいたいです。

たとえば以下のようなコードで、関数のシグネチャ的にはOKなのに中のほうでコンパイルエラー起きる…、とかの結構つらい状況になります。なりました。

import std.range; //isOutputRangeのためにimportしたが、同時にputもimportされている

void putValues(T)(ref T outputRange) if (isOutputRange!(T, int[])) //int配列を渡せるOutputRangeならOK
{
    //putをメンバーアクセス風に呼び出している
    //関数や配列ならUFCSが効くが…
    outputRange.put([0, 1, 2]);
}

struct ElementWisePrinter
{
    void put(int value) //1要素だけ受け取れるOutputRange
    {
        writeln(value);
    }
}

unittest
{
    static assert(isOutputRange!(ElementWisePrinter, int[])); //確かに配列を受け取れるOutputRange

    ElementWisePrinter printer;
    putValues(printer); //しかしコンパイルエラー！
}

配列や関数は問題ないんですが、putを実装した構造体やクラスでは「put関数が見つからない」という旨のエラーになります。

実装しているputと名前被りしてるのがダメポイントかなーと思われ、当初はputじゃなくてpushとかにしてくれればよかったんだけどなーー、などと喚いていましたが、UFCSしない世界も案外悪くない。

とりあえず**「UFCSやメンバー関数の感覚でputを使わない」**というのが教訓その２です。（自分でAppenderなどの実装が分かっていてputするのは別に良いと思います）

import std.range : put, isOutputRange;
void putValues(T)(T outputRange) if (isOutputRange!(T, int[])) //良く分からないけどOutputRangeだ
{
    put(outputRange, [0, 1, 2]); //outputRange.put([0, 1, 2]);は厳禁
}

これもいつか上手くUFCSできると良いですね。

put関数の意義

今まで1つのintしか受け取れないdelegateなどにiotaとかバンバン渡していたことからお察しの通り、OutputRangeに対して一般的な要素の渡し方を提供するのがput関数の意義と考えられます。（ちょっと強すぎるけど）

逆に言うと、put関数を使っていれば、実装に合わせて適切な呼び出しが行われるといったメリットがあります。

どういうことか、例としてAppenderを少しずつ最適化するシナリオを考えてみます。

Appender_v1

import std.range : iota, put, ElementType;
struct Appender(T)
{
    T data;

    void put(ElementType!T value)
    {
        data ~= value; //1要素をひたすら連結するだけ
    }
}
unittest
{
    //実装だけ見てるとこうなんだけど
    Appender!(int[]) buf;
    foreach (i; iota(10))
    {
        buf.put(i);
    }
}
unittest
{
    //OutputRangeということでこうしておこう
    Appender!(int[]) buf;
    put(buf, iota(10)); //複数要素まとめて入れられる
}

（ある日）まとめて追加するときは最適化できそうなのでメソッドを追加します。

Appender_v2

import std.range : iota, ElementType, hasLength;
struct Appender(T)
{
    T data;
    void put(ElementType!T value)
    {
        data ~= value;
    }
    void put(R)(ref R range) if (isInputRange!R && hasLength!R) //最適化したputを追加する
    {
        data.length = data.length + range.length; //アロケーションを1回にして高速化する
        //あとは要素を適切なインデックスに入れる
    }
}
unittest
{
    //こちらは見た通りそのまま動いてるが
    Appender!(int[]) buf;
    foreach (i; iota(10))
    {
        buf.put(i);
    }
}
unittest
{
    Appender!(int[]) buf;
    put(buf, iota(10)); //最適化したputのほうが呼ばれるので勝手に少し早くなる！
}

という感じで、使う側のコードは変わらずに実装だけうまく差し変わるわけです。これは良い感じ。

まとめ

以上まとめると、OutputRangeとは、

要素が書き換え可能な配列
1引数の関数、delegateやfunction
1引数の関数呼び出しが可能な構造体やクラス
1引数のputメソッドを実装している構造体やクラス

などのことを言います。

OutputRangeを使うときは、

まず import std.range : put します。
put(range, value) で値を渡しましょう
range.put(value);はしないように（DMD 2.071.2時点ではUFCSが上手くいかないケースがあるので）

ということになります。

雑感

今回、Appenderによる誤解やらUFCSを期待してメンバーアクセス風に呼び出していたところで色々ハマった内容を記事にしました。
特にputの呼び出しでUFCSを期待するコードは書きがちだと思うので、ぜひぜひ気を付けてもらいたいポイントです。

OutputRangeの概念は抽象度も高く、テンプレート重視のプログラミングをしている方はとても楽しめる概念だと思いますので、みなさんは上記のようなハマりどころを回避しつつ楽しくプログラミングしてもらいたいなーと思います。

あとは15日の枠でも使われどころを記事にしようと思っていますので、そのあたり踏まえて面白いなーと思った方は、色々作っていただいて、公開やフィードバックのほどよろしくお願いします！

以上！