prolog - Prolog 中的递归如何从内部工作。一个例子

Question

我在这里有一个小脚本，它将元素列表转换为一个集合。例如列表 [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).

Answer 1

序言程序的过程对应物称为 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] 且结果 = [1 |Y]，则可以这样做。如果统一成功，那么我们在规则主体中使用相同的替换(出现在 :- 之后)。你可能想知道为什么我们使用第二个条款而不是第三个或第一个？ Prolog 实际上尝试了所有这些，试图模拟一个不确定的选择。尽管它按顺序尝试它们，但在程序上。第一个子句不能统一(A = ?，列表中什么都没有)。如果我们的第一次尝试失败，稍后将检查第三个子句。让我们称其为“选择点 1”，因为 Prolog 有这个开放的路径，没有被探索，如果到目前为止已经选择的路径失败，它可以使用。

现在 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 的成员”。你可以检查自己这条道路最终会成功。

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