Как выполнить corecursion в C ++?
Я работаю над проектом 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 и остальная часть Интернета кажется лишенной полезной информации по предмету.
Решение
Следующее практически идентично данной реализации Python, и вы можете использовать его сейчас в производстве:
#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();
}
});
}
Другие решения
Так что есть несколько подходов.
Вы можете дождаться прибытия ключевого слова await, как это предлагается, но это кажется долгосрочным. Если ты подождешь ожидания, вот кто-то реализующий выход с await, который по крайней мере на первый взгляд должен работать в C ++.
Вы можете написать вспомогательный итератор, или позаимствовать его у boost, и сделать из него генератор.
Вы можете использовать изменяемую лямбду, хранящуюся в std::functionможет быть, возвращая std::experimental::optional (или буст по желанию).
Но в основном это просто красиво. Так что давайте уродимся. Я напишу это в 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';
}
Теперь это безобразно — мы поддерживаем состояние, например, вручную.
Я верю, что через ожидание приходит более волшебный путь, но он не стандартизирован.
Генератор-итератор скрывал бы отвратительный интерфейс за фасадом итератора, но состояние по-прежнему управляется вручную.
Возможно, вы сможете сделать что-то необычное с лямбдами, но я не уверен, что лямбда может вернуть свой собственный тип. Может быть. (G: {} -> {G, может быть, 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 вспомогательная функция для замены [] в питоне.
Использование:
for(auto&& value : breadth_first(tree)) {
std::cout << value;
}
что довольно
Интересный вопрос. Проблема больше в природе yield хотя ко-итераторы.
В основном, если вам нужно yield в C ++ вам нужно реализовать конечный автомат, похожий на итератор, который в любом случае является идеей совместной рекурсии.
Рабочий пример потребовал бы реализации класса дерева, но вот частичная реализация 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 Генератор стратегии, чтобы сделать это. Вместо того, чтобы определять класс, вы можете просто использовать очередь прямо в своем коде.
Это немного отличается от алгоритма википедии, потому что … хорошо, алгоритм вики не идеален. Они в основном идентичны, но пример из Википедии — своего рода очередь для бедняков.