避免具有大量相似构造函数的数据类型的代码重复

Question

我正在用 Haskell 编写一个简单的解析器，并使用这种保存解析结果的数据类型。

data AST = Imm Integer
    | ArgName String
    | Arg Integer
    | Add AST AST
    | Sub AST AST
    | Mul AST AST
    | Div AST AST
    deriving (Show, Eq)

当我想在树上映射以使用映射用其引用号替换变量名称时，问题就出现了。我必须写这段代码

refVars :: M.Map String Integer -> AST -> Maybe AST
refVars d (ArgName s) = case d M.!? s of
                            Just n -> Just (Arg n)
                            Nothing -> Nothing
refVars _ (Imm n)     = Just $ Imm n
refVars _ (Arg n)     = Just $ Arg n                       
refVars d (Add a1 a2) = Add <$> refVars d a1 <*> refVars d a2
refVars d (Sub a1 a2) = Sub <$> refVars d a1 <*> refVars d a2
refVars d (Mul a1 a2) = Mul <$> refVars d a1 <*> refVars d a2
refVars d (Div a1 a2) = Div <$> refVars d a1 <*> refVars d a2

这似乎非常多余。理想情况下，我希望有一种模式可以匹配任何模式（op a1 a2），但 Haskell 不允许这样做。有什么建议？

Answer 1

正如评论中所建议的，解决您当前问题的方法是将有关运算符类型的信息移出构造函数：

data Op = Add | Sub | Mul | Div
data AST = Imm Integer
    | ArgName String
    | Arg Integer
    | Op Op AST AST

这个数据类型有一个用于所有二元运算的构造函数，所以你只需要一行代码就可以把它拆开：

refVars :: M.Map String Integer -> AST -> Maybe AST
refVars d (ArgName s)   = Arg <$> d !? s
refVars _ (Imm n)       = Just $ Imm n
refVars _ (Arg n)       = Just $ Arg n                       
refVars d (Op op a1 a2) = Op op <$> refVars d a1 <*> refVars d a2

您可以处理所有不同类型的二元运算，而无需修改refVars，但如果添加不同的语法形式的AST，你必须的条款增加refVars。

data AST = -- other constructors as before
    | Ternary AST AST AST
    | List [AST]
    | Call AST [AST]  -- function and args

refVars -- other clauses as before
refVars d (Ternary cond tt ff) = Ternary <$> refVars d cond <*> refVars d tt <*> refVars d ff
refVars d (List l) = List <$> traverse (refVars d) l
refVars d (Call f args) = Call <$> refVars d f <*> traverse (refVars d) args

所以它仍然很乏味——所有这些代码所做的就是遍历树到叶子，然后refVars可以检查叶子是否是一个ArgName。有趣的部分refVars是ArgName一行；该函数的其余六行是纯样板文件。

如果我们可以将“遍历树”与“句柄ArgNames”分开定义，那就太好了。这就是泛型编程的用武之地。有很多泛型编程库，每个库都有自己的风格和方法，但我将演示使用lens.

该Control.Lens.Plated模块Plated为知道如何访问其子项的类型定义了一个类。交易是：您展示lens如何访问您的孩子（通过将他们传递给回调g），并且lens可以递归地应用它来访问孩子的孩子等等。

instance Plated AST where
    plate g (Op op a1 a2) = Op op <$> g a1 <*> g a2
    plate g (Ternary cond tt ff) = Ternary <$> g cond <*> g tt <*> g ff
    plate g (List l) = List <$> traverse g l
    plate g (Call f args) = Call <$> g f <*> traverse g args
    plate _ a = pure a

旁白：您可能会反对，即使逐句编写plate也过于样板。编译器应该能够AST为您找到的孩子。lens有你的背部-有一个默认的实现plate对任何类型的这是一个实例 Data，所以你应该能够拍deriving Data上AST，离开 Plated实例空。

现在我们可以refVars使用transformM :: (Monad m, Plated a) => (a -> m a) -> a -> m a.

refVars :: M.Map String Integer -> AST -> Maybe AST
refVars d = transformM $ \case
    ArgName s -> Arg <$> d !? s
    x -> Just x

transformM采用（monadic）转换函数并将其应用于 AST 的每个后代。我们的转换函数搜索ArgName节点并用节点替换它们Arg，保持任何 non- ArgNames 不变。

有关更详细的解释，请参阅Neil Mitchell 的这篇论文（或随附的幻灯片，如果您愿意）。这是该Plated模块的基础。