对将两个列表附加在一起的Prolog算法的说明 [英] Explanation of a Prolog algorithm to append two lists together

问题描述

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

This is an algorithm to append together two lists:

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"中.

The result is a list [9,2,3,4,-10,-5,6,7,8], and it's saved in "Ot".

我的问题是，这如何工作?

My question is, how does this work?

我了解的是，在每个递归调用中，在第一个列表中，您仅将尾部作为列表(从而将其大小减小了1，直到它成为[])，第二个参数是"List2"完全没有变化，第三个参数...最初是[]，在每次递归调用后您都得到了尾巴，但是由于它是[]，因此保持为[].

What I understand is that in every recursive call, in the first list, you get only the tail as a list ( thus reducing its size by 1 until it's [] ), the second argument "List2" does not change at all, and the 3rd argument ... at first it's [], and after each recursive call you get its tail, but since it's [], it stays [].

那么为什么突然出现了第三个参数("Ot")中的附加列表? 有人可以逐步解释此算法吗?

So how come, suddenly, in 3rd argument ("Ot") we have the appended list ? Can someone explain this algorithm step by step ?

推荐答案

首先，让我们将这些子句翻译成更易于理解的内容:

First, let's translate the clauses into something more understandable:

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).

我希望这对您来说已经很清楚了.

I hope this will already be clearer for you.

然后逐步地，数字表示每次使用的子句，并显示结果调用:

Then, step by step, the number indicates the clause used each time, and the resulting call is shown:

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的后续调用( tail recursive )填充的，从而在Prolog自上而下的方式(也称为 尾递归模态缺点" ).

At this step all the values we're interested in are already defined. Notice how the head of the result is set before its tail is filled up by a subsequent (tail recursive) call to append, building the resulting list in the characteristic for Prolog top-down fashion (also known as "tail recursion modulo cons").

在最后一步，让我们遵循以下定义以查看Ot是什么:

Let's follow the definitions to see what Ot is, at the final step:

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]

希望您能从中学到一些东西.

I hope you'll get something out of it.

这篇关于对将两个列表附加在一起的Prolog算法的说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！