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

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

% list concatenation with difference lists:
app_dl(L-M, M-N, L-N).

% complexity: linear of the length of arg 1
rev_dl([],L,L).
rev_dl([X|Xs],L,M) :- rev_dl(Xs,L,[X|M]).

revdl(Xs,Ys) :- rev_dl(Xs,Ys,[]).