Haskell中更广泛的模式匹配的更干净的选择 [英] Cleaner Alternative to Extensive Pattern Matching in Haskell

问题描述

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

Right now, I have some code that essentially works like this:

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 many more such patterns regarding all the ways one can simplify a boolean expression. As I add more operators and rules however, this grows immensely and feels.. clunky. Especially so since some rules need to be added twice to account for commutativity.

我该如何很好地重构很多甚至是对称的模式(例如，And和Or模式)?

How can I nicely refactor lots and lots of patterns of which some (most, I'd say) are even symmetrical (take the And and Or patterns for example)?

现在，添加一条将And (Variable "x") (Not (Variable "x"))简化为Literal False的规则要求我添加两个嵌套的规则，这些规则几乎都是最优的.

Right now, adding a rule to simplify And (Variable "x") (Not (Variable "x")) to Literal False requires me to add two nested rules, which is all but optimal.

推荐答案

您可以做的一件事就是在构造时简化操作，而不是先构造然后反复破坏.所以:

One thing you can do is simplify as you construct, rather than first constructing then repeatedly destructing. So:

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中试用:

We can try it out in ghci:

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

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

Note that the constructors are not exported: this ensures that folks constructing one of these can't avoid the simplification process. Actually, this may be a drawback; occasionally it is nice to see the "full" form. A standard approach to dealing with this is to make the exported smart constructors part of a type-class; you can either use them to build a "full" form or a "simplified" way. To avoid having to define the type twice, we could either use a newtype or a phantom parameter; I'll elect for the latter here to reduce the noise in pattern-matching.

{-# 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中，我们可以通过两种不同的方式运行"相同的术语:

Now in ghci we can "run" the same term in two different ways:

> :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

您以后可能想添加更多规则；例如，也许您想要:

You might want to add more rules later; for example, maybe you want:

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

必须重复模式的两个顺序"有点烦人.我们应该对此进行抽象！数据声明和类将相同，但是我们将添加辅助函数eitherOrder并将其用于and和or的定义中.这是使用此想法的更完整的简化集(以及该模块的最终版本):

Having to repeat both "orders" of patterns is a bit annoying. We should abstract over that! The data declaration and classes will be the same, but we'll add the helper function eitherOrder and use it in the definitions of and and or. Here's a more complete set of simplifications using this idea (and our final version of the module):

{-# 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中，我们可以进行更复杂的简化，例如:

Now in ghci we can do more complicated simplifications, like:

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

即使我们只写了一个重写规则命令，但两个命令都可以正常工作:

And even though we only wrote one order of the rewrite rule, both orders work properly:

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

这篇关于Haskell中更广泛的模式匹配的更干净的选择的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！