重复使用模式保护或案例表达中的模式

Question

我的Haskell项目包括一个表达式求值程序,为了这个问题的目的可以简化为:

data Expression a where
    I :: Int -> Expression Int
    B :: Bool -> Expression Bool
    Add :: Expression Int  -> Expression Int  -> Expression Int
    Mul :: Expression Int  -> Expression Int  -> Expression Int
    Eq  :: Expression Int  -> Expression Int  -> Expression Bool
    And :: Expression Bool -> Expression Bool -> Expression Bool
    Or  :: Expression Bool -> Expression Bool -> Expression Bool
    If  :: Expression Bool -> Expression a    -> Expression a -> Expression a

-- Reduces an Expression down to the simplest representation.
reduce :: Expression a -> Expression a
-- ... implementation ...

实现此目的的直接方法是编写case表达式以递归计算和模式匹配,如下所示:

reduce (Add x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' + y'
                    (x', y')     -> Add x' y'
reduce (Mul x y) = case (reduce x, reduce y) of
                    (I x', I y') -> I $ x' * y'
                    (x', y')     -> Mul x' y'
reduce (And x y) = case (reduce x, reduce y) of
                    (B x', B y') -> B $ x' && y'
                    (x', y')     -> And x' y'
-- ... and similarly for other cases.

对我来说,这个定义看起来有点尴尬,所以我然后使用模式保护重写了定义,如下所示:

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'

我认为这个定义与case表达式相比看起来更干净,但是当为不同的构造函数定义多个模式时,模式会重复多次.

reduce (Add x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' + y'
reduce (Mul x y) | I x' <- reduce x
                 , I y' <- reduce y
                 = I $ x' * y'

注意到这些重复的模式,我希望有一些语法或结构可以减少模式匹配中的重复.是否有一种普遍接受的方法来简化这些定义？

编辑:在审查模式保护后,我意识到他们不能在这里作为替代品.虽然他们提供相同的结果时x,并y可以降低到I _,他们不减少任何值时,该模式卫兵不匹配.我仍然想reduce简化Add等人的子表达式.

Answer 1

我在类似情况下使用的一个部分解决方案是将逻辑提取到"提升"函数中,该函数采用正常的Haskell操作并将其应用于您的语言值.这包括了包装/解包和导致的错误处理.

我们的想法是创建两个类型类,以便进出自定义类型,并进行适当的错误处理.然后你可以使用它们来创建一个如下所示的liftOp函数:

liftOp :: (Extract a, Extract b, Pack c) => (a -> b -> c) -> 
            (Expression a -> Expression b -> Expression c)
liftOp err op a b = case res of
  Nothing  -> err a' b'
  Just res -> pack res
  where res = do a' <- extract $ reduce' a
                 b' <- extract $ reduce' b
                 return $ a' `op` b'

然后每个特定的案例看起来像这样:

Mul x y -> liftOp Mul (*) x y

这不是太糟糕:它不是过分冗余.它包含重要的信息:Mul映射到*,并且在错误情况下我们Mul再次应用.

您还需要打包和解包的实例,但无论如何这些都很有用.一个巧妙的技巧是,这些也可以让你自动使用表格实例在你的DSL中嵌入功能(Extract a, Pack b) => Pack (a -> b).

我不确定这是否适用于你的例子,但我希望它能给你一个很好的起点.您可能需要额外的接线错误在整个事情的处理,但好消息是,大部分是被折叠成的定义pack,unpack和liftOp,所以它仍然是相当集中.

我为相关(但有些不同)的问题编写了类似的解决方案.它也是一种处理本机Haskell值和解释器之间来回的方法,但解释器的结构不同.尽管如此,一些相同的想法仍然适用!