Prolog 中的递归如何从内部工作.一个例子 [英] How does recursion in Prolog works from inside. One example

问题描述

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

I've got here a small script, that converts list of elements into a set. For example list [1,1,2,3] -> set [1,2,3]. Can somebody explain to me, step by step, whats happening inside those procedures? Can you please use my [1,1,2,3] -> [1,2,3] example?

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).

推荐答案

prolog 程序的过程对应物称为 SLDNF.查询:

The procedural counterpart of a prolog program is called SLDNF. Query:

 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 有这个开放的路径，没有被探索，如果到目前为止已经选择的路径失败，它可以使用.

Now SLDNF tries to match [1,1,2,3] with [A|X] through a procedure called unification. In a few words, it checks whether variable can be instantiated. [A|X] is a shortcut, it means (loosely): "A is the first element and X is the rest". This can be done if A= 1 and X = [1,2,3] and Result = [1 |Y]. If the unification succeeds then we use the same substitution in the body of the rule (what appears after :-). You may wonder why are we using the second clause but not the third or the first? Prolog actually tries all of them, tryign to emulate a nondeterministic choice. procedurally though it tries them in order. The first clause can't be unified (A = ?, there's nothing in the list). The third clause will be checked later if our first attempt fails. Let's call it "choice point 1", because Prolog has this open path that leaves unexplored and that can use if the paths that have been chosen so far fail.

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

Now SLDNF has reduced your initial query to:

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

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

(Variables can be renamed, and we do it to avoid confusion with the program) This is where the magic happens. SLDNF now does the same thing as before but with a slightly different input [1,2,3]. Recursion at its best. So it tries to unify it with the first clause but it fails again. It succeeds with the second, and similarly you'll get that instead of the first element of the query (called literal) we have again the body, with the variable substitution X = [2, 3], A = 1, Y2 = [1 | Y].

现在我们有

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 的成员".你可以自己检查一下，这条路最终会成功.

I'm not continuing until the end. Eventually we'll end up checking + member(1, [1 | Y]), which means "1 is not member of a list with head 1 and tail Y". This is a build in predicate and will fail, because 1 is in that list (it's the head). Prolog will go back to a choice point end eventually arrive at "choice point 1". Here the last condition in the clause is "A is member of Y". You can check yourself that this path will succeed eventually.

抱歉回复太仓促，希望能帮到你.

Sorry for the lengthy hurried answer, I hope it helps.

这篇关于Prolog 中的递归如何从内部工作.一个例子的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！