replace an element in list with its first occurence but keep replacing for all occurences- Prolog

user_15446433 0
Viewed 59

I have just started programing in Prolog, using tkeclipse. What I want to do, is to replace an element of the list with another element on the first place that it occurs. However, when I press the more button (;) I want the query to return also the other solutions. Example:

?- replace(1,a,[1,2,3],R).

R = [a, 2, 3]
Yes
?- replace(1,a,[1,2,1,1,3],R).
R = [a, 2, 1, 1, 3] ;
R = [1, 2, a, 1, 3] ;
R = [1, 2, 1, a, 3] ;
No

What I wrote so far, works fine, but in the end, after [1,2,1,a,3], I also get [1,2,1,1,3] instead of no. My code is as follows:

%%% replace/4

replace(_,_,[],[]).
replace(X,Y,[X|T],[Y|T]).


replace(X,Y,[H|T],[H|T2]) :-  
    replace(X,Y,T,T2).
prolog list replace
2 Answers

Just delete the first clause

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

and you should be fine.

user_65406060

You [1,2,1,1,3] because:

replace(1,a,[1,2,1,1,3],[1,2,1,1,3]) is successful by

  • always taking the third clause, reducing the pre-replacement-list and the result-of-the-replacement list element by element
  • succeeding on the empty list by taking the first clause

You want:

  1. Success on the empty list (0 replacements); and also
  2. A stream of of exactly-one-replacements

And so:

replace(_,_,[],[]) :- !. % make this deterministic with a a cut

replace(X,Y,PreList,PostList) :-
   replace_2(X,Y,PreList,PostList).

% replace_2/4 is the same as replace/4 but does NOT succeed for the empty list

replace_2(X,Y,[X|T],[Y|T]).

replace_2(X,Y,[H|T],[H|T2]) :-  
    replace_2(X,Y,T,T2).

And so:

?- replace(1,a,[1,2,3],R).
R = [a, 2, 3] ;
false.

?- replace(1,a,[1,2,1,1,3],R).
R = [a, 2, 1, 1, 3] ;
R = [1, 2, a, 1, 3] ;
R = [1, 2, 1, a, 3] ;
false.

?- replace(foo,a,[1,2,1,1,3],R).
false.

?- replace(foo,a,[],R).
R = [] ;
false.
user_8844630
Related