3

空列表……对于像我这样的 Prolog 初学者来说很奇怪。我会说不可能将空列表写[]为差异列表T1-T2，就像不可能将原子写为差异列表一样。但是，我猜想要使用递归，必须有一种方法可以[]在差异列表设置中使用。我已经谷歌了，但我找不到答案，而 Bratko（人工智能的 Prolog 编程）只是简单地触及了这个主题。

那么，是否可以在 Prolog 中编写一个空列表作为差异列表，如果可以，它如何以及何时有用？

4

2 回答 2

5

理解这个主题的问题通常是由于使用了误导性的术语。

如tutorial.pdf尤其是pap95.pdf中所推荐的，例如使用list difference或简单的 difference。

教初学者 Prolog的第 5 节包含了相关的原因。

空列表由atom []唯一表示。

请注意，列表差异始终意味着对两个列表进行推理，并且由于单个列表和多个列表之间的这种分类差异，您最多可以找到一些对应关系或类比，但不能在空列表和列表差异之间找到同一性。

我完全支持上述论文中表达的观点，即你应该专注于使用 DCG，至少一开始是这样。明确地推理差异将在以后自然而然地出现。

于 2017-01-11T13:58:36.750 回答
0

附加两个列表差异意味着第一个差异的结束指针与第二个差异的头部的统一。对于常规列表，它需要追溯第一个列表的整个列表结构。因此，右侧的重复连接对于列表差分技术是线性的，对于普通列表是二次的。

当所有预期的连接完成后，要将整个结构作为普通列表返回给调用者，我们只需将“结束指针”logvar 与[].

在 C 语言中，列表差异是单链表的一部分，我们在其中维护两个变量：它的头指针和尾指针：

// typedef struct { int payload; node* next } node;
typedef struct { node** head; node** tail } list_diff;

现在每个连接只是结束指针的赋值：

void diff_concat( list_diff* a, list_diff* b)
{
    *(a -> tail) -> next = *(b -> head);
    a -> tail = b -> tail;
}

最终确定是

void diff_finalize( list_diff* a)
{
    *(a -> tail) = NULL;  // or some sentinel value, whatever
}

在 Prolog 中，我们可以将其表示为二进制术语-/2，例如-(A,B)或A-B。

但是（就像在 C 中一样）实际上不需要在内存中构建一个实际的结构来保存两个指针。我们可以单独维护两个 logvar。或者让 DCG 为我们做这件事。

以上是对列表差异技术的励志介绍，“它们有什么用？”。它也清楚地表明空差的表示是

list_diff* d;
*(d -> head) = *(d -> tail);

或者在 Prolog 中，一对相互统一的 logvar：L-L, var(L). 要了解原因，请查看当空 diff 在其右侧附加一些其他 diff 时会发生什么（我们总是在右侧附加内容，从而以自上而下的方式增长列表）。我的 C 可能在这里关闭，想法是通过设置尾部附加到空差异也将更新其头部。

于 2017-01-13T16:44:44.283 回答