prolog - “开放式列表”和“差异列表”之间的区别

Question

“开放式列表”和“差异列表”有什么区别？

score 5 · Accepted Answer

正如http://homepages.inf.ed.ac.uk/pbrna/prologbook/node180.html上所解释的，开放列表是一种用于实现差异列表的工具。

打开列表是在列表中的某个位置有未分配变量的任何列表，例如：[a,b,c|X]. 您可以使用开放列表来实现称为差异列表的数据结构，它正式指定了指向第一个元素和开放端的两个术语的结构，传统上定义为：[a,b,c|X]-X，以便更轻松地对此类列表进行操作。

例如，如果您只有一个开放列表，则可以在末尾添加元素，但您需要遍历所有项目。在差异列表中，您可以只使用列表末尾变量（Hole在上面的页面上称为 a）来跳过迭代并在恒定时间内执行操作。

score 3 · Accepted Answer

3

例如

开放式：[a,b,c | _]

差异列表：[a,b,c|U]-U。

于 2012-12-27T17:16:25.497 回答

score 3 · Accepted Answer

这两个概念似乎都是列表，但实际上它们不是。一个是具体的术语，另一个是约定俗成的。

开放式列表、部分列表

开放式列表是不是列表但可以实例化以使其成为列表的术语。在标准术语中，它们被称为部分列表。这里是部分列表：X, [a|X],[X|X]都是部分列表。

开放式列表的概念建议使用此类列表来模拟某些开放式状态。想一想可能由一个开放式列表表示的字典。每次添加新项目时，“部分列表末尾”的变量都会被实例化为一个新元素。虽然这种编程技术在 Prolog 中是完全可行的，但它有一个很大的缺点：程序将严重依赖于过程解释。而且在许多情况下，根本无法进行声明性解释。

差异列表实际上不是列表本身，而是列表的某种使用方式，以便预期列表由两个变量表示：一个用于列表的开头，一个用于列表的结尾。出于这个原因，谈论列表差异而不是差异列表会很有帮助。

考虑：

el(E, [E|L],L).

在这里，最后两个参数可以看作是形成了一个区别：一个包含单个元素的列表[E]。您现在可以从更简单的列表中构造更复杂的列表，前提是您尊重某些约定，这些约定本质上是第二个参数仅被进一步传递。这样的差异永远不会相互比较！

el2(E, F, L0,L) :-
   el(E, L0,L1),
   el(F, L1,L).

请注意，这只是一个约定。这些列表没有被强制执行。考虑到：

?- el2(E, F, L, nonlist).
L = [E,F|nonlist].

该技术也用于编码dcg s。