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?

Ellon

Thanks to all for timely answers. – Ellon

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

Howarth

Why is append/3 not defined as: append(I-M, M, I). ? My understanding of I-M is that it means I is a list who's tail is M. Your defintion and this en.wikibooks.org/wiki/Prolog/Difference_Lists are more comlicated. Why? – Despumate

@Despumate In Prolog, a list with head H and tail M is expressed using the . functor as '.'(H,T), or more commonly with the syntax [H|T]. I-M doesn't have a semantic meaning with respect to lists. It is merely a diadic functor, -, with two arguments, I and M, or can be written, '-'(I,M). In the above answer, I could have just as easily used another diadic functor which is defined as a binary operator, such as + instead of -, and the behavior would be identical. – Howarth

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.

Hanford

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...

Rame

actually, the 3rd and 4th arguments to lists:reverse/4 form a difference list which starts up empty (B-B) and is lengthened by one non-constrained element on each step, so 4th arg represents progressive tails of the 3rd. :) – Fawkes