Объяснение алгоритма Пролог для добавления двух списков вместе

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"вообще не меняется, а 3-й аргумент... сначала это []и после каждого рекурсивного вызова вы получаете его хвост, но так как это []остается [],

Так как же, вдруг, в 3-м аргументе ("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]

На этом этапе все интересующие нас значения уже определены. Обратите внимание, как устанавливается заголовок результата до того, как его хвост заполняется последующим (хвостовым рекурсивным) вызовом appendпостроение результирующего списка в характеристике нисходящего способа Пролога (также известного как "хвостовая рекурсия по модулю минусов").

Давайте следовать определениям, чтобы увидеть, что 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]

Я надеюсь, что вы получите что-то из этого.

Answer 2

Давайте переведем с Пролога на английский. У нас есть два правила:

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], Добавляемый список не пуст, поэтому мы можем пропустить это правило. По второму правилу результат имеет 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],