[erlang-questions] Functional Datastructures

[Torben Hoffmann]

Its been a while since I had a look at this type of thing, but I would
suggest that you had a look at Binary Decision
Diagrams<http://en.wikipedia.org/wiki/Binary_decision_diagram>(
http://en.wikipedia.org/wiki/Binary_decision_diagram) 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.

If that can handle undetermined values is for further study by you!! ;-)

Cheers,
Torben

2008/3/12 Francis Stephens <francisstephens@REDACTED>:

> 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.
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://www.erlang.org/mailman/listinfo/erlang-questions
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20080312/3d2a1395/attachment.htm>