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 Demonstration 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 Grammars 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. Examples One of the earlier examples, revappend, can be written using DCG: revappend([]) --> []. revappend([X|Xs]) --> revappend(Xs), [X]. previous: Reading and Writing code next: Definite Clause Grammars