1

我是 Prolog 的新手，我正在为大学考试学习它，我们使用 SWI Prolog

我有一些问题要理解这个简单的程序如何工作，如果列表 S 是列表 L 的子列表，则说 TRUE ，否则说谓词是 FALSE。

我有以下解决方案，但我有一些问题要理解它的声明性含义

读这本书，我想我有一些想法，但我不确定......

这是使用连接的解决方案：

sublist(S,L) :- conc(L1, L2, L),
            conc(S, L3, L2).

conc([],L,L).

conc([X|L1],L2,[X|L3]) :- conc(L1,L2,L3).

如果第三个列表是第一个和第二个列表的串联，则此解决方案使用另一个响应 TRUE 的小程序。

要说 L 的 S i 子列表是否必须为 TRUE，以下两个条件：

  1. L 必须是一个列表，它是 L1 和 L2 的串联
  2. L2 必须是一个列表，它是S（我的子列表，如果存在于 L 列表中）和另一个列表 L3的串联

这是书的解释，但对我来说只是有点晦涩...

我试图对此进行推理并尝试理解真正深刻的含义......

所以我认为，在某种程度上，它就像使用这个其他程序来搜索一个元素是否是列表的成员：

member2(X, [X|_]).

member2(X,[_|T]):- member2(X,T).

在这个程序中，我只是说如果 X 是列表顶部的元素（它的头部），那么 X 在列表中并且程序响应为真。否则，如果 X 元素不在列表的顶部（或者它不是我的解决方案），我会尝试在此列表的 TAIL T 中搜索它。

回到子列表程序我认为推理是相似的

首先，我将 L 列表分解为两个列表 L1 和 L2（使用 conc 程序）**

然后我检查 S 和 L3 的串联是否是 L2 列表。

如果展位这些条件为真，则 S 是 L 的子列表

我认为 L1 列表与我从成员程序中的列表中提取的 X 元素具有相似的作用。

由于子列表 S 可以从列表 L 的开头开始，因此 L1 可以是 [] 并且我可以在 L1=[] 和 L2 的串联中分解 L，并且我可以尝试在 S 和 L3 中分解 L2。

如果我能做最后的分解，那么程序结束，我可以说 S 是原始列表 L 的子列表是真的

如果conc(S, L3, L2)不正确，则 ddo 回溯并采用另一个计算分支

我的声明式解释是否正确？

我在这个例子中发现了很大的困难，我也试图找到一个程序解释（使用 Prolog shell 中的操作跟踪）但我有很大的问题，因为计算量对于一个简短的列表来说也是如此之大......

4

1 回答 1

1

本书的解释更具说明性，因为它没有调用 Prolog 的搜索机制。我可能会用更多的下划线来写这个：

sublist(S, L) :- append(_, Suffix, L), append(S, _, Suffix).

这至少让 S 和 L2（改名为 Suffix）的关系更加清晰了一些。我们想说的是，这很难用声明性英语表达清楚，如果 L 的后缀名为 Suffix 并且 S 是 Suffix 的前缀，则 S 是 L 的子列表。命名其他成分只会增加混乱。Prolog 将在内部命名这些变量并与它们统一一些东西，因为它试图统一其他所有东西，但它不会与调用者共享该信息。尽管这些变量在某种意义上需要存在，但它们与您的公式没有密切关系，或者它们不会是单例。每当您收到单例变量警告时，请将变量替换为下划线。它将增加清晰度。

碰巧因为涉及的前缀和后缀可以是空列表，所以 S 可以是 L 的适当前缀或 L 的适当后缀，一切都会好起来的。

的声明性阅读member/2，作为参考，如果 X 是列表的头部或 X 是列表尾部的成员，则 X 是列表的成员。仔细注意缺少的内容：提到检查、成功或失败，或者实际上是任何操作顺序。如果X 是尾部的成员或头部的成员，则同样可以说X 是列表的成员。让计算机执行计算必须按照一定的顺序完成，这只是生活中不可避免的事实，所以你必须以正确的顺序告诉 Prolog 事情，否则它将进入无限循环，但这不是逻辑，只是 Prolog。

正如我们已经多次讨论过的，当您调用 Prolog 的机制时，您不再处于声明式阅读中。因此，当您说“首先我分解...”时，您已经离开了声明性世界并进入了程序性世界。声明性世界没有步骤，即使 Prolog 必须按照特定顺序执行操作才能在现实生活中的计算机上执行计算。同样，在声明式阅读中，您不会检查事物，它们只是存在或不存在。backtrack这个词也不能作为陈述性阅读的一部分出现。你应该在陈述性阅读中使用的唯一“动词”是“存在”动词“是”。

也就是说，您的 Prolog/程序读数是完全正确的。

于 2013-03-25T16:27:30.947 回答