11

我的 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等人的子表达式。

4

2 回答 2

8

我在类似情况下使用的一个部分解决方案是将逻辑提取到“提升”函数中，该函数采用正常的 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因此它仍然非常集中。unpackliftOp

我为一个相关（但有些不同）的问题写了一个类似的解决方案。这也是一种处理原生 Haskell 值和解释器之间来回切换的方法，但解释器的结构不同。一些相同的想法仍然应该适用！

于 2014-08-14T18:08:29.483 回答
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删除最内层的术语，用文字替换它们，将表达式树的高度缩短一。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
    ...

我们需要添加对Varto的支持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 的后续问题的回答中进行了描述。

于 2014-08-18T19:13:08.967 回答