KOTET'S
PERSONAL
BLOG

#dlang 無限レンジを作るときはemptyの実装に気をつけなければならない

Created:
#dlang #tech

D言語で無限レンジを作るときに注意しなければならないこと。 ドキュメントをちゃんと読み込んでなかったので長らく気づきませんでした。

無限レンジ

無限レンジとは要素数が無限のレンジです。 例えばこれは1が無限に続くレンジです。

struct One {
    long front(){ return 1; }
    void popFront() {}
    bool empty()
    {
        return false;
    }
}

こんな感じにtakeとかと組み合わせて使います。

import std.range : take;
import std.stdio : writeln;

void main()
{
    One().take(10).writeln(); // [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
}

isInfinite!One == false

しかしここでisInfiniteを使ってみるとfalseになります。

assert(isInfinite!One); // Assertion failure

今まで使ってきたなかでこれで困ったことはありませんが、ライブラリを作るときや、 契約で無限レンジのみを受け取るようにしている関数を使うようなことがあるとマズいです。

enumを使う

emptyが定数falseを返しているので無限レンジとして成り立っているように思えますが、 これはコンパイル時的にはアウトのようです。 この関数が常にfalseを返すのか確かめるすべがありません。

関数ではなくenumを使ってコンパイル時定数にしてやる必要があります。

struct Two {
    long front(){ return 2; }
    void popFront() {}
    enum bool empty = false;
}

これでisInfinitetrueになります。

assert(isInfinite!Two); // Pass

今までずっと関数で書いてたので、自分が書いていたものは何ひとつ”Infinite range”ではなかったということになります。

調べてみたらdlang-tourも11月まで間違えて constしていましたconstが使えなくなったのはDMD 2.067.1からのようです。 ちなみに関数のemptyisInfiniteに認められていた時期は一度もありません。

追記: 重要なのは静的にわかるかどうか

というわけでstatic関数なら大丈夫です。

struct Two {
    long front(){ return 2; }
    void popFront() {}
    static bool empty()
    {
        return false;
    }
}

import std.range : isInfinite;

static assert(isInfinite!Two); // Pass

isInfiniteの中身を見てみればどういうことか理解できます。 というか真っ先に読んでみるべきでしたね……

phobos/primitives.d at v2.086.0 · dlang/phobos

/**
Returns `true` if `R` is an infinite input range. An
infinite input range is an input range that has a statically-defined
enumerated member called `empty` that is always `false`,
for example:
----
struct MyInfiniteRange
{
    enum bool empty = false;
    ...
}
----
 */

template isInfinite(R)
{
    static if (isInputRange!R && __traits(compiles, { enum e = R.empty; }))
        enum bool isInfinite = !R.empty;
    else
        enum bool isInfinite = false;
}

見ての通りisInfiniteは非常にシンプルなテンプレートです。

isInfinitetrueになるのは、インプットレンジRについてenum e = R.empty;がコンパイルできる、 つまりR.emptyにコンパイル時にアクセスできるときで、なおかつR.emptyfalseになるときです。 最初のコードは普通のメンバ関数がインスタンスなしに直接R.emptyを呼び出せないのでfalseになっていたというわけですね。 もちろんstatic関数でもコンパイル時に決まらないような内容だとfalseになります。

単にfalseを返すだけなら行数が増えるだけなので通常はenumを使えばいいと思います。 static関数はテンプレート引数によって無限か有限かが切り替わるようなレンジを作るときに役に立つでしょうか?