Difference lists: Prolog tutorial

Appending to a normal list costs time proportional to its length: append/3 has to walk to the end. A difference list keeps a pointer to the end, so appending takes constant time.

The idea: represent a list as a pair Front-Back where Back is an unbound variable at the end of Front. [1,2,3|T]-T represents the list [1,2,3]: "the elements are whatever you get from the front up to T".

% append two difference lists: just connect the end of the first to the start of the second
dl_append(A-B, B-C, A-C).

?- dl_append([1, 2|T1]-T1, [3, 4|T2]-T2, Result)

A single fact, no recursion, no traversal. The "open" tail T2 is still unbound. To get a plain list, close it with []:

?- dl_append([1, 2|T1]-T1, [3, 4|T2]-T2, Result-[])

It works because Prolog variables can be bound later: the T1 hole in the first list is filled by the front of the second.

A queue

Difference lists make an efficient queue, add at the back, remove from the front, both constant time:

empty_queue(Q-Q).

enqueue(X, Front-[X|NewBack], Front-NewBack).

dequeue(X, [X|Front]-Back, Front-Back).

?- empty_queue(_Q0), enqueue(a, _Q0, _Q1), enqueue(b, _Q1, _Q2), enqueue(c, _Q2, _Q3), dequeue(X, _Q3, _Q4), dequeue(Y, _Q4, _)

(Variables starting with an underscore, like \_Q0\, are not printed, handy for intermediate values.)

The connection to DCGs

A DCG rule a --> b, c. is translated into a(S0, S) :- b(S0, S1), c(S1, S)., each non-terminal takes a list and returns what's left over, exactly like a difference list S0-S. That's why DCG parsing is efficient: concatenation costs nothing.

The reverse/3 accumulator idiom you saw in the recursion lesson is a cousin of the same idea: build the answer by passing the "unfinished" part along.

Exercise: Flatten with a difference list

Write flatten_dl(Tree, List) that collects the leaves of a nested list in order, using a difference-list helper so no append is needed. Provide the helper flat(Tree, List, Tail):

an empty list [] adds nothing;
a list [H|T] flattens H then T;
anything else is a leaf, added to the front.

For example flatten_dl([1, [2, [3, 4]], 5], L) gives L = [1, 2, 3, 4, 5].