Subject: Re: I am having trouble writing replace/4

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 10 Jan 2000 12:28:58 +1300 (NZDT)

Douglas Miles ([email-masked]) wrote:

	replaceList([],[],NothingToDo,NothingToDo):-!.
	replaceList([HeadBefore|TailBefore],[HeadAfter|TailAfter],Start,End):-!,
	        replace(HeadBefore,HeadAfter,Start,Midde),
	        replaceList(TailBefore,TailAfter,Middle,End).
	
	replace(_, _, [], []):-!.
	replace(A, B, [A|L], [B|R]) :- !,    replace(A, B, L, R).
	replace(A, B, [C|L], [C|R]) :-   replace(A, B, L, R).
	
There is one fairly obvious problem with this as an implementation of
substitution, which is that implements *sequential* substitution rather
than *simultaneous* substitution.  Basically, there's a substitution
 {Old_I -> New_I} for I=1..M
and a list of items [Elt_J] for J=1..N.  Simultaneous substitution
has the form
    for J = 1 .. N do
        for I = 1 .. M do
            if Elt_J = Old_I then replace it by New_I
while sequential substitutione has the form
    for I = 1 .. M do
        for J = 1 .. N do
            if Elt_J = Old_I then replace it by New_I

	here is my trouble..
	
	?- replaceList([a,b],[A,B],[1,2,3,a,b,c,x,y,z],O).
	A = b
	B = _G422
	O = [1, 2, 3, _G422, _G422, c, x, y, z]
	yes
	
The binding of A to b is initially rather startling, until you realise that
the first time replace/4 is called (a->A), it changes
	[1,2,3,a,b,c,x,y,z]
to
	[1,2,3,A,b,c,x,y,z]
and then the second time (b->B), it *unifies* b with the elements,
thus binding A to b and then replacing it with B, yielding
	[1,2,3,B,B,c,x,y,z]

The simplest change is to write

	replace(_, _, [], []) :- !.
	replace(A, B, [C|L], [D|R]) :-
	    ( C == A -> D = B ; D = C ),
	    replace(A, B, L, R).
	
	I want it to do this...
	
	?- replaceList([a,b],[A,B],[1,2,3,a,b,c,x,y,z],O).
	A = _G421
	B = _G422
	O = [1, 2, 3, _G421, _G422, c, x, y, z]
	yes
	
	is copy_term/2 the key?

No.

	or maybe numbervars can help?
	
No.

	Any Suggestions?
	
The best method of all is to nest the loops properly.

%   substitute(+Substitution, +List0, -List)
%   succeeds when Substitution is a list of Old>New pairs, List0 and List
%   are lists, and the elements of List are obtained by applying the
%   substitution to the corresponding elements of List0.

substitute(Substitution, List0, List) :-
    substitute1(List0, List, Substitution).

substitute1([], [], _).
substitute1([Item0|Items0], [Item1|Items1], Substitution) :-
	(   member(Old>New, Substitution), Old == Item0 ->
	    Item1 = New
	;/* Substitution has no member matching Item0 */
	    Item1 = Item0
        ),
        substitute1(Items0, Items1, Substitution).