ycombinator.cpp

#include <iostream>
#include <functional>

template <typename Arg>
struct ArgPack{
    decltype(std::placeholders::_1) noarg = std::placeholders::_1;
};

template <typename ... Args>
inline auto expand() -> decltype(std::placeholders::_1) { return std::placeholders::_1; }

template <typename Lambda, typename Curried>
Curried Ycombinator(Lambda f) {
    return std::bind(f, std::bind(&Ycombinator<Lambda, Curried>,f) , std::placeholders::_1);
}

template <typename Lambda, typename Ret, typename ... Args>
Ret Ycombinator2(Lambda f) {
    return std::bind(f, std::bind(&Ycombinator2<Lambda, Ret>, f), expand<Args>()...);
}

int main() {
    typedef std::function<int(int)> L;
    typedef std::function<int(L, int)> LL;

    std::cout << "Fibonacci 10: " << Ycombinator<LL, L>(
        []( L f, int n ) {
            if(n < 2)
                return 1;
            return f(n-2) + f(n-1);
        })(10) << std::endl;

    typedef std::function<int64_t(int)> Fac;
    typedef std::function<int64_t(Fac,int)> FacY;

    std::cout << "Factorial 10: " << Ycombinator<FacY, Fac>(
        [](Fac f,int n) -> int64_t {
            if(n < 2)
                return 1;
            return n * f(n-1);
        })(10) << std::endl;

    std::cout << "Fibonacci 10: " << Ycombinator2<LL, L, int>(
        [](L f, int n) {
            if(n < 2)
                return 1;
            return f(n-2) + f(n-1);
        })(10) << std::endl;

    return 0;
}