2

假设我们有以下数据结构，其值表示某种语言的表达式：

data BExpr = Stop
           | Guard Expr BExpr
           | Choice BExpr BExpr
           | Parallel BExpr BExpr
           | Disable BExpr BExpr
           -- ... and so on.
           | Act Expr


data Expr = Var String | Val Int

我想定义一个函数substBExpr，用它们在 a 中的整数值替换变量名BExpr。这可以按如下方式完成：

subst :: Map String Int -> Expr -> Expr
subst substMap e@(Var name) = maybe e Val $ Map.lookup name substMap
subst _  v@(Val _)          = v

substBExpr :: Map String Int -> BExpr -> BExpr
substBExpr _ Stop                     =  Stop
substBExpr substMap (Guard gExp be)   = Guard gExp' be'
    where gExp' = subst substMap gExp
          be' = substBExpr substMap be
substBExpr substMap (Choice be0 be1)  = Choice be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Parallel be0 be1) = Parallel be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Disable be0 be1) = Disable be0' be1'
    where be0' = substBExpr substMap be0
          be1' = substBExpr substMap be1
substBExpr substMap (Act aExp)        = Act aExp'
    where aExp' = subst substMap aExp

问题是这需要很多样板，我想避免。

我现在可以想到两种解决方案。第一个解决方案是添加一个类型参数，BExpr以便我可以自动Functor为它派生一个实例：

data GBExpr e = GStop
              | GGuard e (GBExpr e)
              | GChoice (GBExpr e) (GBExpr e)
              | GParallel (GBExpr e) (GBExpr e)
              | GDisable (GBExpr e) (GBExpr e)
              -- ... and so on.
              | GAct e
              deriving (Show, Functor)

type BExpr2 = GBExpr Expr

substBExpr2 :: Map String Int -> BExpr2 -> BExpr2
substBExpr2 substMap = (subst substMap <$>)

虽然这可行，但如果Bexpr无法更改以包含类型参数，则它是不可行的。

第二种解决方案是使用gfoldl：

substT :: (Typeable a) => Map String Int -> a -> a
substT substMap = mkT (subst substMap)

substExprs :: (Data a) => Map String Int -> a -> a
substExprs substMap a = runIdentity $ gfoldl step return (substT substMap a)
    where
      step :: Data d => Identity (d -> b) -> d -> Identity b
      step cdb d = cdb <*> pure (substExprs substMap d)

这涉及到它自己的一些样板（但我不知道任何遍历结构的函数，并且只有当它们可以转换为特定类型时才将函数应用于结构内的值）。

对于这个“废弃你的样板”问题，是否有更好的替代方案？（我可以想象它可能是一些涉及镜头的解决方案，但我对光学不太熟悉......）。

4

0 回答 0