I'm a total n00b at Haskell and I'm trying to write a simple SAT solver using DPLL.
I have a function expand that takes a schema from (A1 and A2 ...) Or (B1 and B2 ...) to conjunctive normal form: (A1 or B1) and (A1 or B2) and ... (A2 or B2) and ....
I've represented my expression data type as follows
type Term = Int
data Expr = Or Expr Expr | And Expr Expr | Literal Term
(I don't care about negation since I can represent Not(x) with -x)
But now, writing expand, this comes out really ugly looking with the constructor tags.
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))
Can I make this code any cleaner?
You can use as patterns on your Literal cases to remove some redundancy. For example, the first case could be written as
expnd l@(Literal _) r@(Literal _) = Or l r