1

我是 Haskell 的一名普通人，我正在尝试使用 DPLL 编写一个简单的 SAT 求解器。

我有一个函数 expand ，它采用从模式(A1 and A2 ...) Or (B1 and B2 ...)到合取范式：(A1 or B1) and (A1 or B2) and ... (A2 or B2) and ....

我已经将我的表达式数据类型表示如下

type Term = Int
data Expr = Or Expr Expr | And Expr Expr | Literal Term

（我不关心否定，因为我可以用 -x 表示 Not(x)）

但是现在，写扩展，构造函数标签看起来真的很难看。

expnd (Literal l) (Literal r) = Or (Literal l) (Literal r)
expnd (Literal t) (And l r) = And (expnd (Literal t) l) (expnd (Literal t) r)
expnd (And l r) (Literal t) = And (expnd l (Literal t)) (expnd r (Literal t))
expnd (And l1 r1) (And l2 r2) = 
   And (And (expnd l1 l2) (expnd l1 r2)) (And (expnd r1 l2) (expnd r1 r2))

我可以让这段代码更干净吗？

4

2 回答 2

2

您可以在案例as上使用模式Literal来消除一些冗余。例如，第一种情况可以写成

expnd l@(Literal _) r@(Literal _) = Or l r
于 2014-01-18T04:01:24.693 回答
1

不，您编写的所有代码都是完全必要的。您对所有可能的参数都有模式匹配，您需要重建结果。您可以通过充分利用关键字whereand来使其更简洁let ... in，但这会使其更长。

实际上，您有四行代码保证可以解决这个问题。这比大多数语言能够声称的要好得多......

如果你想用不同的方式来解决这个问题，那么你可以让它更简单。

type Or a = [a]
type And a = [a]

为了清楚起见，我们会这样做，然后我们可以像这样解决问题，

expand :: Or (And a) -> And (Or a)
expand []     = []
expand (x:xs) = zipWith (:) x (expand xs)

这应该可以工作，虽然我还没有测试过。

于 2014-01-18T03:56:40.043 回答