Prolog/Difference Lists

Definition

A Difference list in Prolog is a normal list except the very end of it is a logic variable, paired with that variable. For example:

 [a,b,c|E]-E

A common example to explain why they are useful is:

 append(I-M, M-O, I-O).

Given this clause one can query:

 ?- append([a,b,c|E]-E,  [x,y,z|W]-W,  O).
 E = [x, y, z|W],
 O = [a, b, c, x, y, z|W]-W.

Since this uses a single unification to append you have O(1) instead of O(n) complexity.

You can expect a DCG to expand into normal Prolog rules which use difference lists, for example.

?- expand_term(( o --> [a,b,c] ), E).
E = (o(I, O) :- I=[a, b, c|O]).

is a valid expansion.

One of the earlier examples, revappend, can be written using DCG:

revappend([]) --> [].
revappend([X|Xs]) --> revappend(Xs), [X].