copyList([], []). % base case
copyList([H|T], [H|R]) :-
copyList(T, R).
I "sort of" understand how recursion works, but when I analysed this function, I got really confused. Can someone please explain, step-by-step what happens in this function and how it reaches the end using the example below:
我“有点”理解递归是如何工作的,但是当我分析这个函数时,我真的很困惑。有人可以通过以下示例逐步解释此功能中发生的事情以及它如何到达终点:
?- copyList([1,2,3],L).
2 个解决方案
#1
To understand what happens, you must see Prolog as a theorem solver: when you give Prolog the query ?- copyList([1, 2, 3], L)., you're essentially asking Prolog to prove that copyList([1, 2, 3], L) is true.
要理解会发生什么,你必须看Prolog作为一个定理求解器:当你给Prolog一个查询? - copyList([1,2,3],L)。,你基本上要求Prolog证明copyList([1, 2,3],L)是真的。
Prolog will therefore try to prove it. At its disposal, it has two clauses:
因此Prolog将尝试证明这一点。它可以使用它有两个条款:
copyList([], []).copyList([H|T], [H|R]):- copyList(T, R).
copyList([H | T],[H | R]): - copyList(T,R)。
As it is the first that it encounters, Prolog wil try to prove that copyList([1, 2, 3], L) is true by using the clause copyList([], []).
因为它是第一次遇到,Prolog将尝试使用子句copyList([],[])来证明copyList([1,2,3],L)为真。
To do so, and since the clause has no body (nothing after :-), it would just have to unify the arguments of your query with the arguments of the clause (unify [1, 2, 3] with [] and L with []). While it is easy to unify L5 with [] (with the unification L5 = []), it is impossible to unify [1, 2, 3] with []. Therefore Prolog has failed to prove your query by using the first clause at its disposal. It must then try to use the second.
要做到这一点,并且由于该子句没有正文(后面没有任何内容:-),它只需要将查询的参数与子句的参数统一(将[1,2,3]与[]和L统一起来[])。虽然很容易将L5与[]统一(统一L5 = []),但不可能将[1,2,3]与[]统一起来。因此,Prolog无法通过使用第一个条款来证明您的查询。然后必须尝试使用第二个。
Once again it will unify the query arguments with the clause arguments to see if the clause is applicable: here it can do so, with the unifications H = 1, T = [2, 3], L = [H|R]. Now it has to see if the conditions listed after :- are respected, so it has to prove copyList(T, R). The exact same thing goes on twice, until it finds itself trying to prove copyList([], R). There, the first clause is applicable, and its job is over.
再一次,它将使用子句参数统一查询参数,以查看该子句是否适用:这里可以这样做,统一H = 1,T = [2,3],L = [H | R]。现在它必须查看以下列出的条件: - 是否得到尊重,因此必须证明copyList(T,R)。完全相同的事情发生两次,直到它发现自己试图证明copyList([],R)。在那里,第一个条款适用,其工作已经结束。
You can sum up the execution with a drawing as follows:
您可以使用绘图总结执行,如下所示:
copyList([1, 2, 3], L).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and L = [1|R]
|
` copyList([2, 3], R).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and R = [2|R2]
|
` copyList([3], R2).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and R2 = [3|R3]
|
` copyList([], R3).
|
| use clause number 1 and R3 = []. One solution found
| try to use clause number 2, doesn't unify with arguments.
| No more possibilities to explore, execution over.
Now that the execution is over, we can see what the original L is by following the chain of unifications:
既然执行已经结束,我们可以通过遵循统一链看到原始L是什么:
L = [1|R]
R = [2|R2]
R2 = [3|R3]
R3 = []
R2 = [3]
R = [2, 3]
L = [1, 2, 3]
Thanks to Will Ness for his original idea on how to explain the final value of a variable.
感谢Will Ness关于如何解释变量最终值的最初想法。
#2
While your specific question was already answered, few remarks.
虽然您的具体问题已经得到解答,但很少有评论。
First, you could just as well call ?- copyList(L,[1,2,3]). or ?- copyList([1,2,3],[1,2|Z]). etc. What's important is that both lists can be of equal length, and their elements at the corresponding positions can be equal (be unified), because the meaning of the predicate is that its two argument lists are the same - i.e. of the same length, and having the same elements.
首先,你可以调用吗? - copyList(L,[1,2,3])。或? - copyList([1,2,3],[1,2 | Z])。重要的是两个列表的长度可以相等,并且它们在相应位置的元素可以相等(统一),因为谓词的含义是它的两个参数列表是相同的 - 即长度相同,并具有相同的元素。
For example, the first condition can be violated with the call
例如,可以通过呼叫违反第一个条件
?- copyList(X, [A|X]).
because it says that the 2nd argument is one element longer than the first. Of course such solution can not be, but the query will never terminate, because the first clause won't ever match and the second always will.
因为它说第二个参数比第一个参数长一个元素。当然这样的解决方案不可能,但查询永远不会终止,因为第一个子句永远不会匹配,第二个子句总是会匹配。
#1
To understand what happens, you must see Prolog as a theorem solver: when you give Prolog the query ?- copyList([1, 2, 3], L)., you're essentially asking Prolog to prove that copyList([1, 2, 3], L) is true.
要理解会发生什么,你必须看Prolog作为一个定理求解器:当你给Prolog一个查询? - copyList([1,2,3],L)。,你基本上要求Prolog证明copyList([1, 2,3],L)是真的。
Prolog will therefore try to prove it. At its disposal, it has two clauses:
因此Prolog将尝试证明这一点。它可以使用它有两个条款:
copyList([], []).copyList([H|T], [H|R]):- copyList(T, R).
copyList([H | T],[H | R]): - copyList(T,R)。
As it is the first that it encounters, Prolog wil try to prove that copyList([1, 2, 3], L) is true by using the clause copyList([], []).
因为它是第一次遇到,Prolog将尝试使用子句copyList([],[])来证明copyList([1,2,3],L)为真。
To do so, and since the clause has no body (nothing after :-), it would just have to unify the arguments of your query with the arguments of the clause (unify [1, 2, 3] with [] and L with []). While it is easy to unify L5 with [] (with the unification L5 = []), it is impossible to unify [1, 2, 3] with []. Therefore Prolog has failed to prove your query by using the first clause at its disposal. It must then try to use the second.
要做到这一点,并且由于该子句没有正文(后面没有任何内容:-),它只需要将查询的参数与子句的参数统一(将[1,2,3]与[]和L统一起来[])。虽然很容易将L5与[]统一(统一L5 = []),但不可能将[1,2,3]与[]统一起来。因此,Prolog无法通过使用第一个条款来证明您的查询。然后必须尝试使用第二个。
Once again it will unify the query arguments with the clause arguments to see if the clause is applicable: here it can do so, with the unifications H = 1, T = [2, 3], L = [H|R]. Now it has to see if the conditions listed after :- are respected, so it has to prove copyList(T, R). The exact same thing goes on twice, until it finds itself trying to prove copyList([], R). There, the first clause is applicable, and its job is over.
再一次,它将使用子句参数统一查询参数,以查看该子句是否适用:这里可以这样做,统一H = 1,T = [2,3],L = [H | R]。现在它必须查看以下列出的条件: - 是否得到尊重,因此必须证明copyList(T,R)。完全相同的事情发生两次,直到它发现自己试图证明copyList([],R)。在那里,第一个条款适用,其工作已经结束。
You can sum up the execution with a drawing as follows:
您可以使用绘图总结执行,如下所示:
copyList([1, 2, 3], L).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and L = [1|R]
|
` copyList([2, 3], R).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and R = [2|R2]
|
` copyList([3], R2).
|
| try to use clause number 1, doesn't unify with arguments.
| use clause number 2 and R2 = [3|R3]
|
` copyList([], R3).
|
| use clause number 1 and R3 = []. One solution found
| try to use clause number 2, doesn't unify with arguments.
| No more possibilities to explore, execution over.
Now that the execution is over, we can see what the original L is by following the chain of unifications:
既然执行已经结束,我们可以通过遵循统一链看到原始L是什么:
L = [1|R]
R = [2|R2]
R2 = [3|R3]
R3 = []
R2 = [3]
R = [2, 3]
L = [1, 2, 3]
Thanks to Will Ness for his original idea on how to explain the final value of a variable.
感谢Will Ness关于如何解释变量最终值的最初想法。
#2
While your specific question was already answered, few remarks.
虽然您的具体问题已经得到解答,但很少有评论。
First, you could just as well call ?- copyList(L,[1,2,3]). or ?- copyList([1,2,3],[1,2|Z]). etc. What's important is that both lists can be of equal length, and their elements at the corresponding positions can be equal (be unified), because the meaning of the predicate is that its two argument lists are the same - i.e. of the same length, and having the same elements.
首先,你可以调用吗? - copyList(L,[1,2,3])。或? - copyList([1,2,3],[1,2 | Z])。重要的是两个列表的长度可以相等,并且它们在相应位置的元素可以相等(统一),因为谓词的含义是它的两个参数列表是相同的 - 即长度相同,并具有相同的元素。
For example, the first condition can be violated with the call
例如,可以通过呼叫违反第一个条件
?- copyList(X, [A|X]).
because it says that the 2nd argument is one element longer than the first. Of course such solution can not be, but the query will never terminate, because the first clause won't ever match and the second always will.
因为它说第二个参数比第一个参数长一个元素。当然这样的解决方案不可能,但查询永远不会终止,因为第一个子句永远不会匹配,第二个子句总是会匹配。