[erlang-questions] Functional Datastructures

[Francis Stephens]

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.

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},...}.

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.

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}]]

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).

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080312/ffe55ad2/attachment.htm>