I am trying to build an efficient data structure for representing boolean expressions in Erlang.  I am having trouble producing a good data structure in a functional context, although there are very fast data structures for imperative languages like C.  The data structure is to be used for a functional SAT solver.<br>
<br>A boolean expression (always in conjunctive normal form) can be described as a set of variables, such as {p,q,r...} where each variable in the set is mapped to one of three values true|false|indetermined yielding something like {{p->ind},{q->true},{r->ind},...}.<br>
<br>The expression is described as a set of sets of literals, where a literal is a variable with a possible negation (~).  So we have something like {{~p,q},{~q,r}} which describes a formula that would usually be written (~p v q)&(~q v r).  Each of the inner sets has the property that if one of its literals evaluates to true then the whole set can be removed from the outer set.<br>
<br>To being with we can represent the expression as a list of lists where the variable-name, negation and value are all stored in one tuple.  [[{name,negation,value}]]<br><br>Now if we assign a value to a variable we then need to traverse every sublist ensuring a consistent assignment is made for every occurrence of the varia ble in the expression.  However, as a reward for this effort we can easily check each sublist to see whether one of its members evaluates to true (meaning the sublist can be removed).<br>
<br>Alternately we could represent the expression as a list of lists where just the variable name and negation are recorded {name,negation} and have the assignment values stored as a separate mapping.  This makes assignments fast and safer, but we still need to traverse every sublist to see that it does not now contain a literal evaluating to true.  Is there a better way, I suspect that I am thinking about it in the wrong way.  Thanks.