Prolog: Getting unique atoms from propositional formulas

1
votes

I can easily write a predicate to get unique elements from a given list in Prolog e.g. 

no_doubles( [], [] ).
no_doubles( [H|T], F ) :-
 member( H, T ),
 no_doubles( T, F ).
no_doubles( [H|T], [H|F] ) :-
 \+ member( H, T ),
 no_doubles( T, F ).

However, how can you do the same thing but for something other than a normal list i.e. not something like [a,b,c...]? So in my case, I want to extract unique atoms for a propositional formula e.g. unique_atoms(and(x,and(x,y),z),[x,y,z]). is satisfied. Do you use recursion just like in my no_doubles example but for a formula like this?

Any ideas are welcomed :). Thanks.

2
prolog

2 Answers

2
votes

So you need to process a general term (i.e. a tree structure) and get a list of its atomic leaf nodes, without duplicates. Does the result list have to have a specific order (e.g. depth-first left-to-right), or is this not important?

If you have an option to use variables instead of atoms in your formulas then you can use the (SWI-Prolog) builtin term_variables/2, e.g.

?- term_variables(and(X, and(X, Y), Z), Vars).
Vars = [X, Y, Z].

Otherwise you have to go with a solution similar to:

term_atoms(Term, AtomSet) :-
    term_to_atomlist(Term, AtomList),
    list_to_set(AtomList, AtomSet).


term_to_atomlist(Atom, [Atom]) :-
    atom(Atom),
    !.

term_to_atomlist(Term, AtomList) :-
    compound(Term),
    Term =.. [_ | SubTerms],
    terms_to_atomlist(SubTerms, AtomList).


terms_to_atomlist([], []).

terms_to_atomlist([Term | Terms], AtomList) :-
    term_to_atomlist(Term, AtomList1),
    terms_to_atomlist(Terms, AtomList2),
    append(AtomList1, AtomList2, AtomList).

Usage example:

?- term_atoms(f(x^a1+a3*a3/a4)='P'-l, Atoms).
Atoms = [x, a1, a3, a4, 'P', l].

You might want to extend it to deal with numbers and variables in the leaf nodes.

1
votes
?- setof(X, member(X,[a,b,c,a,b,c]), L).
L = [a, b, c].

?- sort([a,b,c,a,b,c], L).
L = [a, b, c].

Propositional formulas:

get_atoms(X,[X]) :-
    atom(X).
get_atoms(and(P,Q),Atoms) :-
    get_atoms(P,Left),
    get_atoms(Q,Right),
    append(Left,Right,Atoms).

etc. Optimize using difference lists if necessary.

unique_atoms(P,UniqueAtoms) :- get_atoms(P,Atoms), sort(Atoms,UniqueAtoms).

A more direct way is to use sets.