[Haskell-cafe] Disjunctive Normal Form

[Luke Palmer]

On 11/1/07, Arnar Birgisson <arnarbi at gmail.com> wrote:
> I'm learning too and found this an interesting problem. Luke, is this
> similar to what you meant?

Heh, your program is almost identical to the one I wrote to make sure
I wasn't on crack.  :-)

> data LS = Var String | Not LS | And LS LS | Or LS LS deriving Show
>
> data Term = Pos String | Neg String deriving Show
> type Conj = [Term]
> type DNF = [Conj]
>
> dnf :: LS -> DNF
> dnf (Var s) = [[Pos s]]
> dnf (Or l1 l2) = (dnf l1) ++ (dnf l2)
> dnf (And l1 l2) = [t1 ++ t2 | t1 <- dnf l1, t2 <- dnf l2]
> dnf (Not (Not d)) = dnf d
> dnf (Not (And l1 l2)) = (dnf $ Not l1) ++ (dnf $ Not l2)
> dnf (Not (Or l1 l2)) = [t1 ++ t2 | t1 <- dnf $ Not l1, t2 <- dnf $ Not l2]

These two are doing a little extra work:

dnf (Not (And l1 l2)) = dnf (Or (Not l1) (Not l2))
dnf (Not (Or l1 l2))  = dnf (And (Not l1) (Not l2))

> dnf (Not (Var s)) = [[Neg s]]
>
> -- test cases
> x = (Or (And (Var "A") (Var "B")) (Or (And (Not $ Var "C") (Var "D"))
> (Var "E")))
> y = (Not (And (Var "A") (Var "B")))
> z = (Not (And (Not y) y))

Luke