如何在C++中完成corecursion？

Question

我正在开发一个C++项目,需要经常与树结构交互,这意味着许多递归函数,我正在寻找改进代码的方法.前几天我遇到了corecursion,我有兴趣为我的应用程序探索这个策略.

但是,我还没有找到任何如何用C++完成corecursion的例子.为了使我的问题具体,我如何在C++中使用corecursion进行树遍历？

def bf(tree):
    tree_list = [tree]
    while tree_list:
        new_tree_list = []
        for tree in tree_list:
            if tree is not None:
                yield tree.value
                new_tree_list.append(tree.left)
                new_tree_list.append(tree.right)
        tree_list = new_tree_list

如果这样做只是一个坏主意,请告诉我.也就是说,在互联网上得到一些答案对于那些试图在未来做这件事的人来说会很有用.关于SO匹配没有任何问题,[c++] corecursion互联网的其余部分似乎缺乏有关该主题的有用信息.

Answer 1

以下内容与给定的 python 实现几乎相同，您现在可以在生产中使用它：

Live On Coliru

#include <vector>
#include <iostream>
#include <boost/coroutine/all.hpp>

using namespace std;

struct Node {
    char value;
    Node *left;
    Node *right;
};

using generator =
    boost::coroutines::asymmetric_coroutine<decltype(Node::value)>::pull_type;

generator bf(Node *tree) {                                //def bf(tree):
    return generator([=](auto &yield) {                   //
        vector<Node *> tree_list = {tree};                //    tree_list = [tree]
        while (!tree_list.empty()) {                      //    while tree_list:
            vector<Node *> new_tree_list;                 //        new_tree_list = []
            for (auto tree : tree_list) {                 //        for tree in tree_list:
                if (tree != nullptr) {                    //            if tree is not None:
                    yield(tree->value);                   //                yield tree.value
                    new_tree_list.push_back(tree->left);  //                new_tree_list.append(tree.left)
                    new_tree_list.push_back(tree->right); //                new_tree_list.append(tree.right)
                }                                         //
            }                                             //
            tree_list = move(new_tree_list);              //        tree_list = new_tree_list
        }                                                 //
    });                                                   //
}                                                         //

int main() {
    Node a{'a'}, b{'b'}, c{'c'}, d{'d'}, e{'e'};

    a.left = &b;
    a.right = &c;
    b.right = &d;
    d.left = &e;

    for (auto node_value : bf(&a))
        std::cout << node_value << " ";
}

为了避免分配/解除分配，我可能会这样做：

generator bf(Node *tree) {
    return generator([=](auto &yield) {
        vector<Node *> tree_list = {tree}, new_tree_list;
        while (!tree_list.empty()) {
            for (auto tree : tree_list) {
                if (tree != nullptr) {
                    yield(tree->value);
                    new_tree_list.push_back(tree->left);
                    new_tree_list.push_back(tree->right);
                }
            }
            swap(tree_list, new_tree_list);
            new_tree_list.clear();
        }
    });
}