:- module(_,_).

% Difference lists 
% ----------------

% Also known as open lists, incomplete lists, ...

% Try:

% ?- L = [1,2,3],
% A closed list; cannot easily add at the end.

% ?- L = [1,2,3|T].
% An incomplete list: we can add at the end by
% instantiating T!

% Create two difference lists L1 and L2 and append them:
% ``by hand'' 
% ?- L1 = [1,2,3|X], L2 = [3,4,5|Y], L2=X.

% A pseudo-type definition for difference lists:
dlist(X-X). 
dlist([_|DL]-X) :- dlist(DL-X).

% Try (ask for multiple solutions):
% ?- dlist(L).

% Appending difference lists (in constant time):

append_dl(B1-E1,E1-E2,B1-E2).

% Try: 
% ?- append_dl( [1,2,3|X]-X, [4,5|Y]-Y, L).
% L has the resulting (appended) diference list.
% But note that we have modified the tail of the 
% first list: we cannot append to it again.

% Checking:
% ?- append_dl( [1,2,3|X]-X, [4,5|Y]-Y, [1,2,3,4,5|Z]-Z).
% Substracting:
% ?- append_dl( L-X, [4,5|Y]-Y, [1,2,3,4,5|Z]-Z).
% ?- append_dl( L1-X, L2-Y, [1,2,3,4,5|Z]-Z).
% But only one solution!