Nontrivial prologue find and replace

Question

Thus, we can easily find and replace an atom with another atom in Prolog by doing something like:

replace([],A,B,[]). replace([H|T],A,B,[B|Result]) :- H=A, replace(T,A,B,Result),!. replace([H|T],A,B,[H|Result]) :- replace(T,A,B,Result). 

I am sure there are other ways to do this.

However, I want to do something more complex in the logic of calculations. How would you do something like replacing conjunctions of type conj(x,y) in a boolean expression with just (x, y)? So it looks like a final one and a replacement, but not atoms. So we could have something like reduce(conj(conj(x,y),z)). which I would like to reduce to ((x,y),z) .

This is a simple example with only conjunctions, but this is what I want to do in the case of unions. If anyone is interested, it's all about descriptive logic and the table method.

What bothers me is how you go about finding and replacing when the input is not a list; it is a structure. I don’t see how you can solve this problem without using the standard [H|T] trick with recursion and lists. Anyone got any ideas?

Many thanks.

Answer 1

This is done in a simple way by writing a meta-interpreter, for example:

 replace(V, V) :- % pass vars through var(V), !. replace(A, A) :- % pass atoms through atomic(A), !. replace([], []) :- % pass empty lists through !. replace([X|Xs], [Y|Ys]) :- % recursively enter non-empty lists !, replace(X, Y), replace(Xs, Ys). replace(conj(X,Y), (NX,NY)) :- % CUSTOM replacement clause for conj/2 !, replace(X, NX), replace(Y, NY). replace(T, NT) :- % finally, recursively enter any as yet unmatched compound term T =.. [F|AL], replace(AL, NAL), NT =.. [F|NAL]. 

Pay attention to the second last sentence, which serves to replace your specific case of replacing conj/2 with connection conj/2 ,/2 . You can add as many other sentences in the same way as this in order to replace the terms in general, because the rest of the definition (all other replace/2 sentences) recursively deconstruct any PROLOG term here, as we have covered all types; vars, atoms, and compound terms (including lists explicitly).

Doing this in your case gives us:

 ?- replace(conj(conj(x,y),z), NewTerm). NewTerm = ((x, y), z). 

Please note that this definition will correctly replace any members nested in arbitrary depth within another term.

Answer 2

Recall that a list is just a specific structure, so you can easily translate your code so that it matches any other structure. This can help you use a cleaner view for your data: just as you use conj / 2 to denote unions, you can introduce the var / 1 functor to denote variables:

 reduce(conj(X0,Y0), (X,Y)) :- reduce(X0, X), reduce(Y0, Y). reduce(var(X), X). 

Example:

 ?- reduce(conj(conj(var(x),var(y)), var(z)), R). R = ((x, y), z). 

Answer 3

You can include the general term in the list using =.. , for example

 ?- conj(conj(x,y),z) =.. List. List = [conj, conj(x, y), z]. 

By doing this recursively, you can smooth out the full term.

A general predicate that modifies certain nodes in an input member will look something like this:

 change_term(NodeChanger, Term1, Term3) :- call(NodeChanger, Term1, Term2), change_term(NodeChanger, Term2, Term3), !. change_term(NodeChanger, Term1, Term2) :- Term1 =.. [Functor | SubTerms1], change_termlist(NodeChanger, SubTerms1, SubTerms2), Term2 =.. [Functor | SubTerms2]. change_termlist(_, [], []). change_termlist(NodeChanger, [Term1 | Terms1], [Term2 | Terms2]) :- change_term(NodeChanger, Term1, Term2), change_termlist(NodeChanger, Terms1, Terms2). 

If you now define:

 conj_changer(conj(X, Y), (X, Y)). 

then you can define your reduction predicate:

 reduce(Term1, Term2) :- change_term(conj_changer, Term1, Term2). 

Using:

 ?- reduce(conj(conj(x,y),z), ReducedTerm). ReducedTerm = ((x, y), z). 

You have to be careful, but as you define a NodeChanger , certain definitions can do a change_term/3 loop. Maybe someone can improve this.