% complexity: linear in the length of the first argument
app([],    Ys,Ys).
app([X|Xs],Ys,[X|Zs]) :- app(Xs,Ys,Zs).


% Concatenation on difference lists: one resolution step
app_dl(L-M, M-N, L-N).


% complexity: quadratic in the length of the first argument
rev([],    []).
rev([X|Xs],Zs) :- rev(Xs,Ys), app(Ys,[X],Zs).

rev_dl([],    L-L).
%rev_dl([X|Xs],L-M) :- rev_dl(Xs,UXs-TXs), app_dl(UXs-TXs, [X|R]-R, L-M).
rev_dl([X|Xs],UXs-R) :- rev_dl(Xs,UXs-[X|R]).

% two arguments instead of a difference list:
rev_dle([],    L,  L).
rev_dle([X|Xs],UXs,R) :- rev_dle(Xs,UXs,[X|R]).

% complexity: linear in the length of the first argument
revdl(L,R) :- rev_dle(L,R,[]).