/* append */
append([],   Y,Y).
append([A|X],Y,[A|Z]) :- append(X,Y,Z).

/* naive reverse */
naive_reverse([],    []).
naive_reverse([A|L0],Lrev) :- 
    naive_reverse(L0,Lrev0), append(Lrev0,[A],Lrev).

/* append reverse */
reverse(L,Lrev) :-
    rev1(L,[],Lrev).
rev1([],   S,S).
rev1([A|L],S,Lrev) :-
    rev1(L,[A|S],Lrev).

/* list length, two versions */
lengthA([],    0).
lengthA([_|L0],N) :- lengthA(L0,N0), N is N0+1.

lengthB(L,N) :- lengthB(L,0,N).
lengthB([],    N, N).
lengthB([_|L0],N0,N) :- N1 is N0+1, lengthB(L0,N1,N).

/* insertion sort */
inssort([],    []).
inssort([X|L0],S) :- inssort(L0,S0), insert(X,S0,S).
insert(X,[],[X]).
insert(X,[Y|L], [X,Y|L]) :- X=<Y.
insert(X,[Y|L0],[Y|L])   :- X>Y, insert(X,L0,L).

/* quicksort */
quicksort(Xs,Ys) :- qsort(Xs,Ys,[]).
qsort([],    Ys, Ys).
qsort([X|Xs],Ys0,Ys3) :- 
% part(X,Xs,S,L), qsort(S,Ys0,[X|Ys2]), qsort(L,Ys2,Ys3).
  part(X,Xs,S,L),
  qsort(S,Ys0,Ys1), Ys1=[X|Ys2], qsort(L,Ys2,Ys3).

part(_,[],    [],[]).
part(A,[X|Xs],[X|S],L) :- A>=X, part(A,Xs,S,L).
part(A,[X|Xs],S,[X|L]) :- A< X, part(A,Xs,S,L).

/* palindrome generation */
element(a).  element(b).  element(c).
palindrome(L) :- palin(L,[]).
palin(L,    L).
palin([X|L],L) :- element(X).
palin(L0,L3) :-
    element(X), L0=[X|L1], palin(L1,L2), L2=[X|L3].