在Haskell中通用遍历树的最简单方法

Question

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

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

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

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

1. 有一个everywhere函数，它不适合我的需求，因为我不需要Tree -> Tree转换。
2. gmapQ似乎在类型上很适合，但事实证明它不是递归的。
3. 到目前为止，最可行的选择是everywhereM。它仍然执行无用的转换，但我可以使用Writer收集toConstr结果。不过，这种方式并不真正正确。

有没有一种替代方法可以执行不必要的（对于此任务而言）转换，并仍然提供构造函数列表？（它们在树中出现的顺序现在并不重要）。

- Ilya Chernov

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` ...

这是为了确定我们想要采取构造函数的类型。如果有很多类型，可能可以通过某种方式缩短此代码。

请注意，由于在这种方式中使用 ++ 可能会导致二次复杂度，因此上述代码对于大型树不太有效率。从性能角度考虑，最好返回Data.Map.Map Constr Int。（即使我们确实需要定义一些 Ord Constr ）

- chi

---

谢谢您的回答！我会研究一下，并使用Map代替列表。然而，在您的示例中，B构造函数只有两个字段。在我的情况下，许多构造函数具有不同数量的字段。这种情况有关系吗？ - Ilya Chernov

另外，您可以具体说明一下，您指的是哪个模块的“everything”吗？我尝试了几个，但都没有与您的示例匹配的类型。 - Ilya Chernov

更新：看起来是 Data.Generics.Schemes，对吗？ - Ilya Chernov

@IlyaChernov 正确。 - chi

好的，我已经测试了这种方法，并针对到目前为止所有的用例进行了测试，它完美地工作了。非常感谢！接下来，我将尝试使用 Map 而不是列表，正如你所建议的那样。 - Ilya Chernov

Answer 2

universe函数来自Data.Generics.Uniplate.Data模块，可返回相同类型的所有子树列表。以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]

- soupi

---

当然，这种方法更为简洁。但是在我的语法树中有不同类型的节点，那么它能够工作吗？ - Ilya Chernov

如果我正确理解你的意思，universeBi 可以用来获取不同类型中特定类型的所有值。 - soupi

我认为通过当前的实现更容易演示我想做的事情：https://github.com/ch3rn0v/dry/commit/8f4ea0bcc14087adbc9aa2c2223de437fcb5553b（特别是 countConstructorOccurrences）。 - Ilya Chernov