parsing - 避免具有许多类似构造函数的数据类型的代码重复

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

根据建议 in the comments ，解决您当前问题的方法是将有关运算符类型的信息移出构造函数:

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线;该函数的其余六行是纯样板文件。
如果我们可以将“遍历树”与“句柄 ArgName s”分开定义，那就太好了。这就是泛型编程的用武之地。有很多泛型编程库，每个都有自己的风格和方法，但我将使用 lens 进行演示.
Control.Lens.Plated 模块定义了 Plated 知道如何访问他们的 child 的类型的类。交易是:你显示 lens如何访问您的 child (通过将它们传递给回调 g )和 lens可以递归地应用它来访问 child 的 child 等等。

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

Aside: you might object that even writing plate clause-by-clause is rather too much boilerplate. The compiler should be able to locatethe AST's children for you. lens has your back — there's a defaultimplementation of plate for any type which is an instance ofData,so you should be able to slap deriving Data onto AST and leave thePlated instance empty.

现在我们可以实现 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采用(单子(monad))转换函数并将其应用于 AST 的每个后代。我们的转换函数搜索 ArgName节点并将它们替换为 Arg节点，留下任何非- ArgName s 不变。
更详细的解释见 this paper (或 the accompanying slides，如果您愿意的话)作者是 Neil Mitchell。这就是 Plated模块基于。