CODEWITHSUNDEEP
listreplaceprolog
user1257768
user1257768

Reputation: 149

replacing terms in a list prolog

I'm trying to write a prolog program that will take as input a list, an old_subterm and a new_subterm, and return a new list where every instance of old_subterm has been replaced with new_subterm. So for instance

| ?- sub_rep([h(A,g(x)),g(x),g(3)],g(x),p,T).
T = [h(A,p),p,g(3)] ? ;
no

So I can get this to work with basic lists, with the following code:

replace(E,S,[],[]).
replace(E,S,[E|T1],[S|T2]):-
    replace(E,S,T1,T2).
replace(E,S,[H|T1],[H|T2]):-
    E\=H, 
    replace(E,S,T1,T2).

%(here's some example input/output)

?- replace(b,e,[a,b,c],L).
L = [a, e, c] ;
false.

?- replace(f(Y),g(Y),[f(Y),1,2,f(Y)],L).
L = [g(Y), 1, 2, g(Y)] ;
false.

but when I try it with a more complicated list, such as

?- replace(g(Y),h,[f(g(Y)),g(Y),g(1)],L).

I get the following answer:

Y = 1,
L = [f(g(1)), h, h] ;
false.

which is not what I'm looking for, since I'm hoping for it to return:

? - L = [f(h),h,g(1)] ;
false.

I'm new to prolog, and I'm probably missing something obvious, but I don't understand why the variable Y is getting instantiated in this case? It doesn't appear to be a problem in the second example. I imagine it has something to do with the appearance of g(1), but I don't understand why? Thanks in advance! :)

Upvotes: 1

Views: 1099

Answers (2)

false
false

Reputation: 10102

A first observation on your problem: The lists are of same length! This sounds like a good candidate for maplist/3!

replace(A, B, As, Bs) :-
   maplist(repl(A,B), As, Bs).

So much for the "recursive" part of your problem. Now, we have to define repl/4. Here is my guess about what you want:

repl(A, B, A0, B0) :-
   ( A == A0 -> B = B0 ; A0 = B0 ).

Maybe you want some other test in stead of (==)/2.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60014

You should 'explode' your terms for comparison.

replace(_, _, [], []).
replace(E, S, [X|T1], [Y|T2]):-
    replace_term(E, S, X, Y),
    !, replace(E, S, T1, T2).
replace(E,S, [H|T1], [H|T2]):-
    replace(E,S,T1,T2).

replace_term(E, S, E, S) :- !.
replace_term(E, S, T, R) :-
      T =.. [F|As],  % explode
      replace(E, S, As, Gs),
      R =.. [F|Gs].  % reassemble

test:

?- replace(a,b,[a(a),b,c],L).
L = [a(b), b, c] ;
false.


?- replace(g(y),h,[f(g(y)),g(y),g(1)],L).
L = [f(h), h, g(1)] .

when there are variables in pattern, things get more complex:

?- replace(g(Y),h,[f(g(Y)),g(Y),g(1)],L).
Y = 1,
L = [f(h), h, h] ;

Perhaps numbervars can help, or we must devise a strategy that instantiate at once the vars...

Upvotes: 0

Related Questions