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 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.
Internal to Definite Clause GrammarsEdit
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].