C++ 11中的递归lambda函数

Question

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

有人可以点亮这个吗？

Answer 1

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

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

考虑对代码的这种轻微修改,它可能更有意义:

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);
};

显然,这不适用于汽车.递归lambda函数运行得非常好(至少它们在MSVC中,我对它们有经验),它只是它们与类型推断不兼容.

Answer 2

诀窍是将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/recursive-lambdas-in-c14/找到了这个简单的技巧

它确实需要C++ 14而问题出在C++ 11上,但对大多数人来说可能都很有趣.

继续进行std::function也是可能的,但可能会导致代码变慢.但不总是.看看std :: function vs template的答案

Answer 3

使用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.
        // [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)};
}

您的原始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);
  }
});

Answer 4

我有另一种解决方案,但只能使用无状态lambda:

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

这里的诀窍是lambdas可以访问静态变量,你可以将无状态转换为函数指针.

您可以将它与标准lambdas一起使用:

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);
    };
}

它在GCC 4.7中的工作

Answer 5

在 C++23 中，添加了显式对象参数（ P0847：推导此）：

auto f = [](this auto& self, int i) -> int
{
    return i > 0 ? self(i - 1) + i : 0;
}

目前，它仅在 Clang 和 EDG eccp 中可用，并且在 MSVC 中部分可用：

https://godbolt.org/z/f3E3xT3fY

Answer 6

您可以递归地进行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));

要非常小心,不要超出包装f的范围.

Answer 7

要在不使用外部类和函数(如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}}});
}

打印:

1
 2
  8
 3
  5
   7
  6
 4

注意,应明确指定lambda的结果类型.

Answer 8

我使用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);
}

产生结果:

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

(注意:我还确认了一个从cin获取输入的版本,以便消除编译时评估)

Clang还会生成编译器警告:

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

这是预期的,安全的,但应该注意.

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

注意:

正如一位评论者所指出的,似乎VC++的最新版本已经找到了一种方法来优化它以达到同等性能的程度.也许我们毕竟不需要更好的方法来解决这个问题(除了语法糖).

此外,正如其他一些SO帖子在最近几周所概述的那样,std::function<>自身的性能可能是直接调用减速与直接调用函数的原因,至少当lambda捕获太大而无法适应std::function小型仿函数的某些库优化空间用途时(我想有点像各种短字符串优化？).