在复杂的 AST 中分解递归

Question

对于我正在从事的一个业余项目，我目前必须处理一个抽象语法树并根据规则对其进行转换（具体细节不重要）。

AST 本身是重要的，这意味着它具有仅限于某些类型的子表达式。（例如，运算符 A 必须仅采用 B 类型的参数，而不是任何 Expr 类型的参数。我的数据类型的大幅简化版本如下所示：

data Expr  = List [Expr]
           | Strange Str
           | Literal Lit
data Str   = A Expr
           | B Expr
           | C Lit
           | D String
           | E [Expr]
data Lit   = Int Int
           | String String

我的目标是分解显式递归并改为依赖递归方案，如 these two 优秀博客文章中所示，它们提供了非常强大的通用工具来操作我的 AST。应用必要的因式分解，我们最终得到：

data ExprF a = List [a]
             | Strange (StrF a)
             | Literal (LitF a)
data StrF a  = A a
             | B a
             | C (LitF a)
             | D String
             | E [a]
data LitF a  = Int Int
             | String String

如果我没有搞砸，type Expr = Fix ExprF 现在应该与之前定义的 Expr.

同构

然而，为这些情况编写 cata 变得相当乏味，因为我必须在 Str :: ExprF a 中模式匹配 B a :: StrF a 以使 cata 类型正确.对于整个原始 AST，这是不可行的。

我偶然发现了 fixing GADTs，在我看来它是解决我的问题的方法，但是重复的高阶类型类等用户不友好的界面非常好不必要的样板文件。

所以，总结一下我的问题：

将 AST 重写为 GADT 是解决此问题的正确方法吗？
如果是，我如何将示例转换为运行良好的版本？其次，现在 GHC 中是否有更好的对更高种类 Functor 的支持？

Answer 1

如果您已经完成了在数据类型中分离出递归的工作，那么您只需导出 Functor 就可以了。您不需要任何花哨的功能来获得递归方案。（附带说明，没有理由参数化 Lit 数据类型。）

弃牌是：

newtype Fix f = In { out :: f (Fix f) }

gfold :: (Functor f) => (f a -> a) -> Fix f -> a
gfold alg = alg . fmap (gfold alg) . out

要指定代数（alg 参数），您需要针对 ExprF 进行案例分析，但另一种方法是让折叠有十几个或更多参数：一个对于每个数据构造函数。这不会真正为您节省很多打字时间，而且会更难阅读。如果你愿意（这通常可能需要 rank-2 类型），你可以将所有这些参数打包到一个记录中，然后你可以使用记录更新来更新 "pre-made" 提供 "default" 行为的记录各种情况。有一篇旧论文 Dealing with Large Bananas 采用了这样的方法。需要明确的是，我的建议只是将上面的 gfold 函数用一个获取记录的函数包装起来，并传入一个代数，该代数将进行案例分析并为每个调用记录的适当字段案例.

当然，您可以使用 GHC Generics 或 the various "generic/polytypic" programming libraries 之类的 Scrap Your Boilerplate 而不是这个。你基本上是在重现他们所做的事情。

在复杂的 AST 中分解递归

Factoring out recursion in a complex AST

haskell

abstract-syntax-tree

recursion-schemes