一个Prolog算法将两个列表连接起来的解释

Question

这是一种将两个列表合并的算法：

Domains
list= integer*

Predicates
nondeterm append(list, list, list)

Clauses
append([], List, List) :- !.
append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

Goal
append([9,2,3,4], [-10,-5,6,7,8], Ot).

结果是一个列表[9,2,3,4,-10,-5,6,7,8]，保存在"Ot"中。

我的问题是，这是如何实现的？

我所理解的是，在每个递归调用中，在第一个列表中，您只得到列表的尾部（因此将其大小减少1，直到它为[]），第二个参数"List2"根本不改变，第三个参数...一开始是[]，每个递归调用后你得到了它的尾巴，但由于它是[]，所以它仍然是[]。

那么，为什么在第三个参数("Ot")中我们会突然有附加的列表？ 有人能逐步解释这个算法吗？

- Jordashiro

Answer 1

首先，让我们将条款翻译成更易理解的内容：

append([], List, List) :- !.

可以写成

append([], List2, Result) :-
    Result = List2,
    !.

并且

append([H|L1], List2, [H|L3]) :- append(L1, List2, L3).

可以编写

append(List1, List2, Result) :-
    List1  = [Head1 | Tail1],
    Result = [HeadR | TailR],
    Head1  =  HeadR,
    append(Tail1, List2, TailR).

我希望这对您已经更加清晰了。

然后，逐步地，每次使用的子句编号都会被指示，并显示结果调用：

append([9, 2, 3, 4], [-10, -5, 6, 7, 8], Ot).
|
2
|
` append([2, 3, 4], [-10, -5, 6, 7, 8], Ot'). % and Ot = [9|Ot']
  |
  2
  |
  ` append([3, 4], [-10, -5, 6, 7, 8], Ot''). % and Ot' = [2|Ot'']
    |
    2
    |
    ` append([4], [-10, -5, 6, 7, 8], Ot'''). % and Ot'' = [3|Ot''']
      |
      2
      |
      ` append([], [-10, -5, 6, 7, 8], Ot''''). % and Ot''' = [4|Ot'''']
        |
        1
        |
        ` Ot'''' = [-10, -5, 6, 7, 8]

在这一步中，我们感兴趣的所有值已经被定义。请注意，在后续的（尾递归）调用append填充其尾部以构建结果列表之前，结果的头部已经被设置，以符合Prolog自上而下的特征方式构建结果列表的特点（也称为“尾递归模cons”）。

让我们跟随定义来看看在最终步骤中Ot是什么：

Ot = [9|Ot']
        Ot' = [2|Ot'']
                 Ot'' = [3|Ot''']
                           Ot''' = [4|Ot'''']
                                      Ot'''' = [-10, -5, 6, 7, 8]
                           Ot''' = [4,          -10, -5, 6, 7, 8]
                 Ot'' = [3,         4,          -10, -5, 6, 7, 8]
        Ot' = [2,        3,         4,          -10, -5, 6, 7, 8]
Ot = [9,       2,        3,         4,          -10, -5, 6, 7, 8]

我希望你能从中获得一些收获。

- m09

---

修改很不错👍，现在我明白了，我之前漏掉的是把List1的头部添加到List3的尾部，再次感谢您，解释得非常好。 - Jordashiro

@Jordashiro 如果在 Mog 对第二个子句的重写中交换了这两行代码，那么你可以说 List1 的头部被添加到了 List3 的尾部。但是现在的顺序是相反的。在后续调用 append 填充尾部之前，先设置头部，因此这是 尾递归模 cons。 - Will Ness

Answer 2

让我们把Prolog翻译成英文。我们有两个规则：

1. 将任何List追加到[]的结果是该List。
2. 将任何List追加到第一个元素为H且其余部分为L1的列表的结果等于一个以H为首元素且其余部分是将List追加到L1的结果的列表。

因此，我们想要将[-10,-5,6,7,8]追加到[9,2,3,4]。被追加的列表不为空，因此我们可以跳过第一条规则。根据第二条规则，结果的第一个元素为9，后跟将[-10,-5,6,7,8]追加到[2,3,4]的结果。

因此，我们想要将[-10,-5,6,7,8]追加到[2,3,4]。被追加的列表不为空，因此我们可以跳过第一条规则。根据第二条规则，结果的第一个元素为2，后跟将[-10,-5,6,7,8]追加到[3,4]的结果。

因此，我们想要将[-10,-5,6,7,8]追加到[3,4]。被追加的列表不为空，因此我们可以跳过第一条规则。根据第二条规则，结果的第一个元素为3，后跟将[-10,-5,6,7,8]追加到[4]的结果。

因此，我们想要将[-10,-5,6,7,8]追加到[4]。被追加的列表不为空，因此我们可以跳过第一条规则。根据第二条规则，结果的第一个元素为4，后跟将[-10,-5,6,7,8]追加到[]的结果。

因此，我们想要将[-10,-5,6,7,8]追加到[]。被追加的列表为空，因此根据第一条规则，结果为[-10,-5,6,7,8]。

将[-10,-5,6,7,8]添加到[]中的结果为[-10,-5,6,7,8]，将[-10,-5,6,7,8]添加到[4]中的结果为[4,-10,-5,6,7,8]。

将[-10,-5,6,7,8]添加到[4]中的结果为[4,-10,-5,6,7,8]，将[-10,-5,6,7,8]添加到[3,4]中的结果为[3,4,-10,-5,6,7,8]。

将[-10,-5,6,7,8]添加到[3,4]中的结果为[3,4,-10,-5,6,7,8]，将[-10,-5,6,7,8]添加到[2,3,4]中的结果为[2,3,4,-10,-5,6,7,8]。

将[-10,-5,6,7,8]添加到[2,3,4]中的结果为[2,3,4,-10,-5,6,7,8]，将[-10,-5,6,7,8]添加到[9,2,3,4]中的结果为[9,2,3,4,-10,-5,6,7,8]。

- Mark Reed

---

谢谢你和@Mog，但我更喜欢他的“图形”解释:) +1 - Jordashiro