了解 Prolog 的空列表

Question

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

当列表或枚举的一部分时，它被视为一个实际的（空）列表元素（因为在树的某处它是某个 Head 的一部分），例如[a, []]
当它是 Tail 中的唯一项目时，它不是一个元素，它实际上是 nothing，例如[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：值和指向下一个列表元素的指针。重要的是，当指向 next 的指针指向一个哨兵时，这就是列表的末尾。

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

.(a, Rest)

Prolog 中列表的标记是特殊的 []。这不是列表，它是空列表！传统上，它是一个 atom，或者如果你愿意的话，它是一个元数为 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’?

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

?- 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 中至少有许多函数 "recycle" 更短的向量，所以这可能是一个有效的用例。

请参阅 this answer 了解关于差异列表的讨论，这就是上一个示例中的 A 和 Rest 通常的名称。

有关使用差异列表实现队列的信息，请参阅。

Answer 2

您的困惑来自于列表是根据一种特殊的人性化格式打印（和阅读）的。因此：

[a, b, c, d]

... 是 .(a, .(b, .(c, .(d, [])))).

的语法糖

. 谓词表示两个值：存储在列表和子列表中的项目。当 [] 出现在 data 参数中时，它被打印为数据。换句话说，这个：

[[], []]

... 是 .([], .([], [])) 的语法糖。最后一个 [] 没有打印出来，因为在那个上下文中它不需要打印。它仅用于标记当前列表的结尾。其他[]是存储在主列表中的列表。

I understand that but I don't quite get why there is such a need for that final empty list.

最后的空表是约定俗成的。它可以写成 empty 或 nil（如 Lisp），但在 Prolog 中，这由 [] 原子表示。请注意，在序言中，您可以不实例化子列表部分，例如：

[a | T]

等同于：

.(a, T)

这些被称为 difference lists。

Answer 3

您对 1. 和 2. 的理解是正确的 - "nothing" 您的意思是，元素方面。是的，一个空列表里面什么都没有（即没有元素）。

有一个特殊的哨兵值SENTINEL = []来标记cons-cells链的结束背后的逻辑，如[1,2,3] = [1,2|[3]] = [1,2,3|SENTINEL] = .(1,.(2,.(3,SENTINEL)))，与某些临时编码相反，如 .(1,.(2,3)) = [1,2|3]，是 类型一致性 。我们希望 cons 单元的第一个字段（或者，在 Prolog 中，. 函数项的第一个参数）总是被视为 "a list's element"，并且第二个——如"a list"。这就是为什么 [1, []] 中的 [] 算作列表的元素（因为它显示为 .-函子复合项的第一个参数），而 [=22] 中的 [] =] 没有（因为它显示为此类术语的 2nd 参数）。

是的，树必须是二进制的——即用于编码列表的仿函数 . 是二进制的——所以我们应该把什么放在那里最后一个节点的 tail 字段，这会告诉我们它是实际上是链的最后一个节点？它必须是某种东西，一致且易于测试。而且它还必须代表空列表，[]。所以用空列表的表示来表示列表的空尾才合乎逻辑。

是的，有一个非[] final "tail" 是完全有效的，就像在 [1,2|3] 中一样，这是一个完全有效的 Prolog term——它只是不是列表的表示{1 2 3}，正如 Prolog 的其他内置函数所理解的那样。

了解 Prolog 的空列表

Understanding Prolog's empty lists

list

prolog

empty-list