Prolog difference list

Question

Consider the following programs, one using difference lists, and the other is not:

reverse1(List1,R) :- rev1(List1, R-[]).
rev1([], A-A).
rev1([H|T], C-A) :-rev1(T, C - [H|A]).

reverse2(List1,R) :- rev2(List1, R, []).
rev2([], A, A).
rev2([H|T], C, A) :- rev2(T, C, [H|A]).

Since both do the same thing, what is the benefit of using difference lists?

Answer 1

In the example given, reverse1 isn't using true difference list, but is just a different representation of reverse2. They both use the same variables in the same way. reverse uses a - functor to attach them and reverse2 maintains them as separate parameters. But that's all that's different between the two. The algorithm behaviors are the same.

A real difference list is a list structure with a "hole" in it, like X-T in which T is not instantiated (until a later point in time perhaps), and X contains T (e.g., [a,b,c|T]-T). The - functor in this associates the "exposed" uninstantiated variable with the structure that contains it.

A popular and simple example is an implementation of append using difference lists. A traditional, recursive implementation of append might look like this:

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

Simple enough, and execution time is proportional to the length of the first list.

Using difference lists, you can implement an append as follows:

append(A-B, B-C, A-C).

That's all you need to append lists using difference lists. No recursion or anything else. Execution time is O(1) independent of the length of the list. Here's an example execution:

append([1,2,3|T]-T, [4,5,6|W]-W, DL).

Yields:

DL = [1,2,3,4,5,6|W]-W
T = [4,5,6|W]

You can get to the concrete answer by "filling" the hole with an empty list in the last parameter:

append([1,2,3|T]-T, [4,5,6|W]-W, L-[]).

You get:

L = [1,2,3,4,5,6]
T = [4,5,6]
W = []