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