% List concatentation:
% app(Xs,Ys,Zs) <=> Xs = [x1,...,xm] /\ Ys = [y1,...,ym] /\ Zs = [x1,...,xm,y1,..,yn]

app([]    ,Ys,Ys).
app([X|Xs],Ys,[X|Zs]) :- app(Xs,Ys,Zs).

% app([a,b],[c],[a,b,c])
%  |- 2nd rule:
% app([b],[c],[b,c])
%  |- 2nd rule:
% app([],[c],[c])
%  |- 1st rule:
% true!

% Complexity: linear in the length of the first list


%%%%%%%%%%%%%%% Relational applications of list concatenation:

% add an element at the end:
add_elem(Xs,X,XsX) :- app(Xs,[X],XsX).

% last element of a list:
last(Xs,X) :- app(_,[X],Xs).

% Is some element contained in a list:
member(X,Xs) :- app(_,[X|_],Xs).

% Delete some element in a list:
delete(L1,E,L2) :- app(Xs,[E|Ys],L1), app(Xs,Ys,L2).

% Is some list part of another list?
sublist(Xs,Ys) :- app(_,Bs,Ys), app(Xs,_,Bs).