在模式保护或大小写表达式中重用模式

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值和解释器之间来回转换的方法，但是解释器的结构不同。一些相同的想法应该仍然适用!

Answer 2

这个答案的灵感来自于rampion的后续问题，它提出了以下功能:

step :: Expression a -> Expression a
step x = case x of
  Add (I x) (I y) -> I $ x + y
  Mul (I x) (I y) -> I $ x * y
  Eq  (I x) (I y) -> B $ x == y
  And (B x) (B y) -> B $ x && y
  Or  (B x) (B y) -> B $ x || y
  If  (B b) x y   -> if b then x else y
  z               -> z

step查看单个项，如果所有需要减少它的东西都存在，则减少它。有了step，我们只需要一种方法来替换表达式树中的任何地方的术语。我们可以从定义一种在每个项中应用函数的方法开始。

{-# LANGUAGE RankNTypes #-}
emap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
emap f x = case x of
    I a -> I a
    B a -> B a
    Add x y   -> Add (f x) (f y)
    Mul x y   -> Mul (f x) (f y)
    Eq  x y   -> Eq  (f x) (f y)
    And x y   -> And (f x) (f y)
    Or  x y   -> Or  (f x) (f y)
    If  x y z -> If  (f x) (f y) (f z)

现在，我们需要在所有地方应用一个函数，包括项和项内的所有地方。有两种基本的可能性，我们可以在将函数应用于项之前将其应用于项，也可以在此之后应用该函数。

premap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
premap f = emap (premap f) . f
postmap :: (forall a. Expression a -> Expression a) -> Expression x -> Expression x
postmap f = f . emap (postmap f)

这给了我们如何使用step的两种可能性，我将其称为shorten和reduce。

shorten = premap step
reduce = postmap step

它们的行为有点不同。shorten删除最内层的术语，用字面量替换它们，将表达式树的高度缩短1。reduce将表达式树完全求值为字面量。下面是在相同的输入

上对它们进行迭代的结果

"shorten"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
If (And (B True) (B True)) (Add (I 1) (I 6)) (I 0)
If (B True) (I 7) (I 0)
I 7
"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul (I 2) (I 3))) (I 0)
I 7

部分减少

你的问题暗示你有时期望表达式不能完全约简。我将扩展您的示例，通过添加一个变量Var来演示这种情况。

data Expression a where
    Var :: Expression Int
    ...

我们需要将Var的支持添加到emap:

emap f x = case x of
   Var -> Var
   ...

bind将替换变量，evaluateFor执行一次完整的求值，只遍历表达式一次。

bind :: Int -> Expression a -> Expression a
bind a x = case x of
    Var -> I a
    z   -> z
evaluateFor :: Int -> Expression a -> Expression a
evaluateFor a = postmap (step . bind a)

现在，reduce在包含变量的示例上迭代产生以下输出

"reduce"
If (And (B True) (Or (B False) (B True))) (Add (I 1) (Mul Var (I 3))) (I 0)
Add (I 1) (Mul Var (I 3))

如果对Var的一个特定值求值，则可以将该表达式一直约简为一个文字。

"evaluateFor 5"
Add (I 1) (Mul Var (I 3))
I 16

应用

emap可以写成Applicative Functor，而postmap可以写成一段适合于表达式以外的其他数据类型的通用代码。如何做到这一点将在对rampion的后续问题的回答中描述。