CODEWITHSUNDEEP
haskellrecursion
Shiroyuki
Shiroyuki

Reputation: 37

recursive case expression with data constructor haskell

I've got a little problem on recursion with data constructors.

data Proposition = Const Bool | Var [Char] | And Proposition Proposition | Or Proposition Proposition | Not Proposition deriving (Show, Eq)

simplify prop = whether (whether prop)
 where whether x = case x of (Const a)             -> x
                         (Var b)                   -> x
                         (And (Const y) (Const z)) -> if y && z then         Const True else Const False
                         (And y z)                 -> And (simplify y)(simplify z)
                         (Or (Const y) (Const z))  -> if y || z then Const True else Const False
                         (Or y z)                  -> Or (simplify y)(simplify z)
                         (Not (Const c))           -> Const (not c)
                         (Not (Var b))             -> Not (Var b)
                         (Not (Not (Const c)))     -> Const c
                         (Not x)                   -> Not (whether x)

So this is the code. The function is supposed to simplify expressions containing And, Or and Not. The function itself does what it should to single expressions. But it doesnt for expressions containing more than one And, Or or Not.

For example

simplify (Not (Const False)) == Const True

is true, but 

simplify (Not (Var "var2" `Or` Const True))

only evaluates to

Not (Or (Var "var2") (Const True))

instead of Const False

I cannot get my head to find a solution, so a hint would be nice on how to get the function recursive. Thank you!

Upvotes: 1

Views: 388

Answers (2)

radrow
radrow

Reputation: 7149

It is quite specific question, but I'll try to explain how I'd do it.

First of all you don't handle sufficient cases. Your program will "simplify" (Var "var2" `Or` Const True) to (Var "var2" `Or` Const True), because it does not care whether second value is Const True, while first is not Const _.

I would write another program that will evaluate your Proposition in 3-valued logics:

eval :: Proposition -> Maybe Bool
eval (Val _) = Nothing
eval (Const x) = Just x
eval (Or a b) = case (eval a, eval b) of
  (Just True, _) -> Just True
  (_, Just True) -> Just True
  (Just False, Just False) -> Just False
  _ -> Nothing -- because we don't know the resulting value
-- ...etc

And then perform simplification, for example

simplify o@(Or a b) = case (eval o) of
  Just v -> Const v
  Nothing -> Or (simplify a) (simplify b) -- we cannot simplify the `Or` usage
-- ...etc

This will greatly reduce cases that you need to check, and provide you and interpreter for your propositions as side effect. I believe it could be written more elegant using some Haskell's magic, but let's leave it as an exercise for a reader

Upvotes: 3

Bob Dalgleish
Bob Dalgleish

Reputation: 8227

You need to add some explicit matches for reducing constants:

(And (Const False) _) -> Const False
(And _ (Const False)) -> Const False
(And (Const True) x)  -> x
(And x (Const True))  -> x
(Or  (Const True) _)  -> Const True
(Or  _ (Const True))  -> Const True
(Or (Const False) x)  -> x
(Or x (Const False))  -> x

There are some others that can be applied in a similar fashion.

Upvotes: 3

Related Questions