gpt4 book ai didi

c++ - 如何在 C++ 中完成 corecursion?

转载 作者:可可西里 更新时间:2023-11-01 17:40:16 24 4
gpt4 key购买 nike

我正在从事一个 C++ 项目,该项目需要与树结构进行频繁交互,这意味着有很多递归函数,我正在寻找改进代码的方法。我遇到了corecursion前几天,我有兴趣为我的应用程序探索这种策略。

但是,我还没有找到任何有关如何使用 C++ 完成 corecursion 的示例。为了使我的问题具体化,我该怎么做 this tree traversal using corecursion在 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

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

最佳答案

所以有几种方法。

您可以按照建议等待 await 关键字到达,但这似乎是长期的。如果你等待等待,here is someone implementing yield with await ,至少乍一看应该适用于 C++。

你可以写一个生成迭代器的助手,或者从 boost 借用一个,然后用它做一个生成器。

您可以使用存储在 std::function 中的可变 lambda,可能会返回一个 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 会带来更神奇的方法,但这还没有标准化。

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

您也许可以用 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_o​​f 辅助函数来替换 python 中的 []

使用:

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

这很漂亮。

关于c++ - 如何在 C++ 中完成 corecursion?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28484131/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com