Understanding Difference Lists
I'm trying to understand difference lists in Prolog, but I'm struggling to actually implement one properly, everytime I try to do it, I get a list of lists, but that's not what I want. I'm trying to implement an append predicate, but having little luck so far. Few attempts, all of which don't work.
app(X, Y, Z) :- Z = [X|Y].
?- app([a,b,c], [z], Z).
Z = [[a,b,c],z].
OR
app(X, Y, Z) :- Z = [X|Hole], Hole = Y.
Same results as the first one, (they do seem to be basically the same). I have an example in a book that does work (although it's not a predicate), and I don't understand the difference. X becomes instantiated to the proper answer [a,b,c,z], how is that much different than my second example?
X = [a,b,c|Y], Y = [z].
What am I missing? Thanks.
Answer
The key to understanding difference lists is understanding what they are on the level of the nested compound term that represents lists. Normally, we see a list like that:
[a, b, c]
This is now a list with three elements. The exactly same nested term using the dot as the list functor, ./2, and the atom [] as the empty list, would be:
.(a, .(b, .(c, [])))
It is important here that the list functor is a compound term with two arguments: the element and the rest of the list. The empty list is an atom, which, informally, could be seen as a compound 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 is the same as:
.(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 the tail:
[a, b|Tail]
which is the same as:
.(a, .(b, Tail))
Do you see how .(a, .(b, .(Last, []))) is not the same as .(a, .(b, Tail))?
Trying this on from the top-level (I am using SWI-Prolog 7, which needs the --traditional flag to treat the ./2 as the 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://www.swi-prolog.org for details.
For help, use ?- help(Topic). or ?- apropos(Word).
?- [a, b, Last] = [a, b|Tail].
Tail = [Last].
?- .(a, .(b, .(Last, []))) = .(a, .(b, Tail)).
Tail = [Last].
Now, a "difference list" is a list like this: [a, b|Tail], identical to .(a, .(b, Tail)), where you hold on the variable Tail that holds the tail. This is not a proper list until the Tail has been instantiated to a proper 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 understand what exactly Tail = [c, d, e] does in this conjunction.
In a predicate that uses a difference list, you need two arguments, or sometimes, a pair, to hold on to the incomplete list and its tail, like this:
% 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 has one, which is a "pair". Modern Prolog code seems to prefer two arguments to a pair, but you see the pair in textbooks and tutorials quite often.
To your append, or app/3: When you are working with difference lists, you need the extra argument (or a pair) so that you can access the tail of the list you are dealing with. If you only have the tail of the list that will be at the front, you can still write an append that only has three arguments, because all it takes is to unify the tail of the first list with the second list:
% app(List1, Tail1, List2)
app(List1, Tail1, List2) :- Tail1 = List2.
or unifying directly in the head:
app(_L1, L2, L2).
?- L1 = [a,b|Tail], app(L1, Tail, [c]).
L1 = [a, b, c],
Tail = [c].
This is the exact same code as in the link provided by @Wouter.
If you had the tails of both lists, you will 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 have done the unification in the head.
EDIT:
You can't make a "hole" once the list is already fully instantiated. How would you go from this .(a, .(b, .(c, []))) to this: .(a, .(b, .(c, Tail)))? You can't, except for traversting the list head to end and replacing the [] with Tail, but this is exactly what the ordinary 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 a diflist_append/3 defined as:
diflist_append(Front, Back, Back).
Which unifies the Back of 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?