app([],L,L).
app(L,[],L).
app([H|L1], L2,[H|L3]) :- app(L1,L2,L3).

app1([],L,L).
app1([H|L1],L2,[H|L3]) :- app1(L1,L2,L3).

mem(X, [X]).
mem(X,[_|L]):- mem(X,L).

rev([],[]).
rev([X],[X]).
rev([H|T],L):- rev(T,L1),app1(L1,[H],L).


rev1(L,R) :- rev1(L,[],R). /* 3-argument rev1 does all the work */
rev1([],L,L).
rev1([H|L1],L2,L) :- rev1(L1,[H|L2],L).

remove(X,[X|L],L).
remove(X,[A|Y],[A|Z]) :- remove(X,Y,Z).

perm([],[]).
perm([X|Y],Z) :- perm(Y,W),remove(X,Z,W). /*assumes distinct elements */

sort1([],[]).
sort1([X],[X]).
sort1(L,S) :- perm(L, S), sorted(S).
sorted([]).
sorted([_]).
sorted([X,Y|L]) :- X=<Y, sorted([Y|L]).