C++11 中的递归 lambda 函数

Recursive lambda functions in C++11

提问by weima

I am new to C++11. I am writing the following recursive lambda function, but it doesn't compile.

我是 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;
}

compilation error:

编译错误：

vimal@linux-718q:~/Study/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp

vimal@linux-718q:~/Study/09C++/c++0x/lambda> g++ -std=c++0x sum.cpp

sum.cpp: In lambda function: sum.cpp:18:36: error: ‘((<lambda(int, int)>*)this)-><lambda(int, int)>::sum' cannot be used as a function

sum.cpp：在 lambda 函数中：sum.cpp:18:36: 错误：“ ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum”不能用作函数

gcc version

海湾合作委员会版本

gcc version 4.5.0 20091231 (experimental) (GCC)

gcc 版本 4.5.0 20091231（实验性）（GCC）

But if I change the declaration of sum()as below, it works:

但是，如果我更改如下声明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);
};

Could someone please throw light on this?

有人可以对此有所了解吗？

回答by I. M. McIntosh

Think about the difference between the autoversion and the fully specified type version. The autokeyword infers its type from whatever it's initialized with, but what you're initializing it with needs to know what its type is (in this case, the lambda closure needs to know the types it's capturing). Something of a chicken-and-egg problem.

想想自动版本和完全指定类型版本之间的区别。该自动关键字推断它的类型无论从那个它与初始化，但你与需要初始化它知道它的类型是什么什么（在这种情况下，拉姆达闭合需要知道它的捕获类型）。有点鸡和蛋的问题。

On the other hand, a fully specified function object's type doesn't need to "know" anything about what is being assigned to it, and so the lambda's closure can likewise be fully informed about the types its capturing.

另一方面，完全指定的函数对象的类型不需要“知道”任何关于分配给它的内容，因此 lambda 的闭包同样可以完全了解其捕获的类型。

Consider this slight modification of your code and it may make more sense:

考虑对您的代码稍作修改，它可能更有意义：

std::function<int(int,int)> sum;
sum = [term,next,&sum](int a, int b)->int {
if(a>b)
    return 0;
else
    return term(a) + sum(next(a),b);
};

Obviously, this wouldn't work with auto. Recursive lambda functions work perfectly well (at least they do in MSVC, where I have experience with them), it's just that they aren't really compatible with type inference.

显然，这不适用于auto。递归 lambda 函数工作得很好（至少它们在 MSVC 中工作，我有使用它们的经验），只是它们与类型推断并不真正兼容。

回答by Johan Lundberg

The trick is to feed in the lambda implementation to itself as a parameter, not by capture.

诀窍是将 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);
};

All problems in computer science can be solved by another level of indirection. I first found this easy trick at http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/

计算机科学中的所有问题都可以通过另一个间接层次来解决。我首先在http://pedromelendez.com/blog/2015/07/16/recursive-lambdas-in-c14/ 上发现了这个简单的技巧

It doesrequire C++14 while the question is on C++11, but perhaps interesting to most.

它确实需要 C++14，而问题是在 C++11 上，但可能对大多数人来说很有趣。

Going via std::functionis also possible but canresult in slower code. But not always. Have a look at the answers to std::function vs template

std::function也可以使用via，但会导致代码变慢。但不总是。看看std::function 与模板的答案

回答by Barry

With C++14, it is now quite easy to make an efficient recursive lambda without having to incur the additional overhead of std::function, in just a few lines of code (with a small edit from the original to prevent the user from taking an accidental copy):

随着C ++ 14，现在是很容易使一个高效的递归拉姆达而不必承担的额外开销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.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*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)};
}

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.
        // [edit: Barry] pass in std::ref(*this) instead of *this
        return f(std::ref(*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)};
}

with which your original sumattempt becomes:

你最初的sum尝试变成了：

auto sum = make_y_combinator([term,next](auto sum, int a, int b) {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
});

---

---

In C++17, with CTAD, we can add a deduction guide:

在 C++17 中，使用 CTAD，我们可以添加一个推导指南：

template <class F> y_combinator(F) -> y_combinator<F>;

Which obviates the need for the helper function. We can just write y_combinator{[](auto self, ...){...}}directly.

这消除了对辅助函数的需要。我们可以直接写y_combinator{[](auto self, ...){...}}。

---

---

In C++20, with CTAD for aggregates, the deduction guide won't be necessary.

在 C++20 中，使用 CTAD 进行聚合，不需要推导指南。

回答by Yankes

I have another solution, but work only with stateless lambdas:

我有另一个解决方案，但仅适用于无状态 lambda：

void f()
{
    static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; };
    std::cout<<self(10);
}

Trick here is that lambdas can access static variables and you can convert stateless ones to function pointer.

这里的技巧是 lambda 可以访问静态变量，您可以将无状态变量转换为函数指针。

You can use it with standard lambdas:

您可以将它与标准 lambda 一起使用：

void g()
{
    int sum;
    auto rec = [&sum](int i) -> int
    {
        static int (*inner)(int&, int) = [](int& _sum, int i)->int 
        {
            _sum += i;
            return i>0 ? inner(_sum, i-1)*i : 1; 
        };
        return inner(sum, i);
    };
}

Its work in GCC 4.7

它在 GCC 4.7 中的工作

回答by Zuza

You canmake a lambda function call itself recursively. The only thing you need to do is to is to reference it through a function wrapper so that the compiler knows it's return and argument type (you can't capture a variable -- the lambda itself -- that hasn't been defined yet).

您可以递归调用 lambda 函数本身。您唯一需要做的就是通过函数包装器引用它，以便编译器知道它的返回值和参数类型（您无法捕获尚未定义的变量——lambda 本身） .

  function<int (int)> f;

  f = [&f](int x) {
    if (x == 0) return 0;
    return x + f(x-1);
  };

  printf("%d\n", f(10));

Be very careful not to run out of the scope of the wrapper f.

非常小心，不要超出包装器 f 的范围。

回答by Tomilov Anatoliy

To make lambda recursive without using external classes and functions (like std::functionor fixed-point combinator) one can use the following construction in C++14 (live example):

要在不使用外部类和函数（如std::function或定点组合器）的情况下使 lambda 递归，可以在 C++14 中使用以下构造（现场示例）：

#include <utility>
#include <list>
#include <memory>
#include <iostream>

int main()
{
    struct tree
    {
        int payload;
        std::list< tree > children = {}; // std::list of incomplete type is allowed
    };
    std::size_t indent = 0;
    // indication of result type here is essential
    const auto print = [&] (const auto & self, const tree & node) -> void
    {
        std::cout << std::string(indent, ' ') << node.payload << '\n';
        ++indent;
        for (const tree & t : node.children) {
            self(self, t);
        }
        --indent;
    };
    print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}});
}

prints:

印刷：

1
 2
  8
 3
  5
   7
  6
 4

Note, result type of lambda should be specified explicitly.

请注意，应明确指定 lambda 的结果类型。

回答by mmocny

I ran a benchmark comparing a recursive function vs a recursive lambda function using the std::function<>capture method. With full optimizations enabled on clang version 4.1, the lambda version ran significantly slower.

我使用std::function<>捕获方法运行了一个比较递归函数与递归 lambda 函数的基准测试。在 clang 版本 4.1 上启用完全优化后，lambda 版本的运行速度明显变慢。

#include <iostream>
#include <functional>
#include <chrono>

uint64_t sum1(int n) {
  return (n <= 1) ? 1 : n + sum1(n - 1);
}

std::function<uint64_t(int)> sum2 = [&] (int n) {
  return (n <= 1) ? 1 : n + sum2(n - 1);
};

auto const ITERATIONS = 10000;
auto const DEPTH = 100000;

template <class Func, class Input>
void benchmark(Func&& func, Input&& input) {
  auto t1 = std::chrono::high_resolution_clock::now();
  for (auto i = 0; i != ITERATIONS; ++i) {
    func(input);
  }
  auto t2 = std::chrono::high_resolution_clock::now();
  auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count();
  std::cout << "Duration: " << duration << std::endl;
}

int main() {
  benchmark(sum1, DEPTH);
  benchmark(sum2, DEPTH);
}

Produces results:

产生结果：

Duration: 0 // regular function
Duration: 4027 // lambda function

(Note: I also confirmed with a version that took the inputs from cin, so as to eliminate compile time evaluation)

（注意：我还确认了一个从 cin 获取输入的版本，以消除编译时评估）

Clang also produces a compiler warning:

Clang 还会产生编译器警告：

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

Which is expected, and safe, but should be noted.

这是预期的，也是安全的，但应该注意。

It's great to have a solution in our toolbelts, but I think the language will need a better way to handle this case if performance is to be comparable to current methods.

很高兴在我们的工具带中有一个解决方案，但我认为如果性能要与当前方法相媲美，该语言将需要一种更好的方法来处理这种情况。

Note:

笔记：

As a commenter pointed out, it seems latest version of VC++ has found a way to optimize this to the point of equal performance. Maybe we don't need a better way to handle this, after all (except for syntactic sugar).

正如评论者指出的那样，似乎最新版本的 VC++ 已经找到了一种方法来优化它以达到同等性能。也许我们不需要更好的方法来处理这个，毕竟（除了语法糖）。

Also, as some other SO posts have outlined in recent weeks, the performance of std::function<>itself may be the cause of slowdown vs calling function directly, at least when the lambda capture is too large to fit into some library-optimized space std::functionuses for small-functors (I guess kinda like the various short string optimizations?).

此外，正如最近几周其他一些 SO 帖子所概述的那样，std::function<>与直接调用函数相比，自身的性能可能是导致速度变慢的原因，至少当 lambda 捕获太大而无法适应std::function小函子的某些库优化空间使用时（我想有点像各种短字符串优化？）。

回答by Mathemagician

Here is a refined version of the Y-combinator solution based on one proposed by @Barry.

这是基于@Barry 提出的解决方案的 Y 组合器解决方案的改进版本。

template <class F>
struct recursive {
  F f;
  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  const { return f(std::ref(*this), std::forward<Ts>(ts)...); }

  template <class... Ts>
  decltype(auto) operator()(Ts&&... ts)  { return f(std::ref(*this), std::forward<Ts>(ts)...); }
};

template <class F> recursive(F) -> recursive<F>;
auto const rec = [](auto f){ return recursive{std::move(f)}; };

To use this, one could do the following

要使用它，可以执行以下操作

auto fib = rec([&](auto&& fib, int i) {
// implementation detail omitted.
});

It is similar to the let reckeyword in OCaml, although not the same.

它类似于let recOCaml 中的关键字，虽然不一样。

回答by Pseudonym

This is a slightly simpler implementation of the fixpoint operator which makes it a little more obvious exactly what's going on.

这是固定点运算符的一个稍微简单的实现，这使得它到底发生了什么更加明显。

#include <iostream>
#include <functional>

using namespace std;

template<typename T, typename... Args>
struct fixpoint
{
    typedef function<T(Args...)> effective_type;
    typedef function<T(const effective_type&, Args...)> function_type;

    function_type f_nonr;

    T operator()(Args... args) const
    {
        return f_nonr(*this, args...);
    }

    fixpoint(const function_type& p_f)
        : f_nonr(p_f)
    {
    }
};


int main()
{
    auto fib_nonr = [](const function<int(int)>& f, int n) -> int
    {
        return n < 2 ? n : f(n-1) + f(n-2);
    };

    auto fib = fixpoint<int,int>(fib_nonr);

    for (int i = 0; i < 6; ++i)
    {
        cout << fib(i) << '\n';
    }
}

回答by Jonas Brandel

C++ 14: Here is a recursive anonymous stateless/no capture generic set of lambdas that outputs all numbers from 1, 20

C++ 14：这是一个递归匿名无状态/无捕获通用 lambda 集，它输出 1、20 中的所有数字

([](auto f, auto n, auto m) {
    f(f, n, m);
})(
    [](auto f, auto n, auto m) -> void
{
    cout << typeid(n).name() << el;
    cout << n << el;
    if (n<m)
        f(f, ++n, m);
},
    1, 20);

If I understand correctly this is using the Y-combinator solution

如果我理解正确，这是使用 Y 组合器解决方案

And here is the sum(n, m) version

这是 sum(n, m) 版本

auto sum = [](auto n, auto m) {
    return ([](auto f, auto n, auto m) {
        int res = f(f, n, m);
        return res;
    })(
        [](auto f, auto n, auto m) -> int
        {
            if (n > m)
                return 0;
            else {
                int sum = n + f(f, n + 1, m);
                return sum;
            }
        },
        n, m); };

auto result = sum(1, 10); //result == 55