将两个列表附加在一起的 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]

在这一步，我们感兴趣的所有值都已经定义好了.注意结果的头部是如何设置的Prolog 自上而下方式的特征列表(也称为 "tail recursion modulo cons").

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屋！