没有Y Combinator的递归lambda回调 [英] Recursive lambda callbacks without Y Combinator
问题描述
建议的递归方法是让函数引用自己：
p> std :: function< void（int）> recursive_function = [&]（int recurse）{
std :: cout<递归< std :: endl;
if（recurse> 0）{
recursive_function（recurse - 1）;
}
};
从函数返回时失败：
#include< functional>
#include< iostream>
volatile bool no_optimize = true;
std :: function< void（int）> get_recursive_function（）{
std :: function< void（int）> recursive_function = [&]（int recurse）{
std :: cout<递归< std :: endl;
if（recurse> 0）{
recursive_function（recurse - 1）;
}
};
if（no_optimize）{
return recursive_function;
}
return []（int）{};
}
int main（int，char **）{
get_recursive_function（）（10）;
}
c $ c> 10 ，因为引用无效。
我如何做？我已成功使用我认为是 Y Combinator （我将发布为一个答案），但它是非常混乱。有更好的方法吗？
其他尝试
尝试了一种无聊的方法，将它包装在另一层回调中：
#include< functional&
#include< iostream>
#include< memory>
volatile bool no_optimize = true;
std :: function< void（int）> get_recursive_function（）{
//关闭以允许自引用
auto recursive_function = []（int recurse）{
//执行工作的实际函数。
std :: function< void（int）> function = [&]（int recurse）{
std :: cout<递归< std :: endl;
if（recurse> 0）{
function（recurse - 1）;
}
};
function（recurse）;
};
if（no_optimize）{
return recursive_function;
}
return []（int）{};
}
int main（int，char **）{
get_recursive_function（）（10）;
}
但这在实际情况下会失败，由外部循环：
#include< functional>
#include< iostream>
#include< memory>
#include< queue>
volatile bool no_optimize = true;
std :: queue< std :: function< void（void）>>回调;
std :: function< void（int）> get_recursive_function（）{
//关闭以允许自引用
auto recursive_function = []（int recurse）{
//执行工作的实际函数。
std :: function< void（int）> function = [&]（int recurse）{
std :: cout<递归< std :: endl;
if（recurse> 0）{
callbacks.push（std :: bind（function，recurse - 1））;
}
};
function（recurse）;
};
if（no_optimize）{
return recursive_function;
}
return []（int）{};
}
int main（int，char **）{
callbacks.push（std :: bind（get_recursive_function（），10）
while（！callbacks.empty（））{
callbacks.front（）（）;
callbacks.pop（）;
}
}
code>，然后 9 ，然后分段错误。
正如您正确地指出，来自lambda捕获 [&] 的引用无效。
返回是各种各样的函子，所以我认为返回的确切类型不重要，只是它表现为一个函数，即可调用。
如果 recursive_function 包装在 struct 或 class 成员的 recursive_function 调用操作符。捕获此变量时出现问题。它将在创建时捕获 this ，所以如果对象被复制一下，原来的 this 可能不再有效。所以一个合适的这个可以在执行时传递给函数（这这个问题可能不是一个问题，但它在很大程度上取决于调用函数的时间和方式）。
#include< functional&
#include< iostream>
volatile bool no_optimize = True;
struct recursive {
std :: function< void（recursive *，int）> recursive_function = []（recursive * me，int recurse）{
std :: cout<递归< std :: endl;
if（recurse> 0）{
me-> recursive_function（me，recurse - 1）;
}
};
void operator（）（int n）
{
if（no_optimize）{
recursive_function（this，n）
}
}
};
递归get_recursive_function（）{
return recursive（）;
}
int main（int，char **）{
get_recursive_function（）（10）;
}
或者，如果 recursive_function 可以 static 然后在原始代码示例中这样声明它也可以为你的技巧。
我想为上面的答案添加一些通用性，即使它成为一个模板;
#include< functional>
#include< iostream>
volatile bool no_optimize = true;
template< typename Signature>
struct recursive;
template< typename R，typename ... Args>
struct recursive< R（Args ...）> {
std :: function< R（recursive const& Args ... args）> recursive_function;
recursive（）= default;
递归（decltype（recursive_function）const& func）：recursive_function（func）
{
}
template< typename ... T&
R运算符（）（T& ... args）const
{
return recursive_function（* this，std :: forward< Args>（args）...）
}
};
递归< void（int）> get_recursive_function（）
{
使用result_type = recursive< void（int）> ;;
if（！no_optimize）{
return result_type（）;
}
result_type result（[]（result_type const& me，int a）{
std :: cout< a<< std :: endl;
if（a> 0）{
me（a - 1）;
}
}
返回结果;
}
int main（int，char **）{
get_recursive_function（）（10）;
}
这是如何工作的？基本上，它将递归从函数内部（即调用自身）移动到对象（即对象本身上的函数运算符）以实现递归。在 get_recursive_function 中，结果类型 recursive< void（int）> 用作递归函数的第一个参数。它是 const& ，因为我已经实现 operator（）为 const 符合大多数标准算法和lambda函数的默认值。它需要一些来自函数实现者的合作（即使用 me 参数;本身为 * this ）来获得递归的工作，但对于那个价格，你得到一个不依赖于栈引用的递归lambda。
I wish to create a callback that recursively returns itself as a callback.
The suggested method to recurse is for the function to have a reference to itself:
std::function<void (int)> recursive_function = [&] (int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
recursive_function(recurse - 1);
}
};
This fails as soon as you return it from a function:
#include <functional>
#include <iostream>
volatile bool no_optimize = true;
std::function<void (int)> get_recursive_function() {
std::function<void (int)> recursive_function = [&] (int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
recursive_function(recurse - 1);
}
};
if (no_optimize) {
return recursive_function;
}
return [] (int) {};
}
int main(int, char **) {
get_recursive_function()(10);
}
which gives a segmentation fault after outputting 10 because the reference becomes invalid.
How do I do this? I have successfully used what I think is a Y Combinator (which I'll post as an answer), but it is hugely confusing. Is there a better way?
Other attempts
I have tried the boring approach of wrapping it in another layer of callbacks:
#include <functional>
#include <iostream>
#include <memory>
volatile bool no_optimize = true;
std::function<void (int)> get_recursive_function() {
// Closure to allow self-reference
auto recursive_function = [] (int recurse) {
// Actual function that does the work.
std::function<void (int)> function = [&] (int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
function(recurse - 1);
}
};
function(recurse);
};
if (no_optimize) {
return recursive_function;
}
return [] (int) {};
}
int main(int, char **) {
get_recursive_function()(10);
}
but this fails in the actual scenario, where the function is being delayed and called by an outer loop:
#include <functional>
#include <iostream>
#include <memory>
#include <queue>
volatile bool no_optimize = true;
std::queue<std::function<void (void)>> callbacks;
std::function<void (int)> get_recursive_function() {
// Closure to allow self-reference
auto recursive_function = [] (int recurse) {
// Actual function that does the work.
std::function<void (int)> function = [&] (int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
callbacks.push(std::bind(function, recurse - 1));
}
};
function(recurse);
};
if (no_optimize) {
return recursive_function;
}
return [] (int) {};
}
int main(int, char **) {
callbacks.push(std::bind(get_recursive_function(), 10));
while (!callbacks.empty()) {
callbacks.front()();
callbacks.pop();
}
}
which gives 10, then 9 and then segmentation faults.
As you rightly pointed out, there is an invalid reference from the lambda capture [&].
Your returns are functors of various sorts, so I assume that the exact type of the return is not important, just that it behaves as a function would i.e. be callable.
If the recursive_function is wrapped in a struct or class you can map the call operator to the recursive_function member. A problem arises with the capture of the this variable. It'll be captured with the this on creation, so if the object is copied around a bit, the original this may no longer be valid. So an appropriate this can be passed in to the function at execution time (this this issue may not be a problem, but it depends heavily on when and how you call the function).
#include <functional>
#include <iostream>
volatile bool no_optimize = true;
struct recursive {
std::function<void (recursive*, int)> recursive_function = [] (recursive* me, int recurse) {
std::cout << recurse << std::endl;
if (recurse > 0) {
me->recursive_function(me, recurse - 1);
}
};
void operator()(int n)
{
if (no_optimize) {
recursive_function(this, n);
}
}
};
recursive get_recursive_function() {
return recursive();
}
int main(int, char **) {
get_recursive_function()(10);
}
Alternatively, if the recursive_function can be static then declaring it as such in the original code sample may also do the trick for you.
I wanted to add some generality to the answer above, i.e. make it a template;
#include <functional>
#include <iostream>
volatile bool no_optimize = true;
template <typename Signature>
struct recursive;
template <typename R, typename... Args>
struct recursive<R (Args...)> {
std::function<R (recursive const&, Args... args)> recursive_function;
recursive() = default;
recursive(decltype(recursive_function) const& func) : recursive_function(func)
{
}
template <typename... T>
R operator()(T&&... args) const
{
return recursive_function(*this, std::forward<Args>(args)...);
}
};
recursive<void (int)> get_recursive_function()
{
using result_type = recursive<void (int)>;
if (!no_optimize) {
return result_type();
}
result_type result ([](result_type const& me, int a) {
std::cout << a << std::endl;
if (a > 0) {
me(a - 1);
}
});
return result;
}
int main(int, char **) {
get_recursive_function()(10);
}
How does this work? Basically it moves the recursion from inside the function (i.e. calling itself) to an object (i.e. the function operator on the object itself) to implement the recursion. In the get_recursive_function the result type recursive<void (int)> is used as the first argument to the recursive function. It is const& because I've implemented the operator() as const in line with most standard algorithms and the default for a lambda function. It does require some "co-operation" from the implementer of the function (i.e. the use of the me parameter; itself being *this) to get the recursion working, but for that price you get a recursive lambda that is not dependent on a stack reference.
这篇关于没有Y Combinator的递归lambda回调的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
