In lamda calculas, it is extremly difficult. The research on this topic results in the birth of Y-combinator, which is one of the most beatiful operator in mathematics and MIT math department adpot it as its department elblem. Y-combinator can convert a non-recursive version of a function into a recursive one. I was wondering if it is possible to implement Y-combinator in C++. Unfortuately, a real Y-combinator is not possible, because in lamda calculas, the Y combinator cant be recursive either. But, inspired by a post on stack overflow, we can relax this restriction: why can't we simply write a Y combinator in a recursive way in C++. I finally got a solution to it:
The following code must run with C++11 support.
//inspired by & referencing a post on stack overflow
#include <functional>
#include <iostream>
using namespace std;
template<class ArgType, class RetType>
function<RetType(ArgType)> YCombinator(function<RetType(function<RetType(ArgType)>, ArgType)> pseudo_recur_func)
{
return bind(pseudo_recur_func, bind(&YCombinator<ArgType, RetType>, pseudo_recur_func), placeholders::_1);
}
{
//pass a
pseudo-recursive lambda function (in the sense that the 'self' argument is
actually not itself)
//to Y Combinator,
which returns an equivalent real-recusive function of lambda.
auto fibonacci = YCombinator<int, int>(
[](function<int(int)> self , int n){return n <= 1 ? 1 : self(n - 2) + self(n - 1);}//this is the pseudo
recusive lambda
);
//test 0~9
for(int i = 0; i < 10; ++i)
cout<<fibonacci(i)<<ends;
return 0;
}
A "real Y-combinator" is possible. See http://yongweiwu.wordpress.com/2014/12/14/y-combinator-and-cplusplus/.
ReplyDeleteYour code is faster than my code. However, none beats the performance of the new proposal to the C++ committee: http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0200r0.html