コンパイル時数列生成 generate/unfold/recurrence

Sprout C++ Library
Github https://github.com/bolero-MURAKAMI/Sprout

ご存じのように Sprout には constexpr アルゴリズムがある。
ここでは、そのうち generate と unfold, および recurrence について解説する。
というのも、最近これらについてかなりの破壊的変更が入ったからである。

STL の generate について

さて、STL のアルゴリズムに std::generate というのがある。

namespace std {
    template<typename ForwardIterator, typename Generator>
    void generate(ForwardIterator first, ForwardIterator last, Generator gen);
}

これは、関数オブジェクト gen を次々と呼び出してその返り値をイテレータに格納してゆくものである。

たとえば、このようにして数列などを生成することができる。

- std::generate でフィボナッチ数列を生成

#include <algorithm>
#include <array>
#include <iostream>

template<typename T>
struct fib {
    T a, b;
    constexpr fib() : a(-1), b(1) {}
    constexpr fib(T a, T b) : a(a), b(b) {}
    T operator()() { std::swap(a, b); return b += a; }
};

int main() {
    std::array<int, 30> arr{};
    std::generate(arr.begin(), arr.end(), fib<int>());
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

- std::generate で [1..6] の整数一様分布の乱数列を生成

#include <ctime>
#include <algorithm>
#include <random>
#include <functional>
#include <array>
#include <iostream>

template<typename Rng, typename Dst>
struct rng {
    Rng& r;
    Dst& d;
    constexpr rng(Rng& r, Dst& d) : r(r), d(d) {}
    auto operator()() -> decltype(d(r)) { return d(r); }
};
template<typename Rng, typename Dst>
constexpr rng<Rng, Dst> make_rng(Rng& r, Dst& d) { return {r, d}; }

int main() {
    std::array<int, 30> arr{};
    std::default_random_engine rng(std::time(0));
    std::uniform_int_distribution<int> dst(1, 6);
    std::generate(arr.begin(), arr.end(), make_rng(rng, dst));
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

6 5 1 2 4 2 4 5 4 2 1 3 1 3 4 2 1 1 4 6 4 2 5 2 1 6 3 2 3 5

見て分かるように、前の項の計算結果を利用したり、状態を更新したりする場合は、関数オブジェクト gen の呼出が副作用を持たねばならない。
問題は、そのような仕様では constexpr な処理に置き換えられないことである。

このような数列を生成するようなアルゴリズムを、いかにして constexpr で定義するか。
Sprout C++ Library ではこれに対して３つの回答を用意した。
それが sprout::generate と sprout::unfold, および sprout::recurrence である。

なぜ３つもあるかといえば、どのモデルが一般に最適解であるか見いだせなかったからだ。

なお、この記事中のサンプルコードはすべて g++ (GCC) 4.7.2 -std=gnu++0x でコンパイルしている。

sprout::recurrence

まずは sprout::recurrence について。

template<typename Container, typename Generator, typename... Inits>
constexpr typename sprout::fixed::result_of::algorithm<Container>::type
recurrence(Container const& cont, Generator const& gen, Inits const&... inits);

これは、以下のように使う。

- sprout::recurrence でフィボナッチ数列を生成

#include <sprout/algorithm.hpp>
#include <sprout/array.hpp>
#include <iostream>

template<typename T>
struct rec_fib {
    constexpr T operator()(T a, T b) const { return a + b; }
};

int main() {
    constexpr auto arr = sprout::recurrence(
        sprout::array<int, 30>{},
        rec_fib<int>(), 0, 1
        );
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

ここで gen は、x_n = gen( x_{n-m} .. x_{n-1} ) となるような漸化式である。
rec_fib の場合、x_n = x_{n-2} + x_{n-1} であり、これはフィボナッチ数列の定義と同様である。

inits は初期値であり、gen を呼び出す引数の数は、アルゴリズムに渡した sizeof...(Inits) と同じになる。
なお、inits も結果の列に含まれる。

template<typename T>
struct rec_trib {
    constexpr T operator()(T a, T b, T c) const { return a + b + c; }
};

たとえばこのような関数オブジェクトを用意し、初期値に 0, 0, 1 を与えれば、トリボナッチ数列が得られる。
また operator() を Variadic function にすれば、前項までの任意個の和を計算するフィボナッチ数（の拡張）となるだろう。

このように sprout::recurrence は、フィボナッチ数のようなシンプルな漸化式を素直に表現するのに向いている。

しかし個人的には、これをさほど気に入っていない。
一般のプログラムにおいて、あまり汎用的とは考えにくいからだ。
Sprout の初期の実装においては、もともとこの sprout::recurrence が generate という名前だった。
そういった経緯の事情から、recurrence という名前に変更し、今もライブラリに残してある。

sprout::unfold

次に sprout::unfold について。

template<typename Container, typename Generator, typename Init>
constexpr typename sprout::fixed::result_of::algorithm<Container>::type
unfold(Container const& cont, Generator const& gen, Init const& init);

これは、以下のように使う。

- sprout::unfold でフィボナッチ数列を生成

#include <sprout/algorithm.hpp>
#include <sprout/array.hpp>
#include <sprout/utility.hpp>
#include <iostream>

template<typename T>
struct unf_fib {
    constexpr sprout::pair<T, sprout::pair<T, T>>
    operator()(sprout::pair<T, T> const& x) const
    { return {x.first, {x.second, x.first + x.second}}; }
};

int main() {
    constexpr auto arr = sprout::unfold(
        sprout::array<int, 30>{},
        unf_fib<int>(), sprout::make_pair(0, 1)
        );
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

ここで gen は、ただ一つの引数をとり (現在の値, 次の呼出に与える引数) のペアを返すような関数オブジェクトである。

このようなデザインは、Haskell の unfoldr などに倣ったものである。
ちなみに Haskell の unfoldr は Maybe モナドを返すが、sprout::unfold で同じようなことをやりたい場合は、
無効値をとる型を返す関数オブジェクトと無効値をとる型を格納できるコンテナを用いる必要がある。

なお、この Generator の返値として用いることができるクラスは、デフォルトで pair や tuple などがあるが、
コンセプトを満たすことで独自のクラスを用いることもできる。

1. generated_value(), next_generator() メンバ関数を持つ。
2. generated_value(), next_generator() フリー関数を ADL で呼び出すことができる。
3. get<0>(), get<1>() フリー関数を (sprout::tuples::get を含めた) ADL で呼び出すことができる。

以上を上から順にいずれかを満たすクラスを GeneratorResult コンセプトとしている。

これについてはなかなか汎用的なデザインではないかと思う。
ところで Generator については UnaryFunction が求められ、これは悪くはないのだが、場合によっては別の仕様であるほうがやりやすいこともある。
それについては以下。

sprout::generate

最後に sprout::generate について。

template<typename Container, typename Generator>
constexpr typename sprout::fixed::result_of::algorithm<Container>::type
generate(Container const& cont, Generator const& gen);

これは、以下のように使う。

- sprout::generate でフィボナッチ数列を生成

#include <sprout/algorithm.hpp>
#include <sprout/array.hpp>
#include <sprout/utility.hpp>
#include <iostream>

template<typename T>
struct gen_fib {
    T a, b;
    constexpr gen_fib() : a(0), b(1) {}
    constexpr gen_fib(T a, T b) : a(a), b(b) {}
    constexpr sprout::pair<T, gen_fib> operator()() const { return {a, gen_fib(b, a + b)}; }
};

int main() {
    constexpr auto arr = sprout::generate(
        sprout::array<int, 30>{},
        gen_fib<int>(0, 1)
        );
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229

unfold の場合と異なるのは、ここで gen は引数を取らず (現在の値, 次に呼出すべきジェネレータ) のペアを返すような関数オブジェクトであることだ。
これは std::generate と unfold の合の子のようなデザインである。

Sprout.Random の乱数生成機はこのような Generator のコンセプトを満たすので、sprout::generate と組み合わせて使うことができる。

- sprout::generate で [1..6] の整数一様分布の乱数列を生成

#include <sprout/algorithm.hpp>
#include <sprout/random.hpp>
#include <sprout/array.hpp>
#include <iostream>

int main() {
    constexpr auto arr = sprout::generate(
        sprout::array<int, 30>{},
        sprout::random::combine(
            sprout::default_random_engine(SPROUT_UNIQUE_SEED),
            sprout::uniform_smallint<int>(1, 6)
            )
        );
    for (int e : arr) {
        std::cout << e << ' ';
    }
    std::cout << std::endl;
}

- 出力

3 2 3 1 5 1 2 5 3 3 2 5 5 4 6 1 2 1 1 6 6 3 6 6 2 6 6 1 1 5

まとめ

ともあれ、これで constexpr でコンパイル時に漸化式や乱数の展開を扱うことができる。

ところで、アルゴリズムができれば今度は Range Adaptor を作りたくなるのが人情である。
たとえば上記のような仕様を満たす generated Range Adaptor を作ることなどは簡単だ。

しかし、STL や Boost のように伝統的なイテレータを念頭に置いた Range のモデルでは、いくらか無駄のある実装にならざるを得ないという問題がある。
"Iterators Must Go" などと言われて久しい（参照：「Iterators Must Go」を訳してみた - Faith and Brave - C++で遊ぼう）が、他方、イテレータベースの実装にすれば既存の様々な処理と連携しやすいこともまた事実である。

D言語の Range などは非常に洗練されていると思うが、あれが C++ においてもベストプラクティスとなりうるかは疑問である。
このあたり悩ましいので、何かあればさまざま拝聴したいところだ。