Appending two list differences means just a unification of first diff's end pointer with the second one's head. With regular lists it requires retracing of the whole list structure of the first list. Thus repeated concatenation on the right is linear with the list difference technique, and quadratic with plain lists.
When all the intended concatenations are done, to return the whole structure as a plain list to a caller we just unify the "end pointer" logvar with [].
In C terms, list difference is a portion of singly-linked list where we maintain two variables: its head pointer but also its tail pointer:
// typedef struct { int payload; node* next } node;
typedef struct { node** head; node** tail } list_diff;
Now each concatenation is just an assignment of the end pointer:
void diff_concat( list_diff* a, list_diff* b)
{
*(a -> tail) -> next = *(b -> head);
a -> tail = b -> tail;
}
And finalization is
void diff_finalize( list_diff* a)
{
*(a -> tail) = NULL; // or some sentinel value, whatever
}
In Prolog we could represent it as a binary term like -/2, e.g. -(A,B) or A-B.
But (as in C also) there's no actual need to build an actual structure in memory just for holding the two pointers; we can just maintain two logvars individually. Or let DCGs do it for us.
The above was the motivational introduction to list difference technique, "what are they good for?". It also makes clear that the representation of empty difference is
list_diff* d;
*(d -> head) = *(d -> tail);
Or in Prolog, a pair of logvars unified with each other: L-L, var(L). To see why, see what happens when empty diff is appended with some other diff on its right (it is always on the right that we append things, thus growing the lists in the top-down manner). My C may be off here, the idea being that by setting the tail the appending to an empty diff will also update its head.
