3

这是一种将两个列表附加在一起的算法：

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”根本没有改变，第三个参数.. . 起初 it's []，在每次递归调用后你得到它的尾巴，但因为它是[]，所以它保持[]。

那么，为什么突然，在第三个参数（“ Ot”）中我们有附加列表？有人可以逐步解释这个算法吗？

4

2 回答 2

13

首先，让我们把这些条款翻译成更容易理解的东西：

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 自上而下的方式（也称为“尾部递归模数”）构建结果列表。

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

我希望你能从中有所收获。

于 2012-05-16T14:06:15.520 回答
3

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

  1. 附加任何List到的结果[]是List.

  2. 将 any 附加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]. 附加到的列表不为空，因此我们可以跳过该规则。根据第二条规则，结果具有9作为第一个元素，然后是附加[-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]

于 2012-05-16T14:06:29.927 回答