debugcppMinor
Fixed point combinator in C++1x
Viewed 0 times
fixedcombinatorpoint
Problem
This has been tested and compiled under Visual Studio 2010. Are there any serious problems with this implementation?
PS. This implementation is fully lambda expression based. If I can make
PS. This implementation is fully lambda expression based. If I can make
fixpoint::fix a real member function it will be simpler than this.//As decltype(variable)::member_name is invalid currently,
//the following template is a workaround.
//Usage: t2t::t::member_name
template
struct t2t
{
typedef T t;
};
template
struct fixpoint
{
typedef std::function func_t;
typedef std::function tfunc_t;
typedef std::function yfunc_t;
class loopfunc_t {
public:
func_t operator()(loopfunc_t v)const {
return func(v);
}
template
loopfunc_t(const L &l):func(l){}
typedef V Parameter_t;
private:
std::function func;
};
static yfunc_t fix;
};
template
typename fixpoint::yfunc_t fixpoint::fix =
[](fixpoint::tfunc_t f) -> fixpoint::func_t {
fixpoint::loopfunc_t l = [f](fixpoint::loopfunc_t x) ->
fixpoint::func_t{
//f cannot be captured since it is not a local variable
//of this scope. We need a new reference to it.
auto &ff = f;
//We need struct t2t because template parameter
//V is not accessable in this level.
return [ff, x](t2t::t::Parameter_t v){
return ff(x(x))(v);
};
};
return l(l);
};
int _tmain(int argc, _TCHAR* argv[])
{
int v = 0;
std::function fac =
fixpoint::fix([](std::function f)
-> std::function{
return [f](int i) -> int{
if(i==0) return 1;
else return i * f(i-1);
};
});
int i = fac(10);
std::cout << i; //3628800
return 0;
}Solution
I hav tried the same thing in G++ (version 4.5 from Ubuntu 11.04 original), and the result is quite impressing me. We now do have a lot more features to generise the solution.
-
we can now support any number of parameters without modifying the code.
-
the t2t class is no longer needed as G++ lambda supports accessing all identifiers in scope, including global things.
I also tried write a free template function to access the internal function. And the result looks good. I just wanted to say: it is elegant!
-
we can now support any number of parameters without modifying the code.
-
the t2t class is no longer needed as G++ lambda supports accessing all identifiers in scope, including global things.
I also tried write a free template function to access the internal function. And the result looks good. I just wanted to say: it is elegant!
#include
#include
template
struct fixpoint
{
typedef std::function func_t;
typedef std::function tfunc_t;
typedef std::function yfunc_t;
class loopfunc_t {
public:
func_t operator()(loopfunc_t v)const {
return func(v);
}
template
loopfunc_t(const L &l):func(l){}
loopfunc_t(){}
private:
std::function func;
};
static func_t Fix(tfunc_t f){
return [](loopfunc_t x){ return x(x); }
([f](loopfunc_t x){ return [f, x](V... v){ return f(x(x))(v...); }; });
}
};
template
struct getfixpoint
{
typedef typename getfixpoint::fp fp;
};
template
struct getfixpoint (T::*)(std::function)>
{
typedef fixpoint fp;
};
template
struct getfixpoint (T::*)(std::function)const>
{
typedef fixpoint fp;
};
template
struct getfixpoint (*)(std::function)>
{
typedef fixpoint fp;
};
template
auto getFix(T f) -> typename getfixpoint::fp::func_t {
return getfixpoint::fp::Fix(f);
};
int main(int argc, char* argv[])
{
auto fac = getFix([](std::function f) -> std::function{
return [f](int n)->int { if(n==0) return 1; else return n * f(n-1); };
});
std::cout<<fac(10)<<std::endl; //3628800
return 0;
}Code Snippets
#include <iostream>
#include <functional>
template<typename R, typename... V>
struct fixpoint
{
typedef std::function<R (V...)> func_t;
typedef std::function<func_t (func_t)> tfunc_t;
typedef std::function<func_t (tfunc_t)> yfunc_t;
class loopfunc_t {
public:
func_t operator()(loopfunc_t v)const {
return func(v);
}
template<typename L>
loopfunc_t(const L &l):func(l){}
loopfunc_t(){}
private:
std::function<func_t (loopfunc_t)> func;
};
static func_t Fix(tfunc_t f){
return [](loopfunc_t x){ return x(x); }
([f](loopfunc_t x){ return [f, x](V... v){ return f(x(x))(v...); }; });
}
};
template<typename T>
struct getfixpoint
{
typedef typename getfixpoint<decltype(&T::operator())>::fp fp;
};
template<typename R, typename T, typename... V>
struct getfixpoint<std::function<R (V...)> (T::*)(std::function<R (V...)>)>
{
typedef fixpoint<R, V...> fp;
};
template<typename R, typename T, typename... V>
struct getfixpoint<std::function<R (V...)> (T::*)(std::function<R (V...)>)const>
{
typedef fixpoint<R, V...> fp;
};
template<typename R, typename... V>
struct getfixpoint<std::function<R (V...)> (*)(std::function<R (V...)>)>
{
typedef fixpoint<R, V...> fp;
};
template<typename T>
auto getFix(T f) -> typename getfixpoint<T>::fp::func_t {
return getfixpoint<T>::fp::Fix(f);
};
int main(int argc, char* argv[])
{
auto fac = getFix([](std::function<int (int)> f) -> std::function<int (int)>{
return [f](int n)->int { if(n==0) return 1; else return n * f(n-1); };
});
std::cout<<fac(10)<<std::endl; //3628800
return 0;
}Context
StackExchange Code Review Q#3111, answer score: 3
Revisions (0)
No revisions yet.