В данном разделе мы рассмотрим процедуру конкатенации двух списков L1,L2 другими словами добавление элементов из одного списка к другому, результатом такой операции является список L3 = L1+L2.

С этой целью определим предикат concatenation(L1, L2, L3), здесь  L1 и  L2 определяют исходные списки, а L3 – выходной список.

Например: concatenation ([a,b], [c, d] , [a,b,c,d])

является истинным.

Для определения правил конкатенации двух списков рассмотрим следующие ситуации:

1. Если параметр предиката L1 является пустым списком, тогда списки L2, L3 должны быть одинаковыми (можно их обозначить L).

2. Если первый параметр является не пустым списком, тогда этот список делится на голову и хвост, его можно представить как [X | L1].

Можно выделить общие шаги для выполнения данной процедуры, а именно сначала список L3 пуст, в него должны быть скопированы элементы из списка L2, а затем из L1.

Это можно записать так:

concatenation([ ], L, L).

concatenation( [X|L1], L2, [X|L3] ):- concatenation(L1, L2, L3).

Рассмотрим шаги выполнения этого предиката при следующем вызове:

concatenation([1,2,3], [4,5], L3).

В данном случае первое правило не выполняется, так как первый параметр не является пустым списком, тогда начинает работать второе правило. Так как третий список пустой, то к нему невозможно применить операцию деления на голову и хвост, тогда происходит рекурсивное деление на хвост и голову первого списка (данные помещаются в стек), это происходит до тех, пока он не опустеет.

concatenation([ ], [4,5], _).

После этого срабатывает первое правило, что приводит к инициализации третьего списка вторым.

concatenation ([ ], [4,5], [4,5]).

После того как рекурсивные вызовы завершаются, данные извлекаются из стека и в соответствии со вторым правилом элементы добавляются в третий список.

concatenation([1,2,3], [4,5], [1,2,3,4,5]).