在Haskell中一般遍历树的最简单方法

Question

假设我使用language-javascript库在Haskell中构建AST。AST具有不同类型的节点，并且每个节点可以具有这些不同类型的字段。每个类型可以具有许多构造函数。（所有类型的实例Data，Eq和Show）。

我想计算树中每种类型的构造函数的出现。我可以使用它toConstr来获得构造函数，理想情况下，我会先创建一个Tree -> [Constr]函数fisrt（然后计数很容易）。

有不同的方法可以做到这一点。显然，模式匹配太冗长了（使用9-28个构造函数可以想象3种类型）。

因此，我想使用通用遍历，并尝试在SYB库中找到解决方案。

有一个everywhere函数不适合我的需求，因为我不需要Tree -> Tree转换。
存在gmapQ，就其类型而言似乎很合适，但事实证明它不是递归的。
到目前为止，最可行的选择是everywhereM。它仍然会进行无用的转换，但是我可以使用Writer来收集toConstr结果。不过，这种方式确实感觉不正确。

是否有其他选择不会执行无用的转换（对于此任务），而仍然提供构造函数的列表？（它们在树中出现的顺序暂时不重要）

Answer 1

不知道这是否最简单，但是：

> data T = L | B T T deriving Data
> everything (++) (const [] `extQ` (\x -> [toConstr (x::T)])) (B L (B (B L L) L))
[B,L,B,B,L,L,L]

这里++说明如何合并子项的结果。

const []是不是类型的子项的基本情况T。对于类型T，我们应用\x -> [toConstr (x::T)]。

如果您有多种树类型，则需要使用扩展查询

const [] `extQ` (handleType1) `extQ` (handleType2) `extQ` ...

这是确定我们要采用构造方法的类型所必需的。如果类型很多，则可以通过某种方式将其缩短。

注意上面的代码在大树上不是很有效，因为++以这种方式使用会导致二次复杂性。从性能角度考虑，最好返回a Data.Map.Map Constr Int。（即使我们确实需要为此定义一些Ord Constr内容）