From foldl to difference lists

Most declarative languages have lists. Usually this lists are either a nil atom (empty list) or a cons (a couple whose second element is a list). It is easy to see how we can append things to the head of the list.

In my former article we explored lists and foldl. Indeed, it is clear that we need an accumulator because appending at the end of the list is basically not possible (with decent performance). Appending at the end of the list means copying the whole list. Why? Consider how lists are done.

You have the head (say X1) and a pointer to another list. And this other list is built in the very same way. The last element has a pointer to an empty list.








If we want to add something at the end (even though we had a magical last::[E] --> E
function which got to the last element of a list in O(1) time) we need to "modify" the last element in the process. Since modifying is not allowed, we need to create another last element whose car (first element) is 3 (following our example) and whose second element (cdr) is a cons(4, []). Of course, at this point we should modify another element in the list. Basically we need to create a copy of the list. That's O(N).

However, if we bound the cdr of the last element not to an empty list but to an "unbound variable" we could simply add at the end cons(4, Unbound2), binding the Unbound1 to cons(3, Unbound1). Amazing... there are two major drawbacks.

First, we need logical variables. Which is simply true if we are using Prolog or Oz (sorry, no Erlang this time). In Erlang/Haskell you just can't do almost anything with unbound variables. In Prolog you can.

The second problem is our magical last function. We can build such a function, though it runs O(N). We can't do better. That means that appending at the end of a list, even though we left the tail of the list unbound, costs a lot. Well, usually O(N) is good, the point is that this operation is very low level and if we got a lot of O(N) stuff in inner "loops" the algorithm will suck.

Now, let us get back to the reverse with accumulator.

standard_reverse(Xs, Ys) :- standard_reverse(Xs, [], Ys).
standard_reverse([X|Xs], Acc, Ys) :-
    standard_reverse(Xs, [X| Acc], Ys).
standard_reverse([], Ys, Ys).

Let us change the argument order:

standard_reverse2([X|Xs], Ys, Acc) :-
    standard_reverse2(Xs, Ys, [X| Acc]).
standard_reverse2([], Ys, Ys).

Ok, this change seems unimportant to say the least. Let us do a further modification: instead of using two arguments for the reverted list and for the accumulator, let us use one single argument which includes both. For example Reverted-Acc.

diff_reverse([X|Xs], Ys-Acc) :-
    diff_reverse(Xs, Ys-[X|Acc]).
diff_reverse([], Ys-Ys).

Extremely nice! Here we have difference lists. Difference lists are a subject difficult to master. Their declarative meaning is quite obvious (and I will explain it in the next paragraphs), however their procedural/operational meaning is quite messy.

Basically a difference list is a way to represent an ordinary list. For example the list [1, 2, 3] can be represented by the difference lists [1, 2, 3, a]-[a] or by the difference list [1, 2, 3, a, 4]-[a, 4] or by [1, 2, 3]-[] or in another thousand of different ways, the most interesting of which is [1, 2, 3|X]-X. Notice that the latter unifies which any of the others. The careful reader may have noticed that now we may have a way to get to the last element of the list in order to add stuff in O(1). But let's not jump to conclusions.

Any ordinary list L can be represented as L-[], so it's easy to build a difference list representing an ordinary list. Unfortunately this difference lists is fully specified (if L was).

A classical problem in Prolog is appending two lists. This should be an O(M) operation, where M is the length of the shortest list. In fact in Prolog it is O(N) where N is the length of the first list:

myappend([], Xs, Xs).
myappend([H|T], Xs, [H|Ys]) :-
    myappend(T, Xs, Ys).

Now, let's benchmark the thing:

?- time(myappend([1, 2, 3], [2, 5], L)).
% 4 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
L = [1, 2, 3, 2, 5].

?- time(myappend([1, 2, 3, a, b, c], [2, 5], L)).
% 7 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
L = [1, 2, 3, a, b, c, 2, 5].

However, we can do that in O(1) using difference lists:

append_dl(Xs-Ys, Ys-Zs, Xs-Zs).
?- time(append_dl([1, 2, 3, a, b, c|Xs]-Xs, [2, 5]-[], Z)).
% 1 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
Xs = [2, 5],
Z = [1, 2, 3, a, b, c, 2, 5]-[].

When applicable, this is very nice. There is not much more on difference lists, still having the ability to add elements at the end of a structure is great. How? Think about it:

push_back(X, L-[X|Xs]).
?- X = [1, 2|Xs]-Xs, time(push_back(3, X)).
% 1 inferences, 0.00 CPU in 0.00 seconds (0% CPU, Infinite Lips)
X = [1, 2, 3|_G305]-[3|_G305],
Xs = [3|_G305].

Now we know how to put new elements to the front or to the back of a difference lists. That means we can build a deque.