list - 有人可以帮忙解释一下这个复制功能的工作原理吗？

Question

copyList([], []).           % base case
copyList([H|T], [H|R]) :- 
    copyList(T, R).

我“有点”理解递归是如何工作的，但是当我分析这个函数时，我真的很困惑。有人可以使用下面的示例逐步解释该函数中发生的情况以及它如何到达终点:

?- copyList([1,2,3],L).

Answer 1

要理解发生了什么，您必须将 Prolog 视为定理求解器:当您向 Prolog 提供查询 ?- copyList([1, 2, 3], L). 时，您实际上是在要求 Prolog 证明 copyList([1, 2, 3], L) 是正确的。

Prolog 因此将尝试证明这一点。它有两个子句供其使用:

1. copyList([], []).
   

2. copyList([H|T], [H|R]):- 
   copyList(T, R).
   

由于这是它遇到的第一个，Prolog 将尝试使用子句 copyList([1, 2, 3], L) 来证明 copyList([], []) 是正确的。

为此，由于子句没有主体( :- 之后没有任何内容)，因此只需将查询的参数与子句的参数统一(将 [1, 2, 3] 与 [] 统一，将 L 与 [] 统一)。虽然很容易将 L5 与 [] 统一(统一 L5 = [] )，但不可能将 [1, 2, 3] 与 [] 统一。因此，Prolog 无法通过使用第一个子句来证明您的查询。然后它必须尝试使用​​第二个。

它将再次将查询参数与子句参数统一起来，以查看该子句是否适用:这里可以这样做，统一为 H = 1, T = [2, 3], L = [H|R] 。现在它必须查看 :- 之后列出的条件是否得到遵守，因此它必须证明 copyList(T, R) 。完全相同的事情会发生两次，直到它发现自己试图证明 copyList([], R) 。到这里，第一个子句就适用了，它的工作就结束了。

可以用图来总结一下执行情况:

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.

现在执行结束了，我们可以通过统一链看到原来的L是什么:

L = [1|R]
       R = [2|R2]
              R2 = [3|R3]
                      R3 = []
              R2 = [3]
       R = [2, 3]
L = [1, 2, 3]

感谢 Will Ness 为 original idea 讲解如何解释变量的最终值。