D言語で今始めるRange

はじめに

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

D言語で今始めるRange

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

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

そうだ、和を求めよう

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

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

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

    return ret;
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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 : (先頭を取り除き)次の要素に変える。

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

int sum(R)(R input) {

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

    return ret;
}

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

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

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

import std.stdio;

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

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

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

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

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

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

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

//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)));
        }

}

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

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

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 現在の状態を独立に保存できる機能⁴
• BidirectionalRange
  • ForwardRangeの要件に加え、
  • back 末尾の要素を得る
  • popBack 末尾の要素を取り除く
• RandomAccessRange
  • ForwardRangeの要件に加え、
  • opIndex 添え字によるアクセス
  • 要素が有限個なら：
    • BidirectionalRangeの要件に加え、
    • length 要素数

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

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

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

例えば配列は、

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

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

レンジをいじろう

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

//ある"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を使って遊ぶ(レンジの遊び方は知っているはずです⁵。)

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

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

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の種類を判定してくれるテンプレートを使いましょう。

//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がわかれば計算できます。

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

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にはテンプレート制約があります。やり方は簡単なので、ちゃんとRはInputRangeのみを受け付けることを宣言しておきましょう。

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

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

お披露目

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

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

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

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レンジは賢く、各要素にアクセスしたそのときに計算が行われます。無駄な配列確保も、元の配列の破壊もありません。⁶そして、大抵の操作―要素を飛ばしたり、ランダムな位置の要素を得たり、ひっくりかえしたり、全部足したり―は配列である必要はないことが多いです。

まとめ

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

次回予告

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

さらに学びたい人の為のリンク

• Programming in D - Ranges(英)
• Programming in D - More Ranges(英)
  • Rangeについて詳しく書かれています。この項に限らず詳しく解説されている『Programming in D』は良著だと思います！
• Phobos Runtime Library(英)
  • カタログを読む感覚で読むと楽しい
• プログラミング言語D(日本語訳)
  • 古いので注意。雰囲気を感じるために読むとよいと思います。英公式と併用必須。

---

1. 構造体でなくとも、クラスでも構いません。 ↩

2. 本来ならば、型Rが我々のsumが要求するempty,front,popFrontを持っているかチェックなどすべきで、D言語はその方法ももちろん用意しています！詳しくは後々。 ↩

3. もっとテンプレート化してもいいですが、今回はここまでで許してやろう。 ↩

4. この機能についてはこの記事が詳しいです。 ↩

5. どの種類レンジかだけ確かめ、そのレンジの操作方法さえ知っていれば、Skip型構造体自体ののリファレンスを引く必要はありません。それがレンジという共通概念を作る利点の一つです。 ↩

6. どうしても配列の形でほしくなることがあるかもしれません。そのときはstd.arrayにあるarray()にレンジを渡すと配列を作ってくれます。 ↩