-- cartesian product of lists
cartprod :: [[a]] -> [[a]]
cartprod [] = [[]]
cartprod (xs : xss) = [ x : ys | x <- xs, ys <- yss]
    where yss = cartprod xss

-- all possible truth values on n vars
build n = cartprod xs
    where xs = take n $ repeat [0,1]

-- datatype for boolean logic
data Expr =
    Var String
  | And Expr Expr
  | Or Expr Expr
  | Imp Expr Expr
  | Not Expr
  | Equiv Expr Expr
  | T | F

-- state of variable named String
type State = [(String, Bool)]

-- evaluate a boolean expression
eval :: Expr -> State -> Bool
eval exp state = case exp of
      Var str -> case lookup str state of
        Nothing -> error "variable not found"
        Just b  -> b
      And a b ->eval a state && eval b state
      Or  a b -> eval a state || eval b state
      Imp a b -> not (eval a state && (not $ eval b state))
      Not a   -> not $ eval a state
      Equiv a b -> eval a state== eval b state
      T -> True
      F -> False

-- possible names
alph = ['a' .. 'z'] ++ ['A' .. 'Z']

-- make state from a list of ints (uses as default left to right entries in alph)
makestate :: [Int] -> State
makestate = zipWith (\x y -> ([x], not $ y == 0)) alph

-- remove duplicate strings from a list (used in getvars)
rmdup :: [String] -> [String]
rmdup [] = []
rmdup (x:xs) | elem x xs = rmdup xs
             | otherwise = x : rmdup xs

-- return the Strings held by variables in an expression
getvars :: Expr -> [String]
getvars exp = case exp of
  Var str -> [str]
  And a b -> getvars a ++ getvars b
  Or a b  -> getvars a ++ getvars b
  Imp a b -> getvars a ++ getvars b
  Equiv a b -> getvars a ++ getvars b
  Not a   -> getvars a
  T -> []
  F -> []

-- count the number of distinct vars in an expression
countvar :: Expr -> Int
countvar = length . rmdup . getvars

-- create state of all possible vars in an expression
totalstate :: Expr -> [State]
totalstate exp = map makestate (build $ countvar exp)

-- eval expression under all possible states
totaleval :: Expr -> [Bool]
totaleval exp = map (eval exp) (totalstate exp)

a = Var "a"
b = Var "b"
c = Var "c"

ex_a = (Imp (Imp (Imp a b) b) b)
ex_b = (Imp (Imp (Imp a b) b) a)
ex_c = (Imp (Imp (Imp a b) a) a)
ex_d = (Imp (Imp (Imp b c) (Imp a b)) (Imp a b))
ex_e = (Imp (Or a (Not (And b c))) (Or (Equiv a c) b))
ex_f = (Imp a (Imp b (Imp b a)))
ex_g = (Imp (And a b) (Or a c))

-- example : totaleval ex_a = [True, True, True, True]