[Haskell-cafe] Disjunctive Normal Form

Luke Palmer lrpalmer at gmail.com
Thu Nov 1 20:15:18 EDT 2007


On 11/2/07, Luke Palmer <lrpalmer at gmail.com> wrote:
> On 11/1/07, Arnar Birgisson <arnarbi at gmail.com> wrote:
> > 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))

I should clarify.  I meant that *you* were doing a little extra work,
by re-implementing that logic for the not cases.  I'm a fan of only
implementing each "unit" of logic in one place, whatever that means.

But to appease the pedantic, my versions are actually doing more
computational work: they are doing one extra pattern match when these
patterns are encountered.  Whoopty-doo.  :-)

Luke


More information about the Haskell-Cafe mailing list