8

我正在开发一个需要与树结构频繁交互的 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，互联网的其余部分似乎没有关于该主题的有用信息。

4

3 回答 3

4

所以有几种方法。

您可以按照建议等待 await 关键字到达，但这似乎是长期的。如果您确实等待 await，这里有人用 await 实现了 yield，至少乍一看应该可以在 C++ 中使用。

您可以编写一个生成迭代器助手，或者从 boost 中借用一个，并从中制作一个生成器。

您可以使用存储在 a 中的可变 lambda std::function，可能返回 a std::experimental::optional（或 boost 可选）。

但那些大多只是让它变得漂亮。所以让我们变得丑陋。我会用 C++14 写这个，因为懒惰。

struct generator {
  using trees=std::vector<tree>;
  trees m_cur;      
  trees m_next;
  bool next(value* v){
    while(true){
      if (m_cur.empty()){
        m_cur=std::move(m_next);
        m_next.clear();
        std::reverse(begin(m_cur),end(m_cur));
        if(m_cur.empty())
          return false;
      }
      auto t = m_cur.back();
      m_cur.pop_back();
      if(!t)continue;
      *v = get_value(t);
      m_next.push_back(get_left(t));
      m_next.push_back(get_right(t));
      return true;
    }
  }
  generator(tree t):m_cur{t}{};
};

树类型需要自由函数来获取值、获取左右和运算符！判断它是否为空。它需要是可复制的（指针可以）。

利用：

generator g(some_tree);
value v;
while(g.next(&v)){
  std::cout<<v<<'\n';
}

现在这很难看——例如，我们手动维护状态。

我相信通过 await 会出现一种更神奇的方式，但这不是标准化的。

生成器迭代器会将丑陋的接口隐藏在迭代器门面后面，但状态仍然是手动管理的。

你也许可以用 lambda 做一些花哨的事情，但我不确定 lambda 是否可以返回它自己的类型。也许。（G:{}->{G,Maybe X} 或类似的）

现在，因为它太棒了，这里是n4134提出的await/yield解决方案。

template<class T0, class...Ts>
std::vector<std::decay_t<T0>> vec_of(T0&& t0, Ts&&... ts) {
  return {std::forward<T0>(t0), std::forward<Ts>(ts)...};
}
auto breadth_first = [](auto&& tree){
  auto tree_list = vec_of(decltype(tree)(tree));
  while(!tree_list.empty()) {
    decltype(tree_list) new_tree_list;
    for(auto&& tree:tree_list) {
      if (tree) {
        yield get_value(tree);
        new_tree_list.push_back(get_left(tree));
        new_tree_list.push_back(get_right(tree));
      }
    }
    tree_list = std::move(new_tree_list);
  }
};

这基本上是python代码的逐行翻译。我确实写了一个vec_of辅助函数来替换[]python。

利用：

for(auto&& value : breadth_first(tree)) {
  std::cout << value;
}

这很漂亮。

于 2015-02-12T18:58:57.993 回答
3

以下与给定的 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();
        }
    });
}
于 2015-02-14T01:15:24.057 回答
2

有趣的问题。问题更多是关于yield协同迭代器的性质。

基本上，如果你需要yield在 C++ 中，你需要实现一个类似迭代器的状态机，无论如何这几乎是共同递归的想法。

一个工作示例需要实现一个树类，但这里是使用基本上是 wiki 文章中的策略的 BFS 的部分实现（修复了一点，因为他们的算法有点傻）

for (bfs_generator i = bfs_generator(myTree);
    i.is_good();
    i.next())
{
  print (i.value());
}

// Iterator-style operation overloads may be more appropriate, but I don't want to deal with the syntactic details
// I assume a standard C Node struct with left and right pointers implementation of your tree.
class bfs_iterator
{
  // The Python example is a little strange because it expresses the state as two lists, when only one is necessary
  std::queue<Node *> tree_list;

  public:
  bfs_iterator (Node * root)
  {
    tree_list.push_back(root);
  }

  bool is_good()
  {
    return tree_list.empty();
  }

  void next()
  {
    // Pop the front of the queue then add the children to the queue.
    if (!tree_list.empty())
    {
      Node * node = tree_list.front();
      tree_list.pop();

      if (node->left)
        tree_list.push(node->left);
      if (node->right)
        tree_list.push(node->right);
    }
  }

  MyTree::value value()
  {
    return tree_list.front()->value;
  }
};

从技术上讲，您不需要模仿他们的yield生成器策略来执行此操作。您可以直接在代码中简单地使用队列，而不是定义类。

这与维基百科算法有点不同，因为......维基算法并不理想。它们大多相同，但维基百科的例子有点像穷人的队列。

于 2015-02-12T20:19:52.953 回答