我是c++ 11的新手。我正在写下面的递归lambda函数，但它不能编译。
sum.cpp
#include <iostream>
#include <functional>
auto term = [](int a)->int {
return a*a;
};
auto next = [](int a)->int {
return ++a;
};
auto sum = [term,next,&sum](int a, int b)mutable ->int {
if(a>b)
return 0;
else
return term(a) + sum(next(a),b);
};
int main(){
std::cout<<sum(1,10)<<std::endl;
return 0;
}
编译错误:
vimal@linux-718q：~/Study/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp
sum.cpp:在lambda函数中
sum.cpp:18:36:错误:' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum '不能用作函数
gcc版本
gcc版本4.5.0 20091231(实验性)(gcc)
但如果我改变sum()的声明如下所示，它可以工作:
std::function<int(int,int)> sum = [term,next,&sum](int a, int b)->int {
if(a>b)
return 0;
else
return term(a) + sum(next(a),b);
};
有人能解释一下吗?
你需要一个不动点组合器。看到这个。
或者看看下面的代码:
//As decltype(variable)::member_name is invalid currently,
//the following template is a workaround.
//Usage: t2t<decltype(variable)>::t::member_name
template<typename T>
struct t2t
{
typedef T t;
};
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){}
typedef V Parameter_t;
private:
std::function<func_t (loopfunc_t)> func;
};
static yfunc_t fix;
};
template<typename R, typename V>
typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix =
[](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t {
fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) ->
fixpoint<R, V>::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<decltype(x)>::t::Parameter_t v){
return ff(x(x))(v);
};
};
return l(l);
};
int _tmain(int argc, _TCHAR* argv[])
{
int v = 0;
std::function<int (int)> fac =
fixpoint<int, int>::fix([](std::function<int (int)> f)
-> std::function<int (int)>{
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;
}
在c++ 14中，现在很容易创建一个有效的递归lambda，而不必引起std::function的额外开销，只需几行代码:
template <class F>
struct y_combinator {
F f; // the lambda will be stored here
// a forwarding operator():
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
// we pass ourselves to f, then the arguments.
return f(*this, std::forward<Args>(args)...);
}
};
// helper function that deduces the type of the lambda:
template <class F>
y_combinator<std::decay_t<F>> make_y_combinator(F&& f) {
return {std::forward<F>(f)};
}
你原来的求和尝试变成:
auto sum = make_y_combinator([term,next](auto sum, int a, int b) -> int {
if (a>b) {
return 0;
}
else {
return term(a) + sum(next(a),b);
}
});
在c++ 17中，使用CTAD，我们可以添加演绎指南:
template <class F> y_combinator(F) -> y_combinator<F>;
这样就不需要辅助函数了。我们可以写y_combinator{[](auto self，…){…直接}}。
在c++ 20中，使用CTAD进行聚合，就不需要演绎指南了。
在c++ 23中，通过演绎，你根本不需要y组合子:
auto sum = [term,next](this auto const& sum, int a, int b) -> int {
if (a>b) {
return 0;
}
else {
return term(a) + sum(next(a),b);
}
}
诀窍是将lambda实现作为参数提供给自身，而不是通过捕获。
const auto sum = [term, next](int a, int b) {
auto sum_impl = [term, next](int a, int b, auto& sum_ref) mutable {
if (a > b) {
return 0;
}
return term(a) + sum_ref(next(a), b, sum_ref);
};
return sum_impl(a, b, sum_impl);
};
计算机科学中的所有问题都可以通过另一种间接方式来解决。我第一次发现这个简单的技巧是在http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/
它确实需要c++ 14，而问题是c++ 11，但对大多数人来说可能很有趣。
这是戈德波特大学的完整例子。
使用std::function也是可能的，但会导致代码变慢。但并非总是如此。看看std::function vs template的答案
这不仅仅是c++的特性，
它直接映射到微积分的数学中。从维基百科:
Lambda微积分不能像其他表达式那样直接表示这个
符号:
所有的函数在微积分中都是匿名的，所以我们不能引用a
还没有定义的值，在定义它的lambda项中
相同的值。但是，递归仍然可以通过排列
Lambda表达式接收自身作为参数值
