D言語で今始めるRange

#はじめに
この記事は**D言語初心者向け**です。
特殊なテクニック解説というより、レンジの思想を紹介する記事です。

#D言語で今始めるRange

**Range**は複数のデータを格納するデータ型の一つで、いままでなんでもかんでも配列でこなしてきた仕事をより汎用的に扱えるようにしたものです。言語仕様として書いてあるわけではないですが、DMDの標準ライブラリであるphobosもこのアイデアを積極的に取り入れており、事実上のスタンダードと言ってよいと思います。

本稿はD言語を学び始め、初めてRangeという言葉を聞いたというような方の為の解説記事です。

#そうだ、和を求めよう

例えば複数のint型データの和を求める関数を考えてみましょう。(phobosの`std.algorithm`には既に素晴らしい`sum`がありますが・・・)

```d
//とても素直なsum
int sum(int[] arr) {

    int ret;
    for(size_t i; i < arr.length; i ++) {
        sum += arr[i];
    }

    return ret;
}
```

int型データを配列としてパスし、それを添え字を用いて一つずつ丁寧に足していくだけです。

確かにこれは総和をちゃんと計算し、期待した通りの結果を返してくれます。**配列ならば**。
しかし次のような漸化式を考えてみてください：

```math
a_{n+1} = 2 a_n + 1, a_0 = 1
```

これのnが0から9までの項の和を求める・・・などとなると、あのsumに直接渡すことができなくなります。だって配列じゃないし。しかしこれも数の集まりである以上、この漸化式でも和は求められるべきでしょう。

今我々に残された選択肢はたぶん二つです。

- `sum`に渡せるよう漸化式を計算し、配列にしてしまう
- `sum`を配列じゃなくても扱えるようにする

配列を確保し、一旦片っ端から計算結果を保存して足す？いやいや、確かにそれでも結果は出ますが、ここで我々がするのはもちろん後者です。

##漸化式でも和を求めたい！

先程作った`sum`は何がいけなかったのか、それは**添え字でアクセスしようとしていた**ことです。なぜなら、数を全部足し合わせる程度のことをする為に、添え字などという高度な機能は必要ないからです。配列ならその無理な要求にも耐えることができましたが、漸化式だと難しかったわけです。

実際考えてみれば、単に足すだけなら以下のことさえできれば問題ないことが分かります：

- すべての要素を一回ずつ順番に取り出す

4番目の要素の次は2番目、次は9番目・・・というようなトリッキーなアクセス方法は`sum`に必要ありません。ただ単純に一個ずつ順番に渡してくれれば良いのです。

そしてすべての要素を一回ずつ取り出すことは、以下の三つの操作だけでうまく表現できることが知られています。

- **front**     : 先頭の要素を得る操作
- **popFront**  : 先頭の要素を取り除く操作
- **empty**     : 要素がなくなったかの確認

実際に、先ほどの漸化式を構造体として表現してみましょう。[^c]

```d
struct Foo {

    int a = 1;
    int n = 0;

    //先頭の要素を得る(現在の要素を返す)
    @property int front() {
        return a;
    }

    //先頭の要素を取り除く(次の要素に差し替える)
    void popFront() {
        a = 2*a + 1;
        n++;
    }

    //空っぽならtrueを返す
    bool empty() {
        return 9 < n;
    }

}
```

##次は私がRangeを使う番だ。

適切な形のデータは用意できました。
ではsum関数をこのアイデアに対応させましょう。

- **empty**     : 要素が空っぽかどうか確かめて・・・
- **front**     : 先頭を足して・・・
- **popFront**  : (先頭を取り除き)次の要素に変える。

もう引数は配列である必要はありません。[テンプレート][template]でなんでも受け取れるようにしておきましょう。[^a]

```d
int sum(R)(R input) {

    int ret;
    while(!input.empty) {
        ret += input.front;
        input.popFront;
    }

    return ret;
}
```

要素が空かどうか確かめ、空でなければ先頭の要素を足して次に進める。
まさに先程書いたことを、そのままコードにしただけです。[^b]

##スマートなsumの力を体感しよう

では、ここまで100行も読んでもらってやっと完成した`sum`を使ってみます！
よりスマートに書くために、D言語の機能[UFCS][UFCS]をここで使いましょう。(これもD言語の単純でめっちゃクールな機能の一つです！)

```d
import std.stdio;

void main() {
    Foo()           //構造体を作り
        .sum        //足して
        .writeln;   //表示する
}
```

美しい・・・
答えは2036だそうです。

ちなみにこの強化されたsumは、D言語の[プロパティ関数][propertyFunctions]という機能により`import std.range;`または`import std.array;`することで配列でも使うことができます。

```d
import std.stdio;
import std.array;       //配列に対してのempty,front,popFrontが実装されています

void main() {
    [1,2,3,4,5]
        .sum
        .writeln;
}
```

##ついでだしもっと汎用性のあるものを作ろう

先程作った構造体`Foo`をもう少し拡張してみます。

```d
//x = ax + b型の漸化式の表現
struct Bar {

    private:
        int cur;
        int a, b;       //係数

    public:
        this(int x0, int a, int b) {
            this.cur = x0;
            this.a = a;
            this.b = b;
        }

        @property int front() {
            return cur;
        }

        void popFront() {
            cur = a*cur + b;
        }

        //ずっと空にならない・・・つまり、無限個の要素を持ちます。
        enum bool empty = false;

        unittest {
            import std.range : isInputRange;
            static assert(isInputRange!(typeof(this)));
        }

}
```

ここまで作れば、もう十分遊べますね！

```math
a_{n+1} = 2 a_n + 3 , a_0 = 1
```

```d
import std.stdio;

void main() {
    import std.range : take;
    Bar(1, 2, 3)
        .take(10)       //Barは無限個の要素を持っていますが、std.rangeにあるtakeは指定個取り出します。
        .sum
        .writeln;
}
```

#Rangeの仲間たち

今作った、

- `front`
- `popFront`
- `empty`

を持つRangeは、**InputRange**と呼ばれます。
`sum`程度ではこの三つさえあれば十分ですが、例えばランダムに要素を一つ取り出す時は添え字のアクセスが欲しくなるでしょう。

Rangeでは、要求するインターフェイスに応じて、

- **InputRange**
    - **front**
        先頭の要素を得る
    - **popFront**
        先頭の要素を取り除く
    - **empty**
        もう要素が空ならtrueを返す
- **ForwardRange**
    - InputRangeの要件に加え、
    - **save**
        現在の状態を独立に保存できる機能[^d]
- **BidirectionalRange**
    - ForwardRangeの要件に加え、
    - **back**
        末尾の要素を得る
    - **popBack**
        末尾の要素を取り除く
- **RandomAccessRange**
    - ForwardRangeの要件に加え、
    - **opIndex**
        添え字によるアクセス
    - 要素が有限個なら：
        - BidirectionalRangeの要件に加え、
        - **length**
            要素数

と、これらとは性質がやや異なりますが

- **OutputRange**
    - **put**
        Range内に要素を出力する

の5つに分類しています。

例えば配列は、

- 先頭の要素を得ることができ、
- 先頭の要素を取り除くことができ、
- 現在の配列の状態を保存することができ、
- 末尾の要素を得ることができ、
- 末尾の要素を取り除くことができ、
- 添え字によるアクセスができ、
- 要素数を得ることができる

ので、(要素が有限個の)**RandomAccessRange**です。

#レンジをいじろう

話を戻します。先程我々は簡単な漸化式を表すレンジの作成に成功しました。そしてレンジを引数にして総和を求める関数の作成にも成功しました。次はレンジを関数の引数にし、さらに新たなレンジを作るのはどうでしょう？つまり、レンジから新たなレンジを生成する関数を作るのです。
例えば、与えられたレンジから要素をn個飛ばしにしたレンジを返す関数を作りましょう。(またしても`std.range`には似た関数がありますが・・・)

```d
//ある"R"型のレンジを受け取り、Skip型のレンジを作って返す関数
Skip!R skip(R)(R input) {
        return Skip!R(input);
}

struct Skip(R) {
        //...
}

//こんなのをつくりたい...
unittest{
    //equalは二つのレンジの要素がすべて同じか確かめる関数です。
    //(普通、Skip型の構造体とint[]に==は使えません！)
    import std.algorithm : equal;
    //二個飛ばし
    assert([1,2,3,4,5,6,7,8].skip(2).equal([1,4,7]));
    assert([1,2,3,4,5,6,7,8].skip(0).equal([1,2,3,4,5,6,7,8]));
    assert([1,2,3,4,5,6,7,8].skip(100).equal([1]));
}
```

骨組みはこんな感じでいいでしょうか。関数の返り値を見ればわかるように、完全に新しいレンジの作成に挑戦しています。
私の考えたパーフェクトな方針はこうです：

- 関数`skip`にレンジ`input`を渡す
- `skip`は与えられた`input`を使って新たに`Skip`型のレンジを作成し、それを返す
- 関数を呼んだ人は`Skip`を使って遊ぶ(レンジの遊び方は知っているはずです[^f]。)

##レンジからレンジを生成する

`Skip`はあるレンジ`input`を受け取って`front`などを使いつつ、先程のオリジナル漸化式レンジと同じく`front`,`popFront`,...などのインターフェイスを実装します。

```d
Skip!R skip(R)(R input, size_t n) {
        return Skip!R(input, n);
}

struct Skip(R) {
    import std.range;
    private:
        R input;                        //与えられたレンジは記憶しておきます。
        alias E = ElementType!R;        //ElementTypeはレンジの要素型を調べてくれます。
        size_t n;

    public:
        this(R input, size_t n) {
            this.input = input;
            this.n = n;
        }

        @property E front() {
            return input.front;
        }

        void popFront() {
            input.popFront;
            for(size_t i; i < n; i++) {
                if (input.empty) break;
                input.popFront;
            }
        }

        @property bool empty() {
            return input.empty;
        }

}

unittest{
    import std.algorithm : equal;

    assert([1,2,3,4,5,6,7,8].skip(2).equal([1,4,7]));
    assert([1,2,3,4,5,6,7,8].skip(0).equal([1,2,3,4,5,6,7,8]));
    assert([1,2,3,4,5,6,7,8].skip(100).equal([1]));
    assert([1].skip(2).equal([1]));
}
```

レンジinputを受け取り、さらにこのSkip自身もレンジになっています。
確かにunittestも通っていますね！

##もらったレンジは丁重に扱うべし

先程のSkipはどのRangeに分類されるでしょうか？

- `front`
- `popFront`
- `empty`

の三つを持っているのでInputRangeですね。これは、`input`が配列だろうがオリジナル漸化式レンジだろうが変わりません。あの`Skip`にはこの三つしか書かれていないのですから。
しかしそれはフェアでしょうか？前述したように配列はRandomAccessRangeであって、InputRangeよりももっと高級なものであったはずです。それを`skip`一回かますだけでInputRangeに格下げしてしまっていいのでしょうか？Skipは自分がどのようなレンジを受け取ったかを慎重に見極め、それに応じてより高級なインターフェイスも提供すべきです。
ここで、Dの条件コンパイルとRangeの種類を判定してくれるテンプレートを使いましょう。

```d
//std.rangeのisInputRangeは型がInputRangeかどうかを(コンパイル前にわかる範囲で)調べてくれます。
static if (isInputRange!R) {
    //ここに書いたことはRがInputRangeのときだけ実装されます
}
static if (isRandomAccessRange!R) {
    //RandomAccessRangeならもっとできることがあるはずです。
}
```

これを使って、

- `input`がRandomAccessRangeなら`opIndex`を作る
    - 添え字は計算で出せます。
- `input`がBidirectionalRangeで、`length`があるなら`back`,`popBack`を作る
    - 後ろに余りが何個あるか計算できます
- `input`がForwardRangeなら、`save`を作る
    - `input`をちゃんとセーブします。
- `input`が`length`を持つなら、`length`を作る
    - 元の`length`がわかれば計算できます。

以上の四つを行ってみます。

```d
Skip!R skip(R)(R input, size_t n) {
        return Skip!R(input, n);
}

struct Skip(R) {
    import std.range;
    private:
        R input;                        //与えられたレンジは記憶しておきます。
        alias E = ElementType!R;        //ElementTypeはレンジの要素型を調べてくれます。
        size_t n;

    public:
        this(R input, size_t n) {
            this.input = input;
            this.n = n;
            static if (isBidirectionalRange!R && hasLength!R) {
                for(size_t i; i < (input.length - 1) % (n + 1); i++) this.input.popBack;
            }
        }

        @property E front() {
            return input.front;
        }

        void popFront() {
            input.popFront;
            for(size_t i; i < n; i++) {
                if (input.empty) break;
                input.popFront;
            }
        }

        @property bool empty() {
            return input.empty;
        }

    //inputがRandomAccessRangeのとき
    static if (isRandomAccessRange!R) {
        public:
            E opIndex(size_t index) {
                return input[1 + n * index];
            }
    }

    //inputがBidirectionalRangeで、lengthをもっているとき
    static if (isBidirectionalRange!R && hasLength!R) {
        public:
            @property E back() {
                return input.back;
            }

            void popBack() {
                input.popBack;
                for(size_t i; i < n; i++) {
                    if (input.empty) break;
                    input.popBack;
                }
            }
    }

    //inputがForwardRangeのとき
    static if (isForwardRange!R) {
        public:
            @property typeof(this) save() {
                return typeof(this)(input.save, n);
            }
    }

    //inputがlengthをもつとき
    static if (hasLength!R) {
        public:
            @property size_t length() {
                return (input.length + n) / (n + 1);
            }
    }
}

//記事では同じunittestは省略しておきます。

unittest{
    assert([1,2,3,4,5,6,7,8].skip(2).back == 7);
    assert([1,2,3,4,5,6,7,8].skip(3).back == 5);
    assert([1,2,3,4,5,6,7,8].skip(100).back == 1);
}

unittest {
    assert([1].skip(10).length == 1);
    assert([1,2,3,4,5,6,7,8].skip(2).length == 3);
    assert([1,2,3,4,5,6,7,8].skip(0).length == 8);
}
```

これで、`input`の型に応じて`opIndex`などを実装したりしなかったり、柔軟な`Skip`が提供できますね！

##制約

そうだ、忘れるところでした。今`skip`の第一引数の型は`R`と名前を付けたものの、int型だろうがchar[]だろうが謎の構造体Fooだろうが何でも受け付ける状態になっています。（まあ`Skip`のどこかしらでエラーになるでしょう）
しかしやはり、このままおいておくのも気持ち悪いものです。Dには[テンプレート制約][templateConstraints]があります。やり方は簡単なので、ちゃんと`R`はInputRangeのみを受け付けることを宣言しておきましょう。

```d
Skip!R skip(R)(R input, size_t n) if(isInputRange!R) {
        return Skip!R(input, n);
}
```

これで、`R`をInputRangeに合わない型にしようとするとすぐ知らせてくれるようになります。

##お披露目

さっきのオリジナル漸化式レンジ`Bar`と一緒にも使えます！

```d
import std.stdio;
import std.range : take;
void main() {
    Bar(1,-2,2)
        .skip(1)        //1つ飛ばしで
        .take(5)        //5つとって
        .sum            //全部足して
        .writeln;       //表示する
}
```

レンジを受け取ってレンジを返す・・・つまりこんなこともできます。

```d
import std.stdio;
import std.range : take;
void main() {
    Bar(1,-2,2)
        .skip(1)        //1つ飛ばしで
        .skip(2)        //(1つ飛ばしのものをさらに)2つ飛ばしで
        .take(5)        //5つとる
        .sum
        .writeln;
}
```

このようなレンジを受け取ってさらにレンジを生成するような関数を組み合わせれば、応用範囲は一気に広がります。

#さらなる利点

ここまでは、特にレンジの扱いやすさについて書いてきました。しかしレンジにはさらなる利点があります。それは各要素が遅延的に評価されるということです。
例えばさきほど作ったSkipについて考えてみてください。もしあれを配列で実装するとなるとどうなるでしょう？配列をもう一つ余分に作るか、元の配列を破壊してしまうかしなければなりません。前者は無駄に配列を確保することになりますし、後者は当然パラメータとして渡した配列がなくなってしまうデメリットがあります。
しかしSkipレンジは賢く、各要素にアクセスしたそのときに計算が行われます。無駄な配列確保も、元の配列の破壊もありません。[^g]そして、大抵の操作―要素を飛ばしたり、ランダムな位置の要素を得たり、ひっくりかえしたり、全部足したり―は配列である必要はないことが多いです。

#まとめ
配列は非常に多機能なデータです。すべての要素を巡回するのはもちろん、要素数をすぐに答えることも、特定の場所の要素をピックアップすることさえできます。しかしそこまで豊富な機能が要らないとき、配列であることを求めることは過剰に厳しい要求です。Rangeを手に入れた我々はいまや、次くれと言われたときに要素を渡すだけでよく、要素数を教えてほしいと言われたら教えるだけでよく、どうしても添え字を使わせてくれと言われたら使わせてやるだけで良いのです。

#次回予告
次週の**12/14(水)**にも枠を頂いています。
本記事では、Rangeの思想と面白さを伝えることに重点をおいたつもりです。次回は、**iota**, **fold**,**map**,**each**などphobosに用意されているレンジ関係の関数を使って実際にrangeを遊び倒します。

#さらに学びたい人の為のリンク
- [Programming in D - Ranges(英)](http://ddili.org/ders/d.en/ranges.html)
- [Programming in D - More Ranges(英)](http://ddili.org/ders/d.en/ranges_more.html)
    - Rangeについて詳しく書かれています。この項に限らず詳しく解説されている『Programming in D』は良著だと思います！
- [Phobos Runtime Library(英)](http://dlang.org/phobos/index.html)
    - カタログを読む感覚で読むと楽しい
- [プログラミング言語D(日本語訳)](http://www.kmonos.net/alang/d/)
    - **古い**ので注意。雰囲気を感じるために読むとよいと思います。**英公式と併用必須**。

[^a]: 本来ならば、型Rが我々のsumが要求するempty,front,popFrontを持っているかチェックなどすべきで、D言語はその方法ももちろん用意しています！詳しくは後々。
[^b]: もっとテンプレート化してもいいですが、今回はここまでで許してやろう。
[^c]: 構造体でなくとも、クラスでも構いません。
[^d]: この機能については[この記事](http://www.codelogy.org/entry/2012/09/09/140933)が詳しいです。
[^f]: どの種類レンジかだけ確かめ、そのレンジの操作方法さえ知っていれば、Skip型構造体自体ののリファレンスを引く必要はありません。それがレンジという共通概念を作る利点の一つです。
[^g]: どうしても配列の形でほしくなることがあるかもしれません。そのときはstd.arrayにあるarray()にレンジを渡すと配列を作ってくれます。

[ufcs]: http://qiita.com/nak2yoshi/items/1bbd91fb23d7cc67109e
[template]: http://qiita.com/k3_kaimu/items/5b2e0232cb94a42da6ae
[propertyFunctions]: http://dlang.org/spec/function.html#property-functions
[templateConstraints]: https://dlang.org/spec/template.html#template_constraints