Classic Procedures

/* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs */
/*   to the list Ys.                                                       */
% append([], Ys, Ys).
% append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).

/* adjacent(X, Y, Zs) is true if the element X immediately precedes the    */
/*   element Y in the list Zs.                                             */
adjacent(X, Y, [X|[Y|_]]).
adjacent(X, Y, [_|Zs]):-adjacent(X, Y, Zs).

/* delete(Xs, Y, Zs) is true if Zs is the result of removing all           */
/*   occurrences of the element Y from the list Xs.                        */
delete([], _, []).
delete([Y|Xs], Y, Zs):-!, delete(Xs, Y, Zs).
delete([X|Xs], Y, [X|Zs]):-delete(Xs, Y, Zs).

/* disjoint(Xs, Ys) is true if the sets of elements in lists Xs and Ys     */
/*   have no common element.                                               */
disjoint([], _).
disjoint([X|Xs], Ys):-
  \+ member(X, Ys), 
  disjoint(Xs, Ys).

/* for(I, J, K) is true if K is an integer between I and J inclusive.      */
for(I, J, I):-I =< J.
for(I, J, K):-I < J, I1 is I + 1, for(I1, J, K).

/* integers(M, N, Is) is true if Is is the list of integers from M to N    */
/*   inclusive.                                                            */
integers(N, N, [N]):-!.
integers(I, N, [I|Is]):-I < N, I1 is I + 1, integers(I1, N, Is).

/* is_set(Xs) is true if all the elements of the list Xs are distinct.     */
is_set([]).
is_set([X|Xs]):-nonmember(X, Xs), is_set(Xs).

/* is_sorted(Xs) is true if the elements of the list Xs are in ascending   */
/*   order.                                                                */
is_sorted([]).
is_sorted([_]).
is_sorted([A,B|Xs]):-A =< B, is_sorted([B|Xs]).

/* ith_element(Ys, I, Z) is true if Z is the I-th (base 0) element of the  */
/*   list Ys.                                                              */
ith_element(Ys, Y, I):-ith_element_1(Ys, Y, 0, I).

ith_element_1([Y|_], Y, I, I).
ith_element_1([_|Ys], Z, I0, I):-I1 is I0 + 1, ith_element_1(Ys, Z, I1, I).

/* joint(Xs, Ys) is true if the sets of elements in lists Xs and Ys have   */
/*   at least one common element.                                          */
joint(Xs, Ys):-member(X, Xs), member(X, Ys), !.

/* last(Xs, Y) is true if Y is the last element of the list Xs.            */
last([X|Xs], Y):-last_1(Xs, X, Y).

last_1([], Y, Y).
last_1([X|Xs], _, Y):-last_1(Xs, X, Y).

/* length(Xs, L) is true if L is the number of elements in the list Xs.    */
% length(Xs, L):-length_1(Xs, 0, L).

/* length_1(Xs, L0, L) is true if L is equal to L0 plus the number of      */
/*   elements in the list Xs.                                              */
% length_1([], L, L).
% length_1([_|Xs], L0, L):-L1 is L0 + 1, length_1(Xs, L1, L).
  
/* max(List, Max) is true if Max is the largest element in List.           */
max([X|Xs], Y):-max_1(Xs, X, Y).

max_1([], X, X).
max_1([Y|Ys], X, Z):-Y >= X, !, max_1(Ys, Y, Z).
max_1([_|Ys], X, Z):-max_1(Ys, X, Z).

/* maximum(X, Y, Z) is true if Z is the maximum of the numbers X and Y.    */
maximum(X, Y, Z):-X >= Y, !, Z = X.
maximum(_, Y, Y).

/* member(X, Ys) is true if the element X is contained in the list Ys.     */
% member(X, [X|_]).
% member(X, [_|Ys]):-member(X, Ys).

/* merge(Xs, Ys, Zs) is true if Zs is the result of merging the two lists  */
/*   Xs and Ys.                                                            */
merge([], [], []).
merge([X|Xs], [Y|Ys], [X,Y|Zs]):-merge(Xs, Ys, Zs).

/* min(List, Min) is true if Min is the smallest element in List.          */
min([X|Xs], Y):-min_1(Xs, X, Y).

min_1([], X, X).
min_1([Y|Ys], X, Z):-Y =< X, !, min_1(Ys, Y, Z).
min_1([_|Ys], X, Z):-min_1(Ys, X, Z).

/* minimum(X, Y, Z) is true if Z is the minimum of the numbers X and Y.    */
minimum(X, Y, Z):-X =< Y, !, Z = X.
minimum(_, Y, Y).

/* nonmember(X, Xs) is true if X is not a member of the list Xs.           */
nonmember(_, []).
nonmember(X, [Y|Ys]):-X \= Y, nonmember(X, Ys).

/* remove(X, Ys, Zs) is true if Zs is the result of removing one           */
/*   occurrence of the element X from the list Ys.                         */
% remove(X, [X|Ys], Ys).
% remove(X, [Y|Ys], [Y|Zs]):-remove(X, Ys, Zs).

/* prefix(Xs, Ys) is true if Xs is a leading sublist of Ys.                */
prefix([], _).
prefix([X|Xs], [X|Ys]):-prefix(Xs, Ys).

/* repeat/0 always succeeds.                                               */
% repeat.
% repeat:-repeat.

/* rest(X, Ys, Zs) is true if X is a member of the list Ys, and the list   */
/*   Zs is the rest of the list following X.                               */
rest(X, [X|Ys], Ys).
rest(X, [_|Ys], Zs):-rest(X, Ys, Zs).

/* reverse(Xs, Ys) is true if Ys is the result of reversing the order of   */
/*   the elements in the list Xs.                                          */
% reverse(Xs, Ys):-reverse_1(Xs, [], Ys).

% reverse_1([], As, As).
% reverse_1([X|Xs], As, Ys):-reverse_1(Xs, [X|As], Ys).

/* same_length(Xs, Ys) is true if the lists Xs and Ys contain the same     */
/*   number of elements.                                                   */
same_length([], []).
same_length([_|Xs], [_|Ys]):-same_length(Xs, Ys).

/* set(Xs, Ys) is true if Ys is the list of the elements appearing in Xs   */
/*   without duplication.  The elements in Ys are in the reverse order of  */
/*   Xs with the first duplicate values being kept.                        */
set(Xs, Ys):-set_1(Xs, [], Ys).

set_1([], As, As).
set_1([X|Xs], As, Ys):-member(X, As), !, set_1(Xs, As, Ys).
set_1([X|Xs], As, Ys):-set_1(Xs, [X|As], Ys).

/* shorter(Xs, Ys) is true if the list Xs contains fewer elements than the */
/*   list Ys.                                                              */
shorter([], [_|_]).
shorter([_|Xs], [_|Ys]):-shorter(Xs, Ys).

/* sublist(Xs, Ys) is true if Xs is a non-empty sublist of the list Ys.    */
sublist([X|Xs], [X|Ys]):-prefix(Xs, Ys).
sublist(Xs, [_|Ys]):-sublist(Xs, Ys).

/* subset(Xs, Ys) is true if the set of elements of Xs is a subset of the  */
/*   set of elements of Ys. Note that subset([1,1],[1,2,3]) is true.       */
subset([], _).
subset([X|Xs], Ys):-member(X, Ys), subset(Xs, Ys).

/* subst(Ls, X, Y, 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 Y.       */
subst([], _, _, []).
subst([X|Ls], X, Y, Ms):-!, Ms = [Y|Ns], subst(Ls, X, Y, Ns).
subst([L|Ls], X, Y, [L|Ms]):-subst(Ls, X, Y, Ms).

/* suffix(Xs, Ys) is true if Xs is a trailing sublist of the list Ys.      */
suffix(Xs, Xs).
suffix(Xs, [_|Ys]):-suffix(Xs, Ys).

/* sum(Xs, Y) is true if Y is the sum of the elements in the list Xs.      */
sum(Xs, Y):-sum_1(Xs, 0, Y).

sum_1([], A, A).
sum_1([X|Xs], A, Y):-B is X + A, sum_1(Xs, B, Y).

/* trim(Xs, Y, Zs) is true if Zs is the list Xs with all leading and       */
/*   trailing occurrences of Y removed.                                    */
trim(Xs, Y, Zs):-trim_left(Xs, Y, Ws), trim_right(Ws, Y, Zs).

/* trim_left(Xs, Y, Zs) is true if Zs is the list Xs with all leading      */
/*   occurrences of Y removed.                                             */
trim_left([Y|Xs], Y, Zs):-trim_left(Xs, Y, Zs), !.
trim_left(Xs, _, Xs).

/* trim_right(Xs, Y, Zs) is true if Zs is the list Xs with all trailing    */
/*   occurrences of Y removed.                                             */
trim_right([], _, []).
trim_right([Y|Xs], Y, []):-trim_right(Xs, Y, []), !.
trim_right([X|Xs], Y, [X|Zs]):-trim_right(Xs, Y, Zs).

LPA Index     Home Page

Valid HTML 4.01 Strict