理解差异列表的关键是理解它们在表示列表的嵌套复合词的级别上是什么.通常，我们会看到这样的列表:

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]

这是一个包含三个元素的列表.使用点作为列表函子 ./2 和原子 [] 作为空列表的完全相同的嵌套项是:

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, [])))

在这里很重要的是，列表函子是一个带有两个参数的复合词:元素和列表的其余部分.空列表是一个原子，非正式地，可以将其视为具有 0 元数的复合词，即没有参数.

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]

等同于:

.(a, .(b, .(Last, [])))

另一方面，这是一个包含两个元素和一个***变量作为列表其余部分的列表，或者 tail:

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]

等同于:

.(a, .(b, Tail))

你看到 .(a, .(b, .(Last, []))) 和 .(a, .(b, Tail)) 不一样吗??

从顶层尝试这个(我正在使用 SWI-Prolog 7，它需要 --traditional 标志来将 ./2 视为列表术语):

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].

现在，差异列表"是这样的列表:[a, b|Tail]，等同于 .(a, .(b, Tail))，你持有变量 Tail 持有尾部.在 Tail 被实例化为一个正确的列表之前，这不是一个正确的列表！

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].

您可以查看前面的查询以了解 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).

第一个 foo/2 有两个参数，第二个有一个，这是一个对".现代 Prolog 代码似乎更喜欢两个参数而不是一对参数，但您经常在教科书和教程中看到这对参数.

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.

到您的附加或 app/3:当您使用差异列表时，您需要额外的参数(或一对)，以便您可以访问您正在处理的列表的尾部.如果你只有将在前面的列表尾部，你仍然可以编写一个只有三个参数的 append，因为只需要将第一个列表的尾部与第二个列表统一起来:

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.

或直接在头脑中统一:

app(_L1, L2, L2).

?- L1 = [a,b|Tail], app(L1, Tail, [c]).
L1 = [a, b, c],
Tail = [c].

这与@Wouter 提供的链接中的代码完全相同.

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.

编辑:

一旦列表已经完全实例化，你就不能制造洞".你会如何从这个 .(a, .(b, .(c, []))) 到这个: .(a, .(b, .(c, Tail)))?你不能，除了从头到尾遍历列表并将[]替换为Tail，但这正是普通的append/3代码> 确实如此.试试:

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].

或者，如果您将 diflist_append/3 定义为:

Or, if you have a diflist_append/3 defined as:

diflist_append(Front, Back, 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].

对于你的例子，X = [a,b,c], Y = [X|Z], Z = [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, []))

所以你现在看到了吗?