解释将两个列表附加在一起的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")中我们有附加的列表？有人可以一步一步地解释这个算法吗？

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]

在此步骤中,我们已经定义了所有我们感兴趣的值.注意在尾部被后续(尾递归)调用填充之前如何设置结果的头部,在appendProlog自上而下方式(也称为"尾递归模数缺点")的特征中构建结果列表.

让我们按照定义来看看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]

我希望你能从中得到一些东西.