Solving logical formula with own data type and a map

Question

I want to write a logical formulae solving program in Haskell. So far I've managed to print given formula as string, for example formula

(I (N (Z 'p')) (A (C (Z 'p') (Z 'q')) (Z 'r')))

results in

"(~p => ((p & q) | r))"

where I is implication, A is alternative, C in conjunction, N in negation and Z is character.

My data type is like:

data Formula = Z Char | V Bool | N Formula 
               | K Formula Formula | A Formula Formula 
               | C Formula Formula | Join Formula Formula 

My problem is that I don't know how to write a function, which will evaluate formula with given map of characters and boolean values, I mean, for ex.: [('p', True), ('q', False), ('r', False)] I can't come up with a method to substitute those letters with some True/False value and check it. Is there any simple way to do this?

Answer 1

You can just pass the list of character and boolean values and use the lookup function from Data.List:

import Data.List

evaluate :: [(Char, Bool)] -> Formula -> Bool
evaluate mapping (Z sym) =
    case lookup sym mapping of
       Just v -> v
       Nothing -> error $ "Undefined symbol " ++ show v
evaluate _mapping (V v) = v
evaluate mapping (N formula) = not (evaluate mapping formula)
...

For a more efficient representation of the mapping, use the Data.Map module instead of the list of associations.