haskell - Haskell 中广泛模式匹配的更清晰替代方案

Question

现在，我有一些代码基本上是这样工作的:

data Expression 
    = Literal Bool 
    | Variable String
    | Not Expression 
    | Or Expression Expression 
    | And Expression Expression
    deriving Eq

simplify :: Expression -> Expression
simplify (Literal b) = Literal b
simplify (Variable s) = Variable s
simplify (Not e) = case simplify e of
    (Literal b) -> Literal (not b)
    e'          -> Not e'
simplify (And a b) = case (simplify a, simplify b) of
    (Literal False, _) -> Literal False
    (_, Literal False) -> Literal False
    (a', b')           -> And a' b'
simplify (Or a b) = case (simplify a, simplify b) of
    (Literal True, _) -> Literal True
    (_, Literal True) -> Literal True
    (a', b')          -> Or a' b'

还有更多这样的模式，涉及简化 bool 表达式的所有方式。然而，当我添加更多的运算符和规则时，它会极大地增长并且感觉......笨重。特别是因为一些规则需要添加两次以考虑交换性。

我怎样才能很好地重构很多很多模式，其中一些(我想说大多数)甚至是对称的(例如 And 和 Or 模式)？

现在，添加一条规则来将 And (Variable "x") (Not (Variable "x"))) 简化为 Literal False 需要我添加两个嵌套规则，这几乎是最佳的。

Answer 1

基本上，问题在于您必须一遍又一遍地写出每个子句中子表达式的simplify。最好先完成所有子表达式，然后再考虑涉及顶级运算符的定律。一种简单的方法是添加 simplify 的辅助版本，它不会向下递归:

simplify :: Expression -> Expression
simplify (Literal b) = Literal b
simplify (Variable s) = Variable s
simplify (Not e) = simplify' . Not $ simplify e
simplify (And a b) = simplify' $ And (simplify a) (simplify b)
simplify (Or a b) = simplify' $ Or (simplify a) (simplify b)

simplify' :: Expression -> Expression
simplify' (Not (Literal b)) = Literal $ not b
simplify' (And (Literal False) _) = Literal False
...

由于 bool 值中的运算量很少，这可能是最明智的方法。然而，随着操作的增多，simplify 中的重复可能仍然值得避免。为此，您可以将一元和二元操作合并到一个公共(public)构造函数中:

data Expression 
    = Literal Bool 
    | Variable String
    | BoolPrefix BoolPrefix Expression 
    | BoolInfix BoolInfix Expression Expression 
    deriving Eq

data BoolPrefix = Negation
data BoolInfix  = AndOp | OrOp

然后你就得到了

simplify (Literal b) = Literal b
simplify (Variable s) = Variable s
simplify (BoolPrefix bpf e) = simplify' . BoolPrefix bpf $ simplify e
simplify (BoolInfix bifx a b) = simplify' $ BoolInfix bifx (simplify a) (simplify b)

显然这会让simplify'变得更加尴尬，所以也许不是一个好主意。然而，您可以通过定义专门的 pattern synonyms 来解决这种语法开销。 :

{-# LANGUAGE PatternSynonyms #-}

pattern Not :: Expression -> Expression
pattern Not x = BoolPrefix Negation x

infixr 3 :∧
pattern (:∧) :: Expression -> Expression -> Expression
pattern a:∧b = BoolInfix AndOp a b

infixr 2 :∨
pattern (:∨) :: Expression -> Expression -> Expression
pattern a:∨b = BoolInfix OrOp a b

就此而言，也许也是

pattern F, T :: Expression
pattern F = Literal False
pattern T = Literal True

有了这个，你就可以写了

simplify' :: Expression -> Expression
simplify' (Not (Literal b)) = Literal $ not b
simplify' (F :∧ _) = F
simplify' (_ :∧ F) = F
simplify' (T :∨ _) = T
simplify' (a :∧ Not b) | a==b  = T
...

我应该添加一个警告:when I tried something similar to those pattern synonyms, not for booleans but affine mappings, it made the compiler extremely slow 。 (此外，GHC-7.10 尚不支持多态模式同义词；到目前为止，这已经发生了很大变化。)

<小时/>

另请注意，所有这些通常不会产生最简单的形式 -为此，您需要找到simplify的不动点。