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 = []

Answer 2

What you have there in your example is not a difference list. Compare http://en.wikibooks.org/wiki/Prolog/Difference_Lists. Difference lists use the trick of keeping the tail as a variable that is known and can be changed directly. Hence, it allows constant time appends to lists. But that is not what you are doing in your example.

Looking at your example then, rev1 really just uses - as a separator, as if it was a comma. I would reckon that the only difference then is that in rev2, the prolog interpreter has a chance to index the rules in a way that improves performance. Not sure whether in this case it would make any difference though. Aesthetically speaking, the second solution seems a lot cleaner to me as well.

Answer 3

I've never seen difference lists used 'out-of-context', and the main context is DCGs implementation.

Here is a DCG based reverse (well, I wrote by myself, but you can find it also in the page linked by Christian).

reverse3(L,R) :- phrase(rev3(L),R).
rev3([]) --> [].
rev3([H|T]) --> rev3(T),[H].

Listing it evidences how your reverse2 is nearly identical:

?- listing(rev3).
stackoverflow:rev3([], A, A).
stackoverflow:rev3([D|A], B, E) :-
    rev3(A, B, C),
    C=[D|E].

All these definitions share a problem: they loops when used in 'backward' mode, on backtracking after the first solution:

?- reverse1(R,[a,b,c]).
R = [c, b, a] ; (^C here)
Action (h for help) ? abort
% Execution Aborted

It's interesting then to look at the proper, efficient, library implementation:

?- listing(reverse).
lists:reverse(A, B) :-
    reverse(A, [], B, B).

lists:reverse([], A, A, []).
lists:reverse([B|A], C, D, [_|E]) :-
    reverse(A, [B|C], D, E).

No difference lists here!

Then, about your question, I would say that the only benefit from difference lists is a better understanding of Prolog...