CODEWITHSUNDEEP
listreplaceprolog
Donald
Donald

Reputation: 91

Prolog element in lists replacement

Hi i was wondering if you could help me out with this

From programming in Prolog: write Prolog script for replacement any given element in lists by an another given element. For example:

replace( 3, a,[1,2,3,4,3,5], [1,2,a,4,a,5])=true

Many Thanks in advance

Upvotes: 8

Views: 38596

Answers (5)

repeat
repeat

Reputation: 18726

All implementations presented so far in other answers are logically unsound when being used with non-ground terms. Consider the original query and a slight variant:

?- replace(3,three,[1,2,3],Xs).
Xs = [1,2,three] ;                 % OK: correct
false

?- A=3, replace(A,B,[1,2,3],Xs).   % OK: correct
Xs = [1,2,B], A = 3 ;
false

It works! Let's ask some very similar queries:

?- replace(A,B,[1,2,3],Xs).        % FAIL: should succeed more than once...
Xs = [B,2,3], A = 1 ;              %       ... but the other solutions are missing 
false

?- replace(A,B,[1,2,3],Xs), A=3.   % FAIL: this query _should_ succeed ...
false                              %       ... it does not!

What's going on? Put the blame on meta-logical builtins (!)/0 and (\=)/2, which are very hard to use right and often make code brittle, impure, and logically unsound.

To preserve logical soundness, stick to logical purity and abstain from meta-logical "features" whenever possible! Luckily, most Prolog implementations support dif/2 as a logical alternative to (\=)/2. Let's use it:

% code by @svick, modified to use dif/2 instead of (\=)/2
replaceP(_, _, [], []).
replaceP(O, R, [O|T], [R|T2]) :- replaceP(O, R, T, T2).
replaceP(O, R, [H|T], [H|T2]) :- dif(H,O), replaceP(O, R, T, T2).

Let's run above queries again, this time with the improved replaceP/4:

?- replaceP(3,three,[1,2,3],Xs).
Xs = [1,2,three] ;                 % OK: correct, like before
false

?- replaceP(A,B,[1,2,3],Xs).       % OK: four solutions, not just one
Xs = [B,2,3], A = 1 ;         
Xs = [1,B,3], A = 2 ;
Xs = [1,2,B], A = 3 ;
Xs = [1,2,3], dif(A,1),dif(A,2),dif(A,3) ;
false

?- replaceP(A,B,[1,2,3],Xs), A=3.  % OK (succeeds now)
Xs = [1,2,B], A = 3 ;                 
false
?- A=3, replaceP(A,B,[1,2,3],Xs).  % OK (same as before)
Xs = [1,2,B], A = 3 ;
false

Upvotes: 10

Maik
Maik

Reputation: 29

domains
I=integer*
K=integer*
Z=integer
A=integer
predicates
nondeterm  rep(I,Z,A,K)
clauses
rep([],_,_,[]).
rep([Z|T1],Z,A,[A|T2]):- rep(T1,Z,A,T2).
rep([H|T1],Z,A,[H|T2]) :- rep(T1,Z,A,T2).
goal
rep([1,2,3],2,4,X).

Upvotes: 0

bearzk
bearzk

Reputation: 790

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).

the idea is simple, if the elements match, change it, if not, go forward until empty.

Upvotes: 0

Davorin Ruševljan
Davorin Ruševljan

Reputation: 4392

replace(_, _ , [], []).

replace(X, Y, [ X | Z ], [ Y | ZZ]):- ! , replace( X, Y, Z, ZZ).

replace(X, Y, [ W | Z], [ W | ZZ] :- replace(X, Y, Z, ZZ).

Though, one would usually arrange the 3. arg to be the first one. And strictly speaking above does not replace anything in the list, it just anwsers if 4th arg is like the one in the 3rd but with Y' instead of X'.

Upvotes: 0

svick
svick

Reputation: 244827

In Prolog, most list processing is done by processing the head and then recursively processing the rest of the list. Of course, you can't forget about the base case, which is an empty list.

Replacing anything with anything in an empty list results again in an empty list. If the head of the list is the same as the element to replace, replace it, otherwise, keep it as it is. In both cases, process recursively the rest of the list. Translated from English into Prolog:

replace(_, _, [], []).
replace(O, R, [O|T], [R|T2]) :- replace(O, R, T, T2).
replace(O, R, [H|T], [H|T2]) :- H \= O, replace(O, R, T, T2).

Upvotes: 14

Related Questions