append/3

Many procedures can be written using calls to append/3. They would, in general, be more efficient if written otherwise. Some examples are:

/* append(Xs, Ys, Zs) is true if Zs is the result of appending the list Xs */
/*   to the list Ys.                                                       */
/* (This is a built-in predicate in LPA Win-Prolog)                        */
% append([], Ys, Ys).
% append([X|Xs], Ys, [X|Zs]):-append(Xs, Ys, Zs).

/* first(Xs, X) is true if X is the first element of the list Xs.          */
first(Xs, X):-append([X], _, Xs), !.

/* last(Xs, X) is true if X is the last element of the list Xs.            */
last(Xs, X):-append(_, [X], Xs), !.

/* member_(X, Ys) is true if the element X is contained in the list Ys.    */
/* (I've changed the name because member/2 is a built-in predicate in LPA  */
/*   Win-Prolog)                                                           */
member_(X, Xs):-append(_, [X|_], Xs).

/* adjacent(P, Q, Xs) is true if the element P immediately precedes the    */
/*   element Q in the list Xs.                                             */
adjacent(P, Q, Xs):-append(_, [P,Q|_], Xs).

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

/* efface(Xs, Y, Zs) is true if Zs is the result of deleting one           */
/*   occurrence of the element Y from the list Xs.                         */
efface(Xs, Y, Zs):-append(As, [Y|Bs], Xs), append(As, Bs, Zs).

/* prefix(Xs, Ys) is true if Xs is a leading sublist of the list Ys.       */
prefix(Xs, Ys):-append(Xs, _, Ys).

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

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

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

/* joint(Xs, Ys) is true if the lists Xs and Ys have at least one common   */
/*   element.                                                              */
joint(Xs, Ys):-append(_, [X|_], Xs), append(_, [X|_], Ys), !.

/* rotate(Xs, Ys) is true if Ys is the result of rotating Xs.              */
rotate(Xs, Ys):-append(As, Bs, Xs), append(Bs, As, Ys), Bs = [_|_].

/* bubble_sort(Xs, Ys) is true if the list Ys is a sorted permutation of   */
/*   the list Xs.                                                          */
bubble_sort(Xs, Ys):-
  append(As, [P,Q|Bs], Xs),
  P > Q,
  append(As, [Q,P|Bs], Cs), !,
  bubble_sort(Cs, Ys).
bubble_sort(Xs, Xs).

/* naive_reverse(Xs, Ys) is true if Ys is the result of reversing the      */
/*   order of the elements in the list Xs.                                 */
naive_reverse([], []).
naive_reverse([X|Xs], Ys):-naive_reverse(Xs, As), append(As, [X], Ys), !.

/* median(Xs, X) is true if X is the median of the values in the ordered   */
/*   list Xs.                                                              */
median([X], X):-!.
median([X1,X2], X):-!, 
  X is (X1 + X2) / 2.
median([_|Xs], X):-
  append(Xs1, [_], Xs),
  !,
  median(Xs1, X).

/* checkorder_lists(Xs, Ys) is true if all the elements of the list Xs are */
/*   elements of the list Ys, and they are in the same order in the two    */
/*   list.                                                                 */
/* e.g. checkorder_lists([a,b,c],[a,d,e,b,f,g,c]). succeeds                */
/*      checkorder_lists([a,b,c],[a,d,e,c,f,g,b]). fails                   */
checkorder_lists([],_).
checkorder_lists([X|L1],L2):-
    append(_,[X|L3],L2),
    checkorder_lists(L1,L3).

/* palindrome(Xs) is true if Xs is a palindrome.                           */
/* e.g. palindrome([m,a,d,a,m, i,m, a,d,a,m]).                             */
palindrome([]).
palindrome([_]).
palindrome([X|Xs]):-append(Xs1,[X],Xs), palindrome(Xs1).

LPA Index     Home Page