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

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

Answer 2

Interesting question. The problem is more about the nature of yield though co-iterators.

Basically, if you need to yield in C++, you need to implement an iterator-like state machine, which is pretty much the idea of co-recursion anyhow.

A working example would require implementing a tree class, but here is a partial implementation of BFS using what is basically the strategy in the wiki article (fixed a little because their algorithm is a bit silly)

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

Technically, you don't need to mimic their yield generator strategy to do this. Rather than defining the class, you could simple use the queue directly in your code.

This differs a bit from the wikipedia algorithm because... well the wiki algorithm isn't ideal. They're mostly identical, but the wikipedia example is kind of a poor-man's queue.

Answer 3

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.