How to generate a set of values for a set of boolean variables in Ocaml

Question

Let's say we have a function that takes as input a set of Boolean variables: bol1,bol2...boln. How can we iterate through all possible Boolean assignments using minimum codes as possible? I need to implement a function that takes input a set of two Boolean variables together with a Boolean expression involving the variables and create a truth table. If you look at my code, It is long. SO I want to reduce it. Furthermore, the way I did it seem to be redudndant as the compiler gives warning saying the match case |Var v2 is unused for all match case |Var v2 in the code.

This is exercises 46/47 in this link : "Define a function, table2 which returns the truth table of a given logical expression in two variables (specified as arguments). The return value must be a list of triples containing (value_of_a, balue_of_b, value_of_expr)."

type bool_expr =
  | Var of string
  | Not of bool_expr
  | And of bool_expr * bool_expr
  | Or of bool_expr * bool_expr 

let table2 (v1 : string) (v2 : string ) (exp : bool_expr)= 
  let rec evaluate (bol1 : bool) (bol2 : bool) (expp : bool_expr) =
    match bol1, bol2 with
    |true, true -> (match expp with
        |Var v1 -> true
        |Var v2 -> true
        |Not q -> not (evaluate bol1 bol2 q )
        |And (q,w) -> (evaluate bol1 bol2 q) && (evaluate bol1 bol2 w)
        |Or (q, w) -> (evaluate bol1 bol2 q) || (evaluate bol1 bol2 w))
    |true, false -> (match expp with
        |Var v1 -> true
        |Var v2 -> false
        |Not q -> not (evaluate bol1 bol2 q )
        |And (q,w) -> (evaluate bol1 bol2 q) && (evaluate bol1 bol2 w)
        |Or (q, w) -> (evaluate bol1 bol2 q) || (evaluate bol1 bol2 w))
    |false, true -> (match expp with
        |Var v1 -> false
        |Var v2 -> true
        |Not q -> not (evaluate bol1 bol2 q )
        |And (q,w) -> (evaluate bol1 bol2 q) && (evaluate bol1 bol2 w)
        |Or (q, w) -> (evaluate bol1 bol2 q) || (evaluate bol1 bol2 w))
    |false, false -> (match expp with
        |Var v1 -> false
        |Var v2 -> false
        |Not q -> not (evaluate bol1 bol2 q )
        |And (q,w) -> (evaluate bol1 bol2 q) && (evaluate bol1 bol2 w)
        |Or (q, w) -> (evaluate bol1 bol2 q) || (evaluate bol1 bol2 w))
  in [(true,true, (evaluate true true exp));(true,false, (evaluate true false exp));(false,true, (evaluate false true exp));(false,false, (evaluate false false exp))]

Here is an example of the expected output:

table2 "a" "b" (And(Var "a", Or(Var "a", Var "b")));;

• : (bool * bool * bool) list = [(true, true, true); (true, false, true); (false, true, false); (false, false, false)]

Answer 1

Hint: try looking at the problem recursively.

bool_values { b_0, b_1, .... b_n } =
  { T + bool_values { b_1. ... b_n } } +
  { F + bool_values { b_1. ... b_n } }

Answer 2

You can cut down your code by a factor of 4 if you don't match bol1 and bol2 but simply use them.

(match expp with
   | Var v1 -> bol1
   | Var v2 -> bol2
   ...

Secondly matching does not compare variables but structure. Matching against Var v1 binds the value expp has to a new variable v1. The two cases Var v1 and Var v2 have the same structure and the second case is never reached.

To compare values you have to write:

| Var v when v == v1 -> bol1
| Var v when v == v2 -> bol2
| Var v -> (* neigther v1 nor v2, what to do now? *)

As for extending this to tables with more columns you will have to use recursion and either lists or arrays instead of tuples. E.g. type table = ((bool list) * bool) list