list - 理解 Prolog 的空列表

Question

我正在阅读 Bratko 的Prolog:人工智能编程。对我来说，理解列表最简单的方法是将它们可视化为二叉树，这很顺利。但是，我对空列表 [] 感到困惑。我觉得有两层含义。

1. 当列表或枚举的一部分时，它被视为实际的(空)列表元素(因为在树中的某个位置它是某个 Head 的一部分)，例如[a，[]]
2. 当它是 Tail 中唯一的项目时，它不是一个元素，它实际上是什么都没有，例如[a|[]]

我的问题是我看不到 2 背后的逻辑。为什么列表需要将这种可能的“无”作为最终尾部？仅仅因为树必须是二元树？还是还有其他原因？ (换句话说，为什么 [] 在 1 中被算作元素，但在 2 中的 Tail 中却不是？)此外，是否存在最终(最右边、最深的元素)被算作元素的情况？ )树的最终节点不是“无”？

Answer 1

In other words, why is [] counted as an element in 1. but it isn't when it is in a Tail in 2?

这是两件不同的事情。 Prolog 中的列表是(退化的)二叉树，但也非常类似于具有指针的语言(例如 C)中的单链表。

在 C 中，您将拥有一个包含两个成员的 struct:值和指向下一个列表元素的指针。重要的是，当指向下一个的指针指向哨兵时，这就是列表的末尾。

在 Prolog 中，您有一个参数为 2 的仿函数:./2，它保存第一个参数中的值，列表的其余部分保存在第二个参数中:

.(a, Rest)

Prolog 中列表的哨兵是特殊的[]。这不是列表，而是空列表!传统上，它是一个原子，或者是一个元数为0的仿函数，如果你愿意的话。

在你的问题中:

• [a, []] 实际上是 .(a, .([], []))
• [a|[]] 实际上是 .(a, [])

这就是为什么:

?- length([a,[]], N).
N = 2.

现在这是一个包含两个元素的列表，第一个元素是 a，第二个元素是空列表 []。

?- [a|[]] = [a].
true.

这是一个包含单个元素 a 的列表。尾部的 [] 只是关闭列表。

问题:.([], [])是什么样的列表？

Also, are there cases where the final (rightmost, deepest) final node of a tree is not ‘nothing’?

是的，你可以在那里留下一个自由变量；然后，列表末尾有一个“洞”，您可以稍后填写。像这样:

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

这个有用吗？我不确定。例如，您可以获得一个重复 a, b, c 且长度为 7 的列表，如下所示:

?- 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 中，至少有许多函数“回收”较短的向量，因此这可能是一个有效的用例。

参见this answer有关差异列表的讨论，通常称为上一个示例中的 A 和 Rest。

参见this answer使用差异列表实现队列。