布尔表达式计算器的实现–Haskell实验三

实验要求

module Lab3(
Prop(..),
isTaut -- :: Prop ->Bool
) where

import Data.List
import Data.Traversable
----------------------------------------------------------------------------
data Prop = Const Bool | Var Char | Not Prop | And Prop Prop | Or Prop Prop | Imply Prop Prop deriving Eq
type Subst = [(Char, Bool)]

p1 :: Prop
p1 = And (Var 'A') (Not (Var 'A'))

p2 :: Prop
p2 = Or (Var 'A') (Not (Var 'A'))

p3 :: Prop
p3 = Imply (Var 'A') (And (Var 'A') (Var 'B'))

----------------------------------------------------------------------------
instance Show Prop where
 show (Const x) = show x
 show (Var x) = show x
 show (Not x) = "~" ++ show x
 show (And x x1) = show x ++ "&&" ++ show x1
 show (Or x x1) = show x ++ "||" ++ show x1
 show (Imply x x1) = show x ++ "=>" ++ show x1
----------------------------------------------------------------------------

check :: Char -> Subst -> Bool
check word sub = head [snd x | x <- sub,fst x == word]

eval :: Subst -> Prop -> Bool
eval sub (Const y) = y
eval sub (Var y) = check y sub
eval sub (Not y) = not (eval sub y)
eval sub (And y y1) = (eval sub y) && (eval sub y1)
eval sub (Or y y1) = (eval sub y) || (eval sub y1)
eval sub (Imply y y1) = if (eval sub y == True) && (eval sub y1 == False) then False else True
----------------------------------------------------------------------------

vars :: Prop -> [Char]
varstemp :: Prop -> [Char]
--substs :: Prop -> a

vars pr = nub (varstemp pr)

varstemp (Const z) = []
varstemp (Var z) = [z]
varstemp (Not z) = varstemp z
varstemp (And z z1) = varstemp z ++ varstemp z1
varstemp (Or z z1) = varstemp z ++ varstemp z1
varstemp (Imply z z1) = varstemp z ++ varstemp z1
----------------------------------------------------------------------------

subststemp :: Prop -> Subst
subststemp pr = [(x,y) | x <- vars pr , y <- [True,False]]

substs :: Prop -> [Subst]
substs pr = sequenceA $ list temp
   where 
   rootx = varlen (vars pr)
   list [] = []
   list a = [take rootx a] ++ list (drop rootx a)
   temp = subststemp pr

varlen :: [Char] -> Int
varlen res = length res

----------------------------------------------------------------------------
isTaut :: Prop -> Bool
isTaut pr = alwayscheck pr (substs pr)

alwayscheck :: Prop -> [Subst] -> Bool
alwayscheck pr [] = True
alwayscheck pr sub = if (eval (head sub) pr) then (alwayscheck pr (tail sub)) else False

未经允许不得转载：MikuAlpha's Blog » 布尔表达式计算器的实现–Haskell实验三