自动将函数应用于子结构

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个部分,然后明确地重建对3个部分中的每个部分的If应用go.对于Let,我必须模式匹配,命名3个部分,并重新明确Let应用于go相关的2个部分.是否有一种更容易(无点？)的方式来写这个而不必详细说明每一个细节？

Answer 1

这里最好的方法是使用数据类型通用编程,这是为这样的AST行走任务精确设计的.这是一个使用标准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,只要基本递归方案保持不变即可.