C++0x で不動点コンビネータ

Haskell では定義をそのまま書き下すことで不動点コンビネータを定義できるそうですが，

fix :: (a -> a) -> a
fix f = f (fix f)

魔法言語 C++0x も負けてはいないはずです．

template <class F>
struct fix_result
{
    F m_f;

    template <class ...Args>
    auto operator()(Args &&...args) const ->
        decltype(m_f(*std::declval<fix_result const *>(), std::declval<Args>()...))
    {
        return m_f(*this, std::forward<Args>(args)...);
    }
};

template <class F> inline
fix_result<typename std::decay<F>::type> fix(F &&f)
{
    return { std::forward<F>(f) };
}

C++ でカリー化された関数を扱うのは面倒なので，非カリー化された関数を扱うようにしました．つまり

fix :: ((((a1, ..., aN) -> b), a1, ..., aN) -> b) -> (a1, ..., aN) -> b

となります．
ではこれを使って，三角数を無名再帰で求めるコードを書いてみましょう．

int main()
{
    progress_timer t;
    std::cout << fix(
        [](std::function<long long (long long)> f, long long x)
        { 
            return x <= 0 ? 0 : x + f(x - 1);
        }
        )(1000000) << '\n';
    // (1000000 + (999999 + (999998 + ... + (2 + (1 + (0))) ... )))
}

progress_timer http://ideone.com/AvA1s は経過時間を表示するクラスです．
コンパイルして実行してみました．再帰の回数が多いので，スタックサイズを 512 MB に増やしています．

$ g++ -Wall -Wextra -pendatic -std=c++0x -O3 -Wl,--stack=0x20000000 -o triangle_lambda triangle_lambda.cpp

$ ./triangle_lambda
500000500000
0.493 s

さて，上のコードではラムダ式の引数に std::function を使っています．ラムダ式は多相にできないので仕方ないのですが，これはパフォーマンス上のボトルネックになっている可能性があります．試しに，ラムダ式を通常の関数オブジェクトに置き換えてみましょう．

struct T_triabs
{
    template <class F, class X>
    X operator()(F f, X x) const
    {
        return x <= 0 ? 0 : x + f(x - 1);
    }
};

T_triabs const triabs = {};

int main()
{
    progress_timer t;
    std::cout << fix(triabs)(1000000LL) << '\n';
}

$ g++ -Wall -Wextra -pendatic -std=c++0x -O3 -Wl,--stack=0x20000000 -o triangle_function triangle_function.cpp

$ ./triangle_function
500000500000
0.033 s

かなり速くなりました．もっとも，これは無名関数でないので不動点コンビネータを使う意義に乏しく，本末転倒になってしまっています．
このジレンマは，多相なラムダ式さえあれば解決します．C++0x に対応した無名関数ライブラリが待たれるところです．

おまけ

ここに，C++03 での不動点コンビネータの実装があります．
http://stackoverflow.com/questions/152084/fixed-point-combinators-in-c/154267#154267
このコードをベースに，上と同様に無名再帰で三角数を計算するように変形したものがこちらです．

std::function<long long (long long)>
y(std::function<long long (std::function<long long (long long)>, long long)> f)
{
    return std::bind(f, std::bind(&y, f), std::placeholders::_1);
}

int main(int, char **)
{
    progress_timer t;
    auto triangle = y(
        [](std::function<long long (long long)> f, long long v) -> long long
        {
            if (v == 0)
                return 0;
            else
                return v + f(v - 1);
        }
        );
    std::cout << triangle(1000000) << std::endl;
    return 0;
}

$ g++ -Wall -Wextra -pendatic -std=c++0x -O3 -Wl,--stack=0x20000000 -o triangle_bind triangle_bind.cpp

$ ./triangle_bind
500000500000
1.9 s

速くはありません．