#### Flawed Procedures

All the following procedures are flawed. Can you see why?

% merge(Xs, Ys, Zs) is true if Zs is an ordered list obtained from
% merging the ordered lists Xs and Ys.
merge([], Ys, Ys).
merge([X|Xs], [Y|Ys], [Y|Zs]):-
Y =< X, !, merge([X|Xs], Ys, Zs).
merge([X|Xs], Ys, [X|Zs]):-
merge(Xs, Ys, Zs).
% intersection(Xs, Ys, Zs) is true if Zs is the list of the set of
% elements in the intersection of the sets of elements in lists Xs
% and Ys. The elements in Zs are in the same order as they are
% in Xs.
intersection([], _, []).
intersection([X|Xs], Ys, [X|Zs]):-
member(X, Ys), !, intersection(Xs, Ys, Zs).
intersection([_|Xs], Ys, Zs):-intersection(Xs, Ys, Zs).
% insert(Ys, X, Zs) is true if Zs is the ordered list resulting from
% inserting X into the ordered list Ys.
insert([Y|Ys], X, [Y|Zs]):-Y < X, !, insert(Ys, X, Zs).
insert(Ys, X, [X|Ys]).
% subst(Ls, X, A, Ms) is true if the list Ms is the same as the
% list Ls except that all occurrences of the element X are replaced
% by A.
subst([], _, _, []).
subst([X|Ls], X, A, [A|Ms]):-!, subst(Ls, X, A, Ms).
subst([L|Ls], X, A, [L|Ms]):-subst(Ls, X, A, Ms).
% partition(Ls, X, Ms, Ns) is true if the list Ms contains the
% elements of the list Ls which are less than or equal to X,
% and the list Ns contains the elements of Ls which are greater
% than X. The elements of Ms and Ns are in the same order as
% they are in Ls.
partition([], _, [], []).
partition([K|Ls], X, Ms, [K|Ns]):-
X < K, !, partition(Ls, X, Ms, Ns).
partition([K|Ls], X, [K|Ms], Ns):-
partition(Ls, X, Ms, Ns).
% maximum(X, Y, Z) is true if Z is the maximum of the numbers
% X and Y.
maximum(X, Y, X):-X >= Y, !.
maximum(_, Y, Y).
% gcd(X, Y, Z) is true if Z is the greatest common divisor of the integers
% X and Y.
gcd(X, 0, X):-!.
gcd(X, Y, Z):-X1 is abs(X), Y1 is abs(Y), gcd_1(X1, Y1, Z).
gcd_1(X, 0, X):-!.
gcd_1(X, Y, Z):-R is X mod Y, gcd_1(Y, R, Z).

LPA Index
Home Page