c++ - 递归函数的返回类型推导
问题描述
最近,我阅读了Barry对这个问题Recursive lambda functions in C++11的回答:
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)...);
}
};
// deduction guide
template <class F> y_combinator(F) -> y_combinator<F>;
基本上,y_combinator
允许人们更轻松地编写递归 lambda 表达式(例如,无需删除 a std::function
)。当我玩的时候y_combinator
,我发现了一些奇怪的东西:
int main() {
// Case #1 compiles fine
y_combinator{[](auto g, int a, int b) {
if (a >= b) return 0;
return 1 + g(a + 1, b);
}}(1, 2);
// Case #2 deos not compile
y_combinator{[](auto g, int a) {
if (a >= 0) return 0;
return 1 + g(a + 1);
}}(1);
// Case #3 compiles just fine
y_combinator{[](auto g, int a)->int {
if (a >= 0) return 0;
return 1 + g(a + 1);
}}(1);
}
案例#1 和案例#3 编译良好,而案例#2 不编译。我使用 Clang 10.0 和 GCC 9.3 得到了相同的结果。对于案例 #2,Clang 说
prog.cc:25:18: error: no matching function for call to object of type 'std::__1::reference_wrapper<const y_combinator<(lambda at prog.cc:23:18)> >'
return 1 + g(a + 1);
^
- 案例#1 和案例#2 的结果有何不同?
- 为什么尾随返回类型会在案例 #2 和案例 #3 之间产生差异?
您可以在Wandbox上查看。
解决方案
不同之处在于,在 #1 中,初始调用和递归调用y_combinator
具有不同的参数类型,而在 #2 中,它们具有相同的参数类型(包括值类别)。
在 #1 中,初始参数(1, 2)
都是 int prvalue,而递归参数g(a + 1, b)
分别是 int prvalue 和 int lvalue。同时在 #2 中,初始参数(1)
和递归参数g(a + 1)
都是 int prvalue。您可以检查对#1 进行更改以使两个递归参数都是int prvalue(例如调用g(a + 1, b + 0)
)会破坏它,而更改#2 以将int lvalue 作为递归参数(例如g(++a)
)将修复它。
这意味着初始调用的返回类型推导是自引用的,因为它取决于完全相同的调用的类型y_combinator<lambda #2>::operator()<int>(int&&)
(而在 #1 中,初始调用y_combinator<lambda #1>::operator()<int, int>(int&&, int&&)
取决于y_combinator<lambda #1>::operator()<int, int&>(int&&, int&)
)。
像 #3 那样显式地提供返回类型意味着没有自引用类型推导,一切都很好。
您可能会问,既然递归案例仍然是自引用的(注意所有 3 个编译器都同意),为什么 #1 可以。这是因为一旦我们可以进入 lambda 自己的类型推导,[dcl.spec.auto]/10 就会启动,并且第一条return
语句给 lambda 一个返回类型,所以当它递归调用时g
,该类型推导已经成功。
图表通常有助于:
y_combinator<lambda #1>::operator()<int, int>
-> forwards to [lambda #1]::operator()<y_combinator<lambda #1>> {
has return type int by [dcl.spec.auto]/10
calls y_combinator<lambda #1>::operator()<int, int&> (not previously seen)
-> forwards to [lambda #1]::operator()<y_combinator<lambda #1>>
-> already deduced to return int
-> this is OK
}
y_combinator<lambda #2>::operator()<int>
-> forwards to [lambda #2]::operator()<y_combinator<lambda #2>> {
has return type int by [dcl.spec.auto]/10
calls y_combinator<lambda #2>::operator()<int>
but y_combinator<lambda #2>::operator()<int> has incomplete return type at this point
-> error
}
一个修复(感谢@aschepler)是记住已经调用 lambda 的参数列表,并提供一个“干净的”包装器,其功能调用运算符尚未对每组新参数进行返回类型推导类型:
template<class...> struct typelist {};
template<class T, class... Ts>
constexpr bool any_same = (std::is_same_v<T, Ts> || ...);
template <class F>
struct y_combinator {
template <class... TLs>
struct ref {
y_combinator& self;
template <class... Args>
decltype(auto) operator()(Args&&... args) const {
using G = std::conditional_t<
any_same<typelist<Args...>, TLs...>,
ref<TLs...>,
ref<TLs..., typelist<Args...>>>;
return self.f(G{self}, std::forward<Args>(args)...);
}
};
F f;
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return ref<>{*this}(std::forward<Args>(args)...);
}
};
template <class F> y_combinator(F) -> y_combinator<F>;
推荐阅读
- swift - 使用 UIViewControllerRepresentable 更新值时弹出窗口崩溃
- apache-spark - Does Spark support load balancing in heterogeneous clusters?
- django - 如何将字段添加到查询集并在循环中填充它?
- assembly - 在 MASM64 中是否有将 16 位立即数压入堆栈的指令?
- assembly - 在 6502 汇编器中编写子程序的最佳方法?
- mongodb - 通过聚合查找查询预订的可用房间
- android - 如何使用 SDK 版本 30 为 Android 构建 Godot 项目?
- mysql - 如何在 MySQL 中查询 AM 和 PM varchar 时间之间的数据
- angularjs - 如何在 chrome 和 windows 7 中解决“您的连接不是私有的”
- javascript - 获取精确宽度元素