/* Mini-exercise -- reverse rule in CLP(R) using difference lists.

The obvious way of writing reverse uses append, and ends up copying the
result on every recursive call:

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

reverse([],[]).
reverse([X|Xs],Rs) :- reverse(Xs,Ys), append(Ys,[X],Rs).

Mini-exercise: write a reverse rule that uses difference lists to avoid
this excess copying.

Show the derivation tree for your rule for the following goal: 
  ?- reverse([1,2,3],As).
*/


/* solution is below -- see the separate scanned sheet for the derivation tree */

/* declare "\" as a new infix operator */
:- op(35,xfx,\).

reverse(Xs, Rs) :- reverse_dl(Xs, Rs\[]).

reverse_dl([], T\T).
reverse_dl([X|Xs], Rs\T) :- reverse_dl(Xs, Rs\[X|T]).