2

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

AST 本身是不平凡的，这意味着它具有仅限于某些类型的子表达式。（例如，运算符A必须采用B仅类型的参数，而不是 any 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

我的目标是排除显式递归并改为依赖递归方案，正如这 两篇优秀的博客文章所展示的那样，它们提供了非常强大的通用工具来操作我的 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变得相当乏味，因为我必须在 for 内部进行模式匹配才能B a :: StrF a进行良好的类型化。对于整个原始 AST，这是不可行的。Str :: ExprF acata

我偶然发现了修复 GADTs，在我看来这似乎是解决我的问题的方法，但是重复的高阶类型类等用户不友好的界面是相当不必要的样板。

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

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

1 回答 1

2

如果您已经努力分离出数据类型中的递归，那么您只需派生即可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 类型），您可以将所有这些参数打包到一个记录中，然后您可以使用记录更新来更新在各种情况下提供“默认”行为的“预制”记录. 有一篇旧论文处理大香蕉采用了这样的方法。我的建议是明确的，只是包装gfold上面的函数带有一个接受记录的函数，并传入一个代数，该代数将进行案例分析并为每个案例调用记录的适当字段。

当然，您可以使用 GHC Generics 或各种“通用/多类型”编程库，例如 Scrap Your Boilerplate，而不是这个。您基本上是在重新创建他们所做的事情。

于 2017-05-10T00:28:41.617 回答