hello,
below is the
code that i wrote as an excercise for myself (I am still learning
haskell).
it
implements a straighforward way to simplify boolean expressions, and should be
self-explanatory.
my question
is, if i have an expression such as ((Const False) :&: <subexp>), will
<subexp> be reduced first (according to the definition
'simplify (x :&: y) = simplify' ((simplify x) :&: (simplify y))')
or will laziness do the right thing, and emit (Const False) without looking into
<exp>?
i think the
latter, but would appreciate a word from an expert.
thanks
konst
PS: any
coding suggestions, etc. are also welcome
infixr 3 :&:
infixr 2 :|:
data Exp = Const
Bool
| Sym String
| Not Exp
| Exp :&: Exp
| Exp :|: Exp
| Sym String
| Not Exp
| Exp :&: Exp
| Exp :|: Exp
instance Eq Exp where
(Const x) == (Const y) = x==y
(Sym x) == (Sym y) = x==y
(Not x) == (Not y) = x==y
(x :&: y) == (u :&: v) = x==u && y==v || x==v && y==u
(x :|: y) == (u :|: v) = x==u && y==v || x==v && y==u
_ == _ = False
(Const x) == (Const y) = x==y
(Sym x) == (Sym y) = x==y
(Not x) == (Not y) = x==y
(x :&: y) == (u :&: v) = x==u && y==v || x==v && y==u
(x :|: y) == (u :|: v) = x==u && y==v || x==v && y==u
_ == _ = False
simplify (x :&: y) = simplify'
((simplify x) :&: (simplify y))
simplify (x :|: y) = simplify' ((simplify x) :|: (simplify y))
simplify (Not x) = simplify' (Not (simplify x))
simplify x = x
simplify (x :|: y) = simplify' ((simplify x) :|: (simplify y))
simplify (Not x) = simplify' (Not (simplify x))
simplify x = x
simplify' (Not (Const
True)) = Const False
simplify' (Not (Const False)) = Const True
simplify' (Not (Const False)) = Const True
simplify' (Not (Not
x)) = x
simplify' ((Not x) :&: y) | x==y =
Const False
simplify' (x :&: (Not y)) | x==y = Const False
simplify' ((Not x) :|: y) | x==y = Const True
simplify' (x :|: (Not y)) | x==y = Const True
simplify' (x :&: (Not y)) | x==y = Const False
simplify' ((Not x) :|: y) | x==y = Const True
simplify' (x :|: (Not y)) | x==y = Const True
simplify' ((Const False) :&: _) =
Const False
simplify' (_ :&: (Const False)) = Const False
simplify' ((Const True) :&: x) = x
simplify' (x :&: (Const True)) = x
simplify' (_ :&: (Const False)) = Const False
simplify' ((Const True) :&: x) = x
simplify' (x :&: (Const True)) = x
simplify' ((Const True) :|: _)
= Const True
simplify' (_ :|: (Const True)) = Const True
simplify' ((Const False) :|: x) = x
simplify' (x :|: (Const False)) = x
simplify' (_ :|: (Const True)) = Const True
simplify' ((Const False) :|: x) = x
simplify' (x :|: (Const False)) = x
simplify' (x :&: y) |
x==y = x
simplify' (x :|: y) | x==y = x
simplify' (x :|: y) | x==y = x
simplify'
x
= x