递归自底向上遍历代数数据类型

Question

在Haskell中处理可观的代数数据类型时，存在一种特殊的递归遍历，该遍历遍历不能通过折叠数据类型来捕获。例如，假设我有一个简单的数据类型，用于表示命题逻辑中的公式，并在其上定义了折叠： 通用标签

此递归方案为诸如评估或查找文字之类的递归提供了简洁的答案： 通用标签

但是，当我希望“扫描”数据类型时，效果并不理想。在下面，simp是由必要的模式匹配定义的辅助功能： 通用标签

使用折叠来定义简化，当然会产生错误的结果。例如，以下内容不是等效的： 通用标签

像 simplify 这样的递归的最佳解决方案是什么？我应该定义与遍历数据类型相似的通用遍历，还是有用于定义此类函数的标准递归模式？

Answer 1

您尝试了 Uniplate 吗？对于仅适用于单一类型的操作，它可以执行自下而上的重写，并重写直到固定点为止。

例如： 通用标签

与您相关的功能是 transform 和 rewrite 。

要获取有关Uniplate的更深入的文档，还可以 a纸（PDF）。