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

Это алгоритм для добавления двух списков:

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]и он сохранен в & quot;Ot& Quot ;.

У меня вопрос, как это работает?

Я понимаю, что при каждом рекурсивном вызове в первом списке вы получаете только хвост в виде списка (таким образом, его размер уменьшается на1 пока это не[] ) второй аргумент & quot;List2& Quot; вообще не меняется, а 3-й аргумент ... сначала это[]и после каждого рекурсивного вызова вы получаете его хвост, но так как он[]остается[].

Так как же вдруг в 3-м аргументе (& quot;Ot& quot;) у нас есть добавленный список? Может кто-нибудь объяснить этот алгоритм шаг за шагом?

Ответы на вопрос(2)

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

The result of appending any List to [] is that List.

The result of appending any List to a list whose first element is H and remainder is L1 is equal to a list whose first element is also H whose remainder is the result of appending List to 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].

 Jordashiro16 мая 2012 г., 16:10
Спасибо и @Mog, но мне понравился его & quot; grapic & quot; объяснение больше :) +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]

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

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

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

 Jordashiro16 мая 2012 г., 16:12
Редактирование было хорошим дополнением :), теперь я понимаю, что мне не хватало того, что заголовок List1 был добавлен к хвосту List3, еще раз спасибо, отличное объяснение.
 19 июл. 2012 г., 11:34
@Jordashiro, если две строки в переписывании Mog второго предложения были заменены, то можно сказать, что заголовок List1 добавлялся в конец List3. Но в настоящее время порядок обратный. Голова устанавливается до того, как хвост заполняется последующим призывом к добавлению, который, таким образом,tail recursive modulo cons.

Ваш ответ на вопрос