The key to understanding lists of differences is understanding that they are at the level of an embedded compound term that represents lists. Usually we see a list like this:
[a, b, c]
Now this is a list with three items. The exact same nested term using a dot as a ./2 list ./2 and an atom [] as an empty list would be:
.(a, .(b, .(c, [])))
It is important here that the list functor be a compound term with two arguments: an element and the rest of the list. An empty list is an atom, which, unofficially, can be considered as a composite term with arity 0, that is, without arguments.
Now this is a list with three elements, where the last element is a free variable:
[a, b, Last]
which matches with:
.(a, .(b, .(Last, [])))
This, on the other hand, is a list with two elements and a free variable as the rest of the list or tail:
[a, b|Tail]
which matches with:
.(a, .(b, Tail))
You see that .(a, .(b, .(Last, []))) does not match .(a, .(b, Tail)) ?
Try this from the top level (I use SWI-Prolog 7, which needs the --traditional flag to handle ./2 as a list term):
$ swipl --traditional Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.1.26) Copyright (c) 1990-2014 University of Amsterdam, VU Amsterdam SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, and you are welcome to redistribute it under certain conditions. Please visit http:
Now the “list of differences” is a list like this: [a, b|Tail] , identical to .(a, .(b, Tail)) , where you hold the Tail variable that holds the tail. This is not a valid list until a Tail has been created in the corresponding list!
?- L = [a, b|Tail], is_list(L). false. ?- L = [a, b|Tail], Tail = [c,d,e], is_list(L). L = [a, b, c, d, e], Tail = [c, d, e].
You can look at the previous queries to see what exactly Tail = [c, d, e] does in this regard.
In a predicate that uses a list of differences, you need two arguments , and sometimes a pair , to hold the incomplete list and its tail, for example
% using two arguments foo([a,b|Tail], Tail). % using a pair foo([a,b|Tail]-Tail).
The first foo/2 has two arguments, the second one, which is a "pair". Modern Prolog code seems to prefer two arguments for a pair, but you often see a pair in textbooks and textbooks.
To your addition, or app/3 : when you are working with difference lists, you need an additional argument (or a pair) so that you can access the tail of the list you are dealing with. If you have only the tail of the list that will be in front, you can still write an application containing only three arguments, because all that is required is to combine the tail of the first list with the second list:
% app(List1, Tail1, List2) app(List1, Tail1, List2) :- Tail1 = List2.
or combining directly to the head:
app(_L1, L2, L2). ?- L1 = [a,b|Tail], app(L1, Tail, [c]). L1 = [a, b, c], Tail = [c].
This is the same code as the link provided by @Wouter.
If you had the tails of both lists, you replace the tail of the first list with the second list and keep the tail of the second list.
app(List1, Tail1, List2, Tail2) :- Tail1 = List2.
Again, you could do a pool in your head.
EDIT
You cannot make a “hole” as soon as the list has been completely created. How would you go from this .(a, .(b, .(c, []))) to this:. .(a, .(b, .(c, Tail))) ? You cannot, with the exception of traversing the list to the end and replacing [] with Tail , but this is exactly what regular append/3 does. Try:
?- L = [a,b,c,d], append(L, Back, Front), Back = [x,y,z]. L = [a, b, c, d], Back = [x, y, z], Front = [a, b, c, d, x, y, z].
Or, if you have diflist_append/3 , which is defined as:
diflist_append(Front, Back, Back).
Which combines the Back list with the third argument:
?- L = [a,b,c,d], append(L, Back, Front), diflist_append(Front, Back, [x,y,z]). L = [a, b, c, d], Back = [x, y, z], Front = [a, b, c, d, x, y, z].
As for your example, X = [a,b,c], Y = [X|Z], Z = [z] , this is the same as:
X = .(a, .(b, .(c, []))), Y = .(X, Z), % Y = .(.(a, .(b, .(c, []))), Z) Z = [z] % Y = .(.(a, .(b, .(c, []))), .(z, []))
So, do you see it now?