function - 在 Haskell 中减少命题的大小

Question

有一个功能简化 , 其中 simplify :: Proposition -> Proposition ， 在哪里

data Proposition =  Const Bool 
                   | Var String
                   | And Proposition Proposition
                   | Or Proposition Proposition
                   | Not Proposition
                   deriving Show

它用于减小给定命题的大小。

例如，

simplify (Const False `And` a) == Const False 
simplify (Const True `And` a)  == a

我的尝试是在这种情况下使用模式匹配:

simplify (Const False `And` a) = Const False
simplify (Const False `Or` a) = Const False
simplify (Const False `Not` a) = Const False
simplify (Const True `And` a) = a
simplify (Const True `Or` a) = a
simplify (Const True `Not` a) = a
simplify prop = prop

但我收到两种类型的错误:

构造函数“Not”应该有 1 个参数，但已经给出了 2

变量不在范围内:a::Proposition

我究竟做错了什么？

Answer 1

在您的方法中有几件事可以改进。

首先，你的函数有一些错误，
正如评论中已经指出的那样，“Not”构造函数只接受一个参数，所以

simplify (Const False `Not` a) = Const False

和

simplify (Const True `Not` a) = a

不管用。
另外还有一些逻辑错误，

simplify (Const False `Or` a) = Const False

和

simplify (Const True `Or` a) = a

不正确。

一旦这些被修复，你的函数应该适本地简化，但只在命题的顶层。为了简化整个命题，您需要向包含变量的每个右侧添加递归调用，并添加当前涵盖的缺失案例

simplify prop = prop

例如你应该改变你的案例

simplify (Const True `And` a) = a

到

simplify (Const True `And` a) = simplify a

并添加案例

simplify (a `And` b) = ((simplify a) `And` (Simplify b))

这样函数就会遍历整个命题并停在第一层。确保您已涵盖所有案例的一种方法是删除

simplify prop = prop

并为每个构造函数做一个案例。
对于变量，你可以写

simplify (Var a) = (Var a)

这将使他们保持原样。

另外，顶层函数应该有类型注解，所以考虑添加

simplify :: Proposition -> Proposition

在你的函数声明之上。

一个小小的挑剔:
在像这样的情况下

simplify (Const False `And` a) = Const False

您不需要绑定(bind) a 而是可以使用通配符，如下所示:

simplify (Const False `And` _) = Const False