Its been a while since I had a look at this type of thing, but I would suggest that you had a look at <a href="http://en.wikipedia.org/wiki/Binary_decision_diagram">Binary Decision Diagrams</a> (<a href="http://en.wikipedia.org/wiki/Binary_decision_diagram">http://en.wikipedia.org/wiki/Binary_decision_diagram</a>) which I know from own experience in another millennium can be implemented in SML without too much hazzle. I would suspect that it is just as easy in Erlang... especially since you have some neat data structures available that can make the implementation easier to do.<br>
<br>If that can handle undetermined values is for further study by you!! ;-)<br><br>Cheers,<br>Torben<br><br><div class="gmail_quote">2008/3/12 Francis Stephens <<a href="mailto:francisstephens@gmail.com">francisstephens@gmail.com</a>>:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">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.
<br>_______________________________________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://www.erlang.org/mailman/listinfo/erlang-questions" target="_blank">http://www.erlang.org/mailman/listinfo/erlang-questions</a><br></blockquote></div><br>