How to accomplish corecursion in C++?

Question

I'm working on a C++ project that requires frequent interaction with a tree structure, which means lots of recursive functions, and I'm looking for ways to improve the code. I came across corecursion the other day, and I'm interested in exploring this strategy for my application.

However, I haven't been able to find any examples of how to accomplish corecursion with C++. To make my question specific, how can I do this tree traversal using corecursion in C++?

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

If doing this is just a bad idea, let me know. That said, having some answer to this on the internet would be useful for those trying to do this in the future. There are no questions on SO matching [c++] corecursion and the rest of the internet seems devoid of useful information on the subject.

Answer 1

So there are a few approaches.

You can wait for the await keyword to arrive, as proposed, but that seems long term. If you do wait for await, here is someone implementing yield with await, which at least at first glance should work in C++.

You can write a generating iterator helper, or borrow one from boost, and make a generator from it.

You can use a mutable lambda stored in a std::function, maybe returning a std::experimental::optional (or boost optional).

But those mostly just make it pretty. So lets get ugly. I will write this in C++14, because lazy.

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}{};
};

The tree type needs free functiins to get value, get left and right, and an operator! to tell if it is null. And it needs to be copyable (a pointer would do).

Use:

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

Now this is ugly -- we maintain the state manually for example.

A more magic way is coming via await I believe, but that is not standardized.

A generator iterator would hide the ugly interface behind an iterator fascade, but state is still managed manually.

You might be able to do something fancy with lambdas, but I am unsure if a lambda can return its own type. Maybe. (G:{}->{G,Maybe X} or somesuch)

---

Now, because it is awesome, here is the n4134 proposed await/yield solution.

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);
  }
};

which is basically a line to line translation of the python code. I did write a vec_of helper function to replace [] in python.

Use:

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

which is pretty.

Answer 2

The following is almost identical to the given python implementation and you can use it now in production:

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 << " ";
}

To avoid allocations/deallocations I'd probably do it this way:

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();
        }
    });
}