我正在阅读Bratko的Prolog：Programming for Artificial Intelligence。对我来说，理解列表的最简单方法是将它们可视化为二叉树，这很顺利。但是，我对空列表[]感到困惑。在我看来，它有两个含义。
- 当列表或枚举的一部分时，它被视为实际的(空)列表元素(因为树中的某个地方它是某个 Head 的一部分)，例如
[a, []] - 当它是尾巴中唯一的物品时，它不是一个元素，它实际上什么都不是，例如
[a|[]]
我的问题是我没有看到 2 背后的逻辑。为什么列表需要将这种可能的"虚无"作为最后的尾巴？仅仅因为树必须是二进制的？还是有其他原因？(换句话说，为什么[]在 1 中算作一个元素，但当它在 2 中的尾巴中时却不算？另外，是否存在树的最终(最右边，最深)最终节点不是"无"的情况？
换句话说，为什么 [] 在 1 中算作一个元素。 但不是当它在 2 的尾巴中时？
这是两回事。Prolog中的列表是(退化的)二叉树，但也非常像语言中的单向链表，比如C。
在 C 中，您将有一个包含两个成员的struct：值和指向下一个列表元素的指针。重要的是，当指向下一个的指针指向哨兵时，这是列表的末尾。
在 Prolog 中，你有一个带有 arity 2：./2的函子，它在第一个参数中保存值，在第二个参数中保存列表的其余部分：
.(a, Rest)
Prolog中列表的哨兵是特殊[]。这不是列表，而是空列表！传统上，它是一个原子，或者一个 arity 为 0 的函子，如果你愿意的话。
在您的问题中：
[a, []]其实是.(a, .([], []))[a|[]]其实是.(a, [])
这就是为什么：
?- length([a,[]], N).
N = 2.
现在这是一个包含两个元素的列表，第一个元素是a，第二个元素是空列表[]。
?- [a|[]] = [a].
true.
这是一个包含单个元素的列表，a.尾部的[]只是关闭列表。
问题：.([], [])什么样的列表？
另外，是否存在树的最终(最右边，最深)最终节点不是"无"的情况？
是的，你可以在那里留下一个自由变量;然后，你在列表的末尾有一个"洞"，你可以稍后填写。喜欢这个：
?- A = [a, a|Tail], % partial list with two 'a's and the Tail
B = [b,b], % proper list
Tail = B. % the tail of A is now B
A = [a, a, b, b], % we appended A and B without traversing A
Tail = B, B = [b, b].
您还可以创建循环列表，例如，包含无限多个x的列表将是：
?- Xs = [x|Xs].
Xs = [x|Xs].
这有用吗？我不确定。例如，您可以获得一个长度为 7 的重复a, b, c的列表，如下所示：
?- ABCs = [a,b,c|ABCs], % a list that repeats "a, b, c" forever
length(L, 7), % a proper list of length 7
append(L, _, ABCs). % L is the first 7 elements of ABCs
ABCs = [a, b, c|ABCs],
L = [a, b, c, a, b, c, a].
在 R 中，至少许多函数"回收"较短的向量，因此这可能是一个有效的用例。
有关差异列表的讨论，请参阅此答案，这是上一个示例中的A和Rest通常称为。
请参阅此答案，了解如何使用差异列表实现队列。
您的困惑来自这样一个事实，即列表是根据特殊的人类友好格式打印(和阅读)的。因此：
[a, b, c, d]
。是.(a, .(b, .(c, .(d, []))))的句法糖。
.谓词表示两个值：存储在列表中的项和子列表。当[]出现在data参数中时，它将打印为数据。 换句话说，这个：
[[], []]
。是.([], .([], []))的句法糖。 不会打印最后一个[]，因为在这种情况下不需要打印。它仅用于标记当前列表的末尾。其他[]是存储在主列表中的列表。
我理解这一点，但我不太明白为什么需要最后的空列表。
最后一个空列表是一个约定。它可以写empty或nil(如Lisp)，但在Prolog中，这是用[]原子表示的。 请注意，在 prolog 中，您可以不实例化子列表部分，如下所示：
[a | T]
这与：
.(a, T)
这些被称为差异列表。
你对 1. 和 2. 的理解是正确的——你所说的"无"是指元素方面。是的，空列表内部没有任何内容(即没有元素)。
具有特殊的哨兵值SENTINEL = []标记cons-cell链的末端背后的逻辑，如[1,2,3]=[1,2|[3]]=[1,2,3|SENTINEL]=.(1,.(2,.(3,SENTINEL)))，而不是一些临时编码，如.(1,.(2,3))=[1,2|3]，是类型一致性。我们希望 cons 单元格的第一个字段(或者在 Prolog 中，.函项的第一个参数)始终被视为"列表的元素"，第二个字段被视为"列表"。这就是为什么[]in[1, []]算作列表的元素(因为它显示为.-functored 复合项的第一个参数)，而[1 | []]中的[]则不算(因为它显示为该术语的第二个参数)。
是的，树必须是二进制的——即用于编码列表的函子.是二进制的——那么我们应该在最终节点的尾场中放什么，这将向我们发出信号，它实际上是链的最终节点？它必须是一致且易于测试的东西。并且它还必须表示空列表，[].因此，使用空列表的表示来表示列表的空尾是合乎逻辑的。
是的，有一个非[]的最终"尾巴"是完全有效的，就像在[1,2|3]中一样，这是一个完全有效的Prolog术语- 它只是不是列表{1 2 3}的表示，正如Prolog的其他内置所理解的那样。