时间戳

首页 > 解决方案 > 在haskell中一般遍历树的最简单方法

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

问题描述

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

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

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

所以我想使用通用遍历，我试图在 SYB 库中找到解决方案。

  1. 有一个everywhere功能不适合我的需求，因为我不需要Tree -> Tree转换。
  2. 有gmapQ, 就其类型而言似乎很合适，但事实证明它不是递归的。
  3. 迄今为止最可行的选择是everywhereM. 它仍然进行无用的转换，但我可以使用 Writer 来收集toConstr结果。不过，这种方式确实感觉不对。

是否有替代方案不会执行无用的（对于此任务）转换并仍提供构造函数列表？（现在它们在树中出现的顺序无关紧要）

标签： haskellgenericsabstract-syntax-treetree-traversal

解决方案

不确定它是否是最简单的，但是：

> 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 []是不属于 type 的子项的基本情况T。相反，对于那些 type T，我们应用\x -> [toConstr (x::T)]。

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

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

这对于识别我们想要为其采用构造函数的类型是必需的。如果有很多类型，可能可以通过某种方式缩短它。

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

推荐阅读