haskell - 自动将功能应用于子结构

Question

假设我正在抽象语法树数据类型上编写“替代”函数:

data Term = Id String
          | If Term Term Term
          | Let String Term Term
          ...

subst :: String -- name of identifier to replace
      -> Term   -- term to replace the identifier with
      -> Term   -- body in which to perform the replacements
      -> Term
subst identifier term = go
  where go (Id id') = if identifier == id' then term else Id id'
        go (If t1 t2 t3) = If (go t1) (go t2) (go t3)
        go (Let id' term' body) = Let id' (go term') (go body)
        ...

(忽略阴影问题)。注意写 If 是多么乏味。分支。我必须进行模式匹配，命名 3 个部分，然后重构 If申请 go明确地对这三个部分中的每一个。对于 Let ，我必须进行模式匹配，命名这 3 个部分，并重构一个 Let申请 go明确的相关2部分。有没有更简单的(pointfree？)方法来写这个而不必拼出每个细节？

Answer 1

这里最好的方法是使用数据类型泛型编程，它专为像这样的 AST-walking 任务而设计。这是一个示例，使用标准 SYB图书馆:

{-# LANGUAGE DeriveDataTypeable #-}

import Data.Generics

data Term = Id String
          | If Term Term Term
          | Let String Term Term
          deriving (Eq, Show, Typeable, Data)

subst :: String -- name of identifier to replace
      -> Term   -- term to replace the identifier with
      -> Term   -- body in which to perform the replacements
      -> Term
subst identifier term = everywhere (mkT go)
  where go (Id id') = if identifier == id' then term else Id id'
        go x = x

这直接表示转换(在这种情况下，将函数 go 应用于 Term 类型的任何子级)应该以自下而上的方式应用于整个树。这不仅更加简洁，而且无论向 Term 添加多少结构，相同的代码都将继续工作。 ，只要基本递归方案保持不变。