4

我这里有一个小脚本，它将元素列表转换为集合。例如列表 [1,1,2,3] -> 设置 [1,2,3]。有人可以逐步向我解释这些程序中发生了什么吗？你能用我的 [1,1,2,3] -> [1,2,3] 例子吗？

list_to_set([],[]).

list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y),
    \+member(A,Y).

list_to_set([A|X],Y):-
   list_to_set(X,Y),
   member(A,Y).
4

4 回答 4

4

如果你看一个具体的例子，你很快就会被许多不相关的细节所淹没。如此之多，以至于您将忽略程序的重要属性。让我们看看下面的程序片段，它被称为故障片。false通过将目标添加到程序中，您将获得失败部分。失败切片与原始程序有许多有趣的属性。例如，Goal, false使用失败切片执行的目标永远不会使用比原始程序更多的推理。或者相反，原始程序将使用更多（或最多相同数量）的推理。所以，让我指出这样一个片段：

list_to_set([],[]) :-假。
list_to_set([A|X],[A|Y]):-
   list_to_set(X,Y), false ,
     \+member(A,Y)。
list_to_set([A|X],Y):-
   list_to_set(X,Y), false ,
    member(A,Y)。

而且由于这个片段不再对具体元素感兴趣（A不再使用，也不再member/2），我们可以使用length/2最通用的列表。通过这种方式，我们可以观察到每个长度所需的最少推理次数，如下所示：

?-长度（L，N），call_inferences（（list_to_set（L，_），false;true），Inf）。
N = 0，Inf = 3；
N = 1，Inf = 6；
N = 2, Inf = 12 ;
N = 3，Inf = 24；
N = 4，Inf = 48；
N = 5，Inf = 96；
N = 6，Inf = 192；
N = 7，Inf = 384；
N = 8，Inf = 768；
N = 9，Inf = 1536；
N = 10，Inf = 3072 ...

使用

:- meta_predicate user:call_inferences(0,-).
call_inferences( Goal, Inferences) :-
   statistics(inferences, Inferences0),
   Goal,
   statistics(inferences, Inferences1),
   Inferences is Inferences1 - Inferences0.

每增加一个元素，推理的数量就会增加一倍。也就是说，它们呈指数增长。因此，您的实现至少要花费成倍的推论……无需查看具体示例。

您的程序中还有更多问题：

?- L=[A,B],list_to_set(L,S), L = [a,b].

失败，而

?-  L=[A,B], L = [a,b], list_to_set(L,S).

成功。也就是说，您的程序不再是纯粹的关系。maplist(dif(A),Y)代替\+ member(A,Y). _

于 2013-01-23T13:35:01.597 回答
3

在 Prolog 的某些实现中，例如GNU Prolog，您可以跟踪代码的执行。使用此功能，您可以逐步完成评估过程，如下所示。

$ gprolog
GNU Prolog 1.4.2
By Daniel Diaz
Copyright (C) 1999-2012 Daniel Diaz
| ?- consult('list_to_set.pro').
yes
| ?- trace.
yes
{trace}
| ?- list_to_set([1,1,2,3], X).
      1    1  Call: list_to_set([1,1,2,3],_25) ?
      2    2  Call: list_to_set([1,2,3],_57) ?
      3    3  Call: list_to_set([2,3],_83) ?
      4    4  Call: list_to_set([3],_109) ?
      5    5  Call: list_to_set([],_135) ?
      5    5  Exit: list_to_set([],[]) ?
      6    5  Call: \+member(3,[]) ?
      7    6  Call: member(3,[]) ?
      7    6  Fail: member(3,[]) ?
      6    5  Exit: \+member(3,[]) ?
      4    4  Exit: list_to_set([3],[3]) ?
      7    4  Call: \+member(2,[3]) ?
      8    5  Call: member(2,[3]) ?
      ...

可以在http://remus.rutgers.edu/cs314/f2007/ryder/projects/prolog/prologTrace.html的READING A TRACE部分找到有关如何解释 Prolog 跟踪的说明。

于 2013-01-22T16:09:26.467 回答
3

prolog 程序的对应程序称为 SLDNF。询问：

 list_to_set([1,1,2,3], Result)

现在 SLDNF 尝试通过称为统一的过程将 [1,1,2,3] 与 [A|X] 匹配。简而言之，它检查变量是否可以被实例化。[A|X] 是一个快捷方式，它的意思是（松散地）：“A 是第一个元素，X 是其余的”。如果 A= 1 且 X = [1,2,3] 且 Result = [1 |Y]，则可以这样做。如果统一成功，那么我们在规则主体中使用相同的替换（出现在 :- 之后的内容）。您可能想知道为什么我们使用第二个子句而不是第三个或第一个子句？Prolog 实际上尝试了所有这些，试图模拟一个不确定的选择。尽管它按顺序尝试它们。第一个子句不能统一（A = ?，列表中没有任何内容）。如果我们的第一次尝试失败，稍后将检查第三个子句。我们称之为“选择点 1”，

现在 SLDNF 已将您的初始查询减少到：

list_to_set([1,2,3], Y2), \+ member(1, Y2)       {Result = [1 | Y2]}

（变量可以重命名，我们这样做是为了避免与程序混淆）这就是魔术发生的地方。SLDNF 现在做的事情和以前一样，但输入略有不同 [1,2,3]。最好的递归。所以它试图将它与第一个子句统一，但它又失败了。第二个成功了，同样你会得到，而不是查询的第一个元素（称为文字），我们再次拥有主体，变量替换 X = [2, 3], A = 1, Y2 = [ 1 | 是]。

现在我们有

list_to_set([2,3], Y), \+ member (1,Y), \+ member(1, [1 | Y])  {Result = [1 | [1 | Y]]}

我不会继续到最后。最终我们将检查 + member(1, [1 | Y])，这意味着“1 不是头 1 尾 Y 的列表的成员”。这是一个内置谓词并且会失败，因为 1 在该列表中（它是头部）。Prolog会回到一个选择点结束最终到达“选择点1”。这里子句中的最后一个条件是“A 是 Y 的成员”。您可以检查自己，这条路最终会成功。

抱歉冗长的匆忙回答，希望对您有所帮助。

于 2013-01-22T16:20:37.750 回答
1

让我们用英文看一下，看看它是否具有直观意义。将谓词重命名为看起来不那么程序化可能会有所帮助，因此我将其命名为list_set.

list_set([],[]).

这表示空集对应于空列表。

list_set([A|X], [A|Y]):-
  list_set(X,Y),
  \+ member(A,Y).

这表示从 A 开始并以 X 继续的列表对应于以 A 开始并以 Y 继续的集合，前提是 A 不在 Y 中并且 Y 是对应于 X 的集合。或者，以更逐步的方式，给定一个以 A 开头的列表（余数是 X），我们有一个以 A 开头的集合（余数是 Y），假设 Y 是对应于 X 的集合并且 A 不在 Y 中。否定运算符对我来说总是很奇怪，这很有趣，部分原因是这里发生的事情是 A 被保留，而在下一个子句中，没有A意味着它被有效地删除。

list_set([A|X], Y):-
  list_set(X, Y),
  member(A, Y).

这只是前一个子句的“其他”情况。它表示以 A 开头并以 X 继续的列表对应于集合 Y，前提是 Y 也对应于列表 X 并且 A 已经在 Y 中。这就是从结果中删除元素的方式，因为 A 出现在第一个参数的模式，但不在第二个参数的模式中。

于 2013-01-22T17:08:58.037 回答