在 haskell 中遍历树的最简单方法

Question

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

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

有多种方法可以做到这一点。显然模式匹配太冗长了（想象大约 3 种类型和 9-28 个构造函数）。

所以想用泛型遍历，在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` ...

这是确定我们想要获取构造函数的类型所必需的。如果有很多类型，可能可以通过某种方式缩短它。

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

Answer 2

Data.Generics.Uniplate.Data 模块中的

universe 可以为您提供相同类型的所有子树的列表。所以使用 Ilya 的例子：

data T = L | B T T deriving (Data, Show)

tree :: T
tree = B L (B (B L L) L)

λ> import Data.Generics.Uniplate.Data
λ> universe tree
[B L (B (B L L) L),L,B (B L L) L,B L L,L,L,L]
λ> fmap toConstr $ universe tree
[B,L,B,B,L,L,L]

The simplest way to generically traverse a tree in haskell