Требуется помощь в понимании метода пролога для добавления элементов списка

Question

append([],Xs,Xs).
append([Head|Tail],List2,[Head|Tail2]):-
    append(Tail,List2,Tail2).

Метод верхнего добавления добавляет элементы из первых двух слотов параметров в третью переменную param.

?-append([2,1], [3,4], X).
?-X=[2,1,3,4]

То, как я вижу это поэтапно (вероятно, неправильно) ->

1. append (2 | [1], [3,4], 2 | X)

2. append ([1], [3,4], X)

3. append (1 | [], [3,4], 1 | X)

4. append ([], [3,4], [3,4])

И это все. Я не могу обернуть голову, как он складывает элементы, и вот с чем я мог бы помочь - ясное объяснение того, как работает этот метод. Я просто не понимаю, как массив [2,1] добавляется к конечному результату.

Answer 1

X в рекурсии не совпадает X с исходным вызовом, если вы переименуете его в трассировке, вы увидите

append(2 | [1], [3,4], 2 | X1) -- X = [2|X1]

append([1], [3,4], X1)

append(1 | [], [3,4], 1 | X2) -- X1 = [1|X2]
append ([], [3,4], [3,4])  -- X2 = [3,4]

так X1 = [1,3,4] и X = [2,1,3,4]

Answer 2

Во-первых, вы должны понять, как список реализован в Прологе. Это существенно рекурсивная структура данных.

• Пустой список - это список нулевых элементов, представленных атомом [].

• Непустые списки представлены структурой ./2, состоящей из заголовка списка (термин пролога) и хвоста списка (другой список, состоящий из всех элементов, кроме первого). Итак ...

  • [] & mdash; список нулевых позиций представлен как
    []
  • [a] & mdash; список из 1 элемента, представлен как
    .(a,[])
  • [a,b] & mdash; список из 2 предметов, представлен как
    .(a,.(b,[]))
  • [a,b,c] & mdash; список из 3 предметов, представлен как
    .(a,.(b,.(c,[])))

Стандартная запись списка с использованием квадратных скобок - это просто синтаксический сахар поверх этого представления. Сказать [Head|Tail] - это вежливый способ сказать .(Head,Tail), а сказать [X,Y,Z|More] - это вежливый способ сказать .(X,.(Y,.(Z,More))). (Вы можете заметить определенную .... Lisp-ishness ... во внутренней записи списка здесь.)

Чтобы понять, как представлен список, наивный алгоритм добавления (объединения) одного списка в другой таков:

Во-первых, следует рассмотреть два особых случая:

• Результатом добавления непустого списка X к пустому списку Y является X.
  Добавьте [1,2,3] к [] и получите [1,2,3]. Примечание. Однако этот случай может (обычно) обрабатываться обычным случаем ниже. Это возможность для оптимизации, поскольку нет смысла повторять весь список, просто заменить [] на [] в конце, верно?

• Результатом добавления пустого списка X к непустому списку Y является Y.
  Добавьте [] к [1,2,3], и вы получите [1,2,3].

В противном случае мы имеем обычный случай:

• Добавление непустого списка Y к непустому списку X для создания списка Z. Сделать это тривиально:

  Мы просто возвращаемся к списку X, вставляя его голову по ходу и добавляя его к списку Z, результат. Вы заметите, что когда это происходит, список Z представляет собой поврежденную структуру списка, поскольку его последний узел всегда не связан, а не является []. Это исправляется в самом конце, когда список источников, список X, исчерпан и вырождается в особый случай, когда он является пустым списком. В этот момент несвязанный последний узел становится связанным, поскольку он объединяется со списком Y (список из нуля или более узлов), оставляя нам правильную структуру списка.

Код Пролога для append/3 выражает этот алгоритм напрямую. Как отмечалось ранее, первое предложение является необязательной оптимизацией, поскольку оно может быть обработано третьим предложением (обычный случай). Он хочет сократить, хотя, как и без него, возврат приведет к двум решениям.

append( X      , [] , X      ) :- !. ; concatenate empty list X to list Y producing Y
append( []     , Y  , Y      ).      ; concatenate list X to empty list Y producing X
append( [X|Xs] , Y  , [X|Zs] ) :-    ; anything else
  append( Xs , Y , Zs )
  .