とりあえずYコンビネータではない

そういえば「Yコンビネータ（ググる)」なる単語があったなーとか思い出したので調べてみた。そして書いてみようと思った。しかしf(f)がC++の型システムの上で真っ当な方法で書くことができないので、再帰的な処理を「その処理の中では再帰を使わないで」書けるようにするための関数を考えてみる（とりあえず1引数の関数ポインタ対応で）。
まずはよくある例）

// 1.
int fact(int n) {
    return n ? n * fact(n - 1) : 1;
}

fact(5); // == 120

これは単純な階乗を計算する関数で、fact内部でfactを呼び出している。これをfact内部でfactを直接呼び出さずに書けるようにするのが目的。で、色々な話を端折ってこう変形：

// 2.
int fact(boost::function<int(int)> f, n) {
    return n ? n * f(n - 1) : 1;
}

で、このfの内部でfactが呼ばれるようにする。次にそのfを生成する関数Yを作る。とりあえずオレオレ言語的なもので書いてみる。

// 3.
template<typename R, typename A>
function Y(((A->R), A)->R f)->A->R {
    return function (A a)->R {
        return f(Y(f), a);
    };
}

で、これをC++にしてみると、

// 4.
template<typename R, typename A, typename F>
boost::function<R(A)> Y(R (*f)(F, A)) {
    return boost::bind(f, Y(f), _1);
}

3.の式には存在しないtypename Fがあるのは便宜上で、boost::functionとか書いてもいいと思う。しかしこの関数はY(f)が無限に再帰呼び出しするので使ったらもちろんスタックがボンバーになる。なのでやっつけでこんなものを作った。

// 5.
template<typename R, typename Functor>
struct lazy_higher_order_function {
    Functor f_;
    template<typename A1>
    R operator()(A1 a1) {
        return f_()(a1);
    }
    template<typename A1, typename A2>
    R operator()(A1 a1, A2 a2) {
        return f_()(a1, a2);
    }
    template<typename A1, typename A2, typename A3>
    R operator()(A1 a1, A2 a2, A3 a3) {
        return f_()(a1, a2, a3);
    }
    lazy_higher_order_function(Functor f) : f_(f) {}
};

template<typename R, typename F>
lazy_higher_order_function<R, F> make_lazy_higher_order_function(F f) {
    return lazy_higher_order_function<R, F>(f);
}

operator()の呼び出しでメンバーf_を呼び出した結果を引数に適用するファンクタを定義する。で、これを、

// 6.
template<typename R, typename A, typename F>
boost::function<R(A)> Y(R (*f)(F, A)) {
    typedef boost::function<R(A)> self_type(R (*)(F, A));
    return boost::bind(f, make_lazy_higher_order_function<R>(boost::bind(static_cast<self_type*>(Y), f)), _1);
}

というように使えばできあがり。例えばY(fact)(n)で使う。4.の式ではY内部ですぐY(f)が呼ばれて無限再帰だが、これならf(n - 1)が呼ばれるまでY(f)の呼び出しを遅延することができる。
うん、分かってる。多分読んでもややこしいと思うけど、これを書いてる私は説明しようとすればするほど回りくどくなって余計に読みにくくなるからどうしようかって2日ぐらい悩んだんだ。もう自分でソース追いかけておくれ。
ところで、boostにはanyとかあったなー

追記：lazy_higher_order_function的なものがあるはずだー！と思って探したらあった。
自分で妙なもん作らんでもboost::applyを使ってこう書ける。

template<typename R, typename A, typename F>
boost::function<R(A)> Y(R (*f)(F, A)) {
    typedef boost::function<R(A)> self_type(R (*)(F, A));
    return boost::bind(f, boost::bind(boost::apply<boost::function<int(int)> >(), static_cast<self_type*>(Y), f), _1);
}