haskell - 重写树

Question

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

这是到目前为止我得到的橘子树（跟随橙色箭头）

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

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

我想知道这个算法是否有名称和/或红树中操作员位置的名称是什么。是前缀吗？

谢谢。

Answer 1

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

假人的递归方案？

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