Replacing one variable with another
Given a list of lists, I would like to replace everything A
with B
s, where A
and B
are prolog variables.
For example, if the list was [[1,2,D,C],[A,D],[4,A],[1,2,A]]
I want the result to be[[1,2,D,C],[B,D],[4,B],[1,2,B]]
To do this, I wrote the following to replace everything A
in B
with one list:
/*substitude_single(+OldVar,+NewVar,+OldList,-NewList) */
substitute_single(_,_,[],[]).
substitute_single(A,B,[A|As],[B|Bs]):-
substitute_single(A,B,As,Bs).
substitute_single(A,B,[X|As],[X|Bs]):-
substitute_single(A,B,As,Bs).
And now I am applying this to every element of the main list, which is a list:
substitute(_,_,[],[]).
substitute(A,B,[P|Ps],[Q|Qs]):-
substitute_single(A,B,P,Q),
substitute(A,B,Ps,Qs).
The problem arises when, for example, I test my code for substitute_single(A,B,[C,A,D,1],X)
, I get many solutions, some of them apply values to variables. For example, I get:
A = 1,
C = 1,
D = 1,
X = [B, B, B, B] ;
or
A = D,
C = D,
X = [B, B, B, 1]
and only after many other solutions i get:
X = [C, B, D, 1]
which I would like. And yet, there are even more solutions (which I don't want) after it.
So, I tried to cut the program so that it doesn't generate more solutions:
substitute_single(A,B,[A|As],[B|Bs]):-
substitute_single(A,B,As,Bs),
!.
But now that I only get one solution, this is not the one I aimed at!
(For the above example, the solution I get is
A = 1,
C = 1,
D = 1,
X = [B, B, B, B].
)
I don't know how or where I should change my program, so this will only give me the solution I want?
(Note: A
and B
can be variables or also constants, for example:) substitute_single(A,3,[C,A,D,1],X)
should generate [C,3,D,1]
)
source to share
The problem with your solution is that you are applying terminological unification as an equality test when you need a test for strictly identical terms for which a predicate exists ==/2
.
To exchange two terms that can be variables in the same list, provided the correct closed list and the mode +,?,?, - the predicate is enough
exchgterms([],_,_,[]).
exchgterms([X|Xs],A,B,[C|Ys]) :-
( X == A -> C=B ;
( X == B -> C=A ; C=X ) ),
exchgterms(Xs,A,B,Ys).
You can start here to solve your problem and modify it to suit your needs, in particular if your predicate needs to have a different mode.
UPDATE
I changed the name of my predicate to emphasize that it also works for exchanging terms that are not variables.
It should be clear that it must replace with substitute_single/4
arguments in a different order in the second sentence substitute/4
, so the solution you are looking for is
substitute(_,_,[],[]).
substitute(A,B,[L|Ls],[R|Rs]) :-
exchgterms(L,A,B,R),
substitute(A,B,Ls,Rs).
I would suggest that you change the order of the arguments in substitute/4
so that the third argument comes first. In this form, most Prolog systems will know that if this argument is constructed, as is the case here, the two clauses are mutually exclusive and will facilitate more efficient execution.
source to share
substVarInTerm/4
is what I came up with.
:- use_module(library(apply)).
substVarInTerm(A,B,Term0,Term) :-
term_variables(Term0,Vars0),
exclude(==(A),Vars0,Vars),
copy_term(A^Vars^Term0,B^Vars^Term).
Note that it substVarInTerm/4
does n't work if the first argument is anything other than a variable.
The other use cases you gave looks simple:
?- substVarInTerm(A,B,[[1,2,D,C],[A,D],[4,A],[1,2,A]],R). R = [[1, 2, D, C], [B, D], [4, B], [1, 2, B]]. ?- substVarInTerm(A,B,[C,A,D,1],X). X = [C, B, D, 1]. ?- substVarInTerm(A,3,[C,A,D,1],X). X = [C, 3, D, 1].
source to share