哈斯克尔中广泛模式匹配的更清洁的替代方案

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'

还有更多这样的模式，关于简化布尔表达式的所有方法。然而，随着我添加更多的运算符和规则，这极大地增长并感觉......笨重。特别是因为有些规则需要添加两次以考虑交换性。

我怎样才能很好地重构很多很多模式，其中一些(我会说大多数)甚至是对称的(以 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
...

对于布尔值中仅有的少量操作，这可能是最明智的方法。但是，随着操作的增加，simplify中的重复可能仍然值得避免。为此，您可以将一元和二进制操作合并到一个公共构造函数中：

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'更加尴尬，所以也许不是一个好主意。但是，您可以通过定义专门的模式同义词来绕过此语法开销：

{-# 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
...

不过，我应该补充一个警告：当我尝试类似于这些模式同义词的东西时，不是布尔值而是仿射映射，它使编译器非常慢。(此外，GHC-7.10 还不支持多态模式同义词;到目前为止，这已经发生了很大变化。

---

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

Answer 2

您可以做的一件事是在构造时简化，而不是先构造然后反复破坏。所以：

module Simple (Expression, true, false, var, not, or, and) where
import Prelude hiding (not, or, and)
data Expression
= Literal Bool
| Variable String
| Not Expression
| Or Expression Expression
| And Expression Expression
deriving (Eq, Ord, Read, Show)
true = Literal True
false = Literal False
var = Variable
not (Literal True) = false
not (Literal False) = true
not x = Not x
or (Literal True) _ = true
or _ (Literal True) = true
or x y = Or x y
and (Literal False) _ = false
and _ (Literal False) = false
and x y = And x y

我们可以在ghci中尝试一下：

> and (var "x") (and (var "y") false)
Literal False

请注意，构造函数不会导出：这可确保构造其中一个构造函数的人无法避免简化过程。实际上，这可能是一个缺点;偶尔很高兴看到"完整"的形式。处理此问题的标准方法是使导出的智能构造函数成为类型类的一部分;您可以使用它们来构建"完整"表单或"简化"方式。为了避免必须定义类型两次，我们可以使用 newtype 或 phantom 参数;我将在这里选择后者以减少模式匹配中的噪音。

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE KindSignatures #-}
module Simple (Format(..), true, false, var, not, or, and) where
import Prelude hiding (not, or, and)
data Format = Explicit | Simplified
data Expression (a :: Format)
= Literal Bool
| Variable String
| Not (Expression a)
| Or (Expression a) (Expression a)
| And (Expression a) (Expression a)
deriving (Eq, Ord, Read, Show)
class Expr e where
true, false :: e
var :: String -> e
not :: e -> e
or, and :: e -> e -> e
instance Expr (Expression Explicit) where
true = Literal True
false = Literal False
var = Variable
not = Not
or = Or
and = And
instance Expr (Expression Simplified) where
true = Literal True
false = Literal False
var = Variable
not (Literal True) = false
not (Literal False) = true
not x = Not x
or (Literal True) _ = true
or _ (Literal True) = true
or x y = Or x y
and (Literal False) _ = false
and _ (Literal False) = false
and x y = And x y

现在在ghci中，我们可以通过两种不同的方式"运行"相同的术语：

> :set -XDataKinds
> and (var "x") (and (var "y") false) :: Expression Explicit
And (Variable "x") (And (Variable "y") (Literal False))
> and (var "x") (and (var "y") false) :: Expression Simplified
Literal False

您可能希望稍后添加更多规则;例如，您可能希望：

and (Variable x) (Not (Variable y)) | x == y = false
and (Not (Variable x)) (Variable y) | x == y = false

不得不重复模式的两个"顺序"有点烦人。我们应该抽象出来！数据声明和类将是相同的，但我们将在eitherOrder添加帮助程序函数，并在and和or的定义中使用它。以下是使用此想法(以及该模块的最终版本)的一组更完整的简化：

{-# LANGUAGE DataKinds #-}
{-# LANGUAGE FlexibleContexts #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE KindSignatures #-}
module Simple (Format(..), true, false, var, not, or, and) where
import Data.Maybe
import Data.Monoid
import Prelude hiding (not, or, and)
import Control.Applicative ((<|>))
data Format = Explicit | Simplified
data Expression (a :: Format)
= Literal Bool
| Variable String
| Not (Expression a)
| Or (Expression a) (Expression a)
| And (Expression a) (Expression a)
deriving (Eq, Ord, Read, Show)
class Expr e where
true, false :: e
var :: String -> e
not :: e -> e
or, and :: e -> e -> e
instance Expr (Expression Explicit) where
true = Literal True
false = Literal False
var = Variable
not = Not
or = Or
and = And
eitherOrder :: (e -> e -> e)
-> (e -> e -> Maybe e)
-> e -> e -> e
eitherOrder fExplicit fSimplified x y = fromMaybe
(fExplicit x y)
(fSimplified x y <|> fSimplified y x)
instance Expr (Expression Simplified) where
true = Literal True
false = Literal False
var = Variable
not (Literal True) = false
not (Literal False) = true
not (Not x) = x
not x = Not x
or = eitherOrder Or go where
go (Literal True) _ = Just true
go (Literal False) x = Just x
go (Variable x) (Variable y) | x == y = Just (var x)
go (Variable x) (Not (Variable y)) | x == y = Just true
go _ _ = Nothing
and = eitherOrder And go where
go (Literal True) x = Just x
go (Literal False) _ = Just false
go (Variable x) (Variable y) | x == y = Just (var x)
go (Variable x) (Not (Variable y)) | x == y = Just false
go _ _ = Nothing

现在在ghci中，我们可以做更复杂的简化，比如：

> and (not (not (var "x"))) (var "x") :: Expression Simplified
Variable "x"

即使我们只编写了重写规则的一个顺序，两个顺序都可以正常工作：

> and (not (var "x")) (var "x") :: Expression Simplified
Literal False
> and (var "x") (not (var "x")) :: Expression Simplified
Literal False

Answer 3

我想爱因斯坦说过，"尽可能简化，但不要再简单了。你自己有一个复杂的数据类型，以及一个相应的复杂概念，所以我认为任何技术对于手头的问题来说都只能更清晰。

也就是说，第一种选择是改用案例结构。

simplify x = case x of
Literal _  -> x
Variable _ -> x
Not e      -> simplifyNot $ simplify e
...
where
sharedFunc1 = ...
sharedFunc2 = ...

这还有一个额外的好处，即包含共享函数，这些函数在所有情况下都可以使用，但不能在顶级命名空间中使用。我也喜欢这些案例如何摆脱括号。(另请注意，在前两种情况下，我只返回原始术语，而不是创建新术语)。我经常使用这种结构来分解其他简化函数，例如Not。

这个问题尤其可能适合基于基础函子Expression，以便您可以fmap子表达式的简化，然后执行给定情况的特定组合。它将如下所示：

simplify :: Expression' -> Expression'
simplify = Exp . reduce . fmap simplify . unExp

其中的步骤是将Expression'解包到底层函子表示中，将简化映射到基础项上，然后减少简化并包装回新Expression'

{-# Language DeriveFunctor #-}
newtype Expression' = Exp { unExp :: ExpressionF Expression' }
data ExpressionF e
= Literal Bool 
| Variable String
| Not e 
| Or e e
| And e e
deriving (Eq,Functor)

现在，我已经将复杂性推到了reduce函数中，它只是稍微不那么复杂，因为它不必担心首先减少子项。但它现在将仅包含将一个术语与另一个术语组合的业务逻辑。

这对您来说可能是一个好技术，也可能不是一个好技术，但它可能会使一些增强更容易。例如，如果可以在您的语言中形成无效表达式，则可以使用Maybe有价值的失败来简化它。

simplifyMb :: Expression' -> Maybe Expression'
simplifyMb = fmap Exp . reduceMb <=< traverse simplifyMb . unExp

在这里，traverse将simplfyMb应用于ExpressionF的子项，得到Maybe子项ExpressionF (Maybe Expression')的表达式，然后如果Nothing任何子项，它将返回Nothing，如果全部Just x，它将返回Just (e::ExpressionF Expression')。遍历实际上并没有像这样分成不同的阶段，但它更容易解释，就好像它是这样。另请注意，您将需要 DeriveTraversable 和 DeriveFoldable 的语言编译指示，以及派生ExpressionF数据类型的语句。

缺点？好吧，首先，代码的污垢将存在于无处不在的一堆Exp包装器中。考虑以下简单术语simplfyMb的应用：

simplifyMb (Exp $ Not (Exp $ Literal True))

了解这一点也很多，但是如果您了解上面的traverse和fmap模式，则可以在很多地方重用它，所以这很好。我还相信以这种方式定义简化可以使其对特定ExpressionF结构可能变成的任何内容更加健壮。它没有提到它们，因此深度简化不会受到重构的影响。另一方面，reduce功能将是。

Answer 4

继续你的Binary Op Expression Expression想法，我们可以得到数据类型：

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

和辅助功能

{-# LANGUAGE ViewPatterns #-}
simplifyBinary  :: Op -> Expression -> Expression -> Expression
simplifyBinary  binop (simplify -> leftexp) (simplify -> rightexp) =
case oneway binop leftexp rightexp ++ oneway binop rightexp leftexp of
simplified : _ -> simplified
[]             -> Binary binop leftexp rightexp
where
oneway :: Op -> Expression -> Expression -> [Expression]
oneway And (Literal False) _ = [Literal False]
oneway Or  (Literal True)  _ = [Literal True]
-- more cases here
oneway _   _               _ = []

这个想法是，您将简化案例放在oneway中，然后simplifyBinary负责反转参数，以避免编写对称案例。

Answer 5

您可以为所有二进制操作编写一个通用简化器：

simplifyBinWith :: (Bool -> Bool -> Bool) -- the boolean operation
-> (Expression -> Expression -> Expression) -- the constructor
-> Expression -> Expression -- the two operands
-> Expression) -- the simplified result
simplifyBinWith op cons a b = case (simplify a, simplify b) of
(Literal x, Literal y) -> Literal (op x y)
(Literal x, b')        -> tryAll (x `op`) b'
(a',        Literal y) -> tryAll (`op` y) a'
(a',        b')        -> cons a' b'
where
tryAll f term = case (f True, f False) of -- what would f do if term was true of false
(True,  True)  -> Literal True
(True,  False) -> term
(False, True)  -> Not term
(False, False) -> Literal False

这样，您的simplify函数将变为

simplify :: Expression -> Expression
simplify (Not e)   = case simplify e of
(Literal b) -> Literal (not b)
e'          -> Not e'
simplify (And a b) = simplifyBinWith (&&) And a b
simplify (Or a b)  = simplifyBinWith (||) Or a b
simplify t         = t

并且可以轻松扩展到更多的二进制操作。它也适用于Binary Op Expression Expression的想法，您将传递Op而不是Expression构造函数来simplifyBinWith并且simplify中的模式可以推广：

simplify :: Expression -> Expression
simplify (Not e)         = case simplify e of
(Literal b) -> Literal (not b)
e'          -> Not e'
simplify (Binary op a b) = simplifyBinWith (case op of
And -> (&&)
Or -> (||)
Xor -> (/=)
Implies -> (<=)
Equals -> (==)
…
) op a b
simplify t               = t
where
simplifyBinWith f op a b = case (simplify a, simplify b) of
(Literal x, Literal y) -> Literal (f x y)
…
(a',        b')        -> Binary op a' b'