C++14中递归调用泛型lambda表达式的类型

Question

(1) 中的 lambda 表达式的类型是什么？

为什么这段代码可以通过？

#include<functional>
#include<iostream>


int main() {
    std::cout << 
        [](auto&& f0,auto&& a0){return f0(f0,a0);}
        (
            [](auto& f,auto&& a)->int{ return (a>1) ? f(f,a-1)*a : 1; }, // (1)
            5
         )
         << std::endl;
}

我认为无限递归是由这段代码中lambda 表达式(1) 的类型推断引起的。我认为 auto& f 被替换为类型名称，例如 std::function<int(std::function<int(std::function<int(......)>)>)>。

请指出我的错误

Answer 1

来自 [expr.prim.lambda]，强调我的：

The lambda return type is auto, which is replaced by the trailing-return-type if provided and/or deduced from return statements as described in 7.1.6.4.

您提供了一个 trailing-return-type，即代码中的 ->int，因此不必进行类型推导。 return 类型就是 int.

但是，即使没有 ->int，只要提供 if 语句而不是使用条件运算符，您仍然可以编译函数：

auto f = [](auto& f0, auto&& a) {
    if (a <= 1) {
        return 1; // this *must* be the first return case.
    }
    else {
        return f0(f0, a-1) * a;
    }
};

std::cout << f(f, 5) << std::endl; // prints 120

这种情况，而且只有这种情况，符合上述第 7.1.6.4 节中提到的规则之一 [dcl.spec.auto]:

If the type of an entity with an undeduced placeholder type is needed to determine the type of an expression, the program is ill-formed. Once a return statement has been seen in a function, however, the return type deduced from that statement can be used in the rest of the function, including in other return statements.
[Example:
 auto sum(int i) {
     if (i == 1)
         return i; // sum’s return type is int
     else
         return sum(i-1)+i; // OK, sum’s return type has been deduced
 }
—end example ]

Answer 2

第一个错误：std::function 是与任何 lambda 无关的类型。

lambda 是一种匿名类型，具有 operator() 和一些其他已知属性。

std::function<R(Args...)> 是一个类型擦除 class 用于复制构造，使用 Args... 和 return R 销毁和调用。它可以从 lambda 构造，但不是相关类型。

由于无法命名 lambda 的类型，因此使用 std::function 来存储它很常见。但是，lambda 不是 std::function。 std::functions 的类型擦除和多态性几乎不可避免地产生开销：lambda 没有任何多态性，这使得编译器很容易理解 () 在调用时做了什么。

在你的例子中，你有两个 lambda。

您的第一个 lambda 是：

[](auto&& f0,auto&& a0){return f0(f0,a0);}

这看起来像是 y 组合器的一种形式或变体，用于帮助递归。本例中的 operator() 有签名：

template<class F0, class A0>
auto operator()(F0&&,A0&&)const
-> std::result_of_t<F0&(F0&,A0&)>

大致。

一个更有用的版本（在我看来）是：

[](auto&& f0){
  return [f0=std::forward<decltype(f0)>(f0)]
    (auto&&...args) {
      return f0(f0, std::forward<decltype(args)>(args)...);
    };
}

它接受一个 f0，存储它，并使用首先传递 f0 的任何参数调用它。这使您可以绑定递归 'out of sight'。使内部 lambda mutable 是可选的（取决于您是否想在 const 上下文中调用）

无论如何，下一个 lambda：

[](auto& f,auto&& a)->int{ return (a>1) ? f(f,a-1)*a : 1; }

有一个 operator() 签名：

template<class F, class A>
auto operator()(F&,A&&)const
-> int

然后将第二个 lambda 的实例传递给第一个，加上一个参数，它计算 n!。

template运算符()推导的类型不依赖于参数本身推导的类型，因此不存在无限类型推导问题。内部 lambda 的 return 类型被硬编码为 int，因此您不必递归地推断出 () 的内容 return 就可以知道它 return s int.

但是，如果您想将第一个 lambda 存储在 std::function 中，您会失望的。 std::function不能擦除template operator()：只能擦除固定的签名，template成员是方法工厂，不是方法本身。

但是，还记得我上面的 y 组合的更好版本吗？

调用你的第一个 lambda g，你的第二个 h 和我的 lambda y 以及我的 lambda returns z.

则g(h,x) = y(h)(x)——而y(h)可以存入一个std::function<int(int)>没问题。我们隐藏了递归中基本上需要递归类型签名的部分，std::function不支持¹。剩下的，虽然它有一个 template operator()，但可以绑定到一个简单的签名。

¹ 请注意，您可以编写 std::function 来支持递归签名，例如 std::function< std::vector<SELF_TYPE>(int) >。您可以看到这可能如何与 boost::variant 如何与递归变体一起工作。

C++14中递归调用泛型lambda表达式的类型

Type of recursive calling generic lambda expression in C++14

c++

recursion

lambda

c++14