Subject: Re: substitute

From: "Richard A. O'Keefe" <[email-masked]>
Date: Mon, 20 Nov 2000 12:54:46 +1300 (NZDT)

aikGuitarist <[email-masked]> wrote:
	Here is a program that I am writing
	
	% substitute(List, Old, New, RevisedList) is true if the list RevisedList
	% is the result of substituting New for all occurrences of Old in the 
	% list List. 
	
	substitute([], Old, New, []).
	substitute([Old|Olds], Old, New, [New|News]) :-
	    substitute(Olds, Old, New, News).
	substitute([Temp|Olds], Old, New, [Temp,News]) :-
	    Old \= Temp,
	    substitute(Olds,Old, New, News).
	
First, we had a substitution predicate in the DEC-10 Prolog library 20 years
ago.  It's a crying shame that people are *still* writing new ones.  But you
can certainly find code in a book.

Second, it's really a bad idea to say (by omission) in the second clause
"hey, even if the head matches, it's a good idea to try later clauses"
and then patch around it in the third clause.

(\=)/2 is The Predicate That Should Not Exist, except in Prologs that can
implement it soundly.  It is a very good idea to avoid it entirely.

But third, the second clause has [New|News] while the third clause
has [Temp,News] (note the comma).

Cleaning the code up while keeping it close to its present style yields:

	substitute([], _, _, []).
	substitute([Old|Xs], Old, New, [Y|Ys]) :- !,
	    Y = New,
	    substitute(Xs, Old, New, Ys).
	substitute([X|Xs], Old, New, [X|Ys]) :-
	    substitute(Xs, Old, New, Ys).

I reckon this is a case for if-then-else, so would write

	substitute([], _, _, []).
	substitute([X|Xs], Old, New, [Y|Ys]) :-
	    ( X = Old -> Y = New ; Y = X ),
	    substitute(Xs, Old, New, Ys).