haskell - 重写树

Question

我有一个表示类型签名的数据结构，这个数据结构是一棵树，在第一张图中以红色为例。我想要黑色的，到目前为止我只有橙色的(第二张图片)，它是类型树，但与左侧相关联。



这是到目前为止我得到的橙树(按照橙色箭头)



我通过漂亮地打印树然后用解析器组合器解析它来解决这个问题，但这种低效率是不希望的。我想我可以有另一种算法来从橙树转换为黑树，但如果不是组合两个算法，我只能写一个算法会更好。

当我在上面写我的解决方案时，我会将它标记为 Haskell。我可以提供代码来获取像红树这样的数据结构，但我认为它只会使解决方案的尝试复杂化。

我想知道这个算法是否有名称和/或红树中运算符(operator)位置的名称是什么。是前缀吗？

谢谢。

Answer 1

看看递归方案。这里有一个相关的问题，其中包含大量链接:

Recursion schemes for dummies?

该问题的所有链接都非常好，但我会特别查看 Tim Williams 的幻灯片(链接在我对该问题的回答中)，了解各种不同递归模式的具体实现(其中大部分是在树结构上演示的) )。