Simplifying constructor tags in Haskell

Question

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?

Answer 1

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

Answer 2

No, all of the code that you have written is completely necessary. You have pattern matching on all the possible arguments, and you need to reconstruct the result. You can make it cleaner by making good use of the keywords where and let ... in, but that will make it longer.

As it is, you have four lines of code that are guaranteed to work for this problem. Which is much better than most languages are capable of claiming...

---

If you wanted to use a different style of approaching this problem, then you can make it simpler.

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

We'll do that for clarity, and then we can solve the problem like this,

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

This should work, although I haven't tested it out.