append и обработка списков

append/3 — самый показательный предикат Prolog: один и тот же код и склеивает списки, и разбивает их всеми возможными способами.

append(A, B, C) истинен, когда список C получается приписыванием списка B к концу списка A.

Если предыдущий урок показал рекурсию на чтении списка, то append показывает её на построении. И главное — он демонстрирует обратимость: декларативное определение не знает, какие аргументы заданы, а какие нужно найти. Один предикат заменяет десяток функций императивного языка.

Реализуем append/3 сами

Идея рекурсии: чтобы приписать B к [H|T], припишем B к хвосту T, а голову H вернём на место спереди. База — приписывание к пустому списку.

my_append([], B, B).                 % база: [] ++ B = B
my_append([H | T], B, [H | R]) :-    % шаг: голова остаётся, хвост склеиваем
    my_append(T, B, R).

Прочитаем декларативно. Первое правило: приписать B к пустому списку — это сам B. Второе: результат склейки [H|T] с B имеет ту же голову H, а его хвост R — это склейка T с B. Проверим прямое использование:

?- my_append([1, 2], [3, 4], C).
C = [1, 2, 3, 4].

Обратимость: разбиение списка

Здесь начинается магия. Если оставить свободными первые два аргумента, append переберёт все способы разбить список на голову и хвост через бэктрекинг:

?- my_append(A, B, [1, 2, 3]).
A = [],        B = [1, 2, 3] ;
A = [1],       B = [2, 3] ;
A = [1, 2],    B = [3] ;
A = [1, 2, 3], B = [] ;
false.

Мы не писали никакого кода для разбиения — он тот же самый. Просто Prolog, не зная A и B, ищет все их значения, при которых склейка даёт [1, 2, 3]. Это даёт мощный приём: проверку «является ли X подсписком в начале/конце» и генерацию всех префиксов и суффиксов одним вызовом.

last через append

Раз append умеет разбивать, опишем «последний элемент» декларативно: X — последний элемент списка L, если L есть некий список, к концу которого приписан одноэлементный список [X].

my_last(L, X) :-
    my_append(_, [X], L).

?- my_last([a, b, c], X).
X = c.

Мы не обходили список вручную — мы описали последний элемент через структуру и доверили поиск Prolog. Анонимная переменная _ поглощает всё, что стоит перед последним элементом.

reverse — переворот списка

Переворот тоже строится на рекурсии. Наивная версия использует append: перевернём хвост и припишем голову в самый конец одноэлементным списком.

my_reverse([], []).                     % перевёрнутый [] — это []
my_reverse([H | T], R) :-               % перевернуть [H|T]
    my_reverse(T, RT),                  %   = перевернуть хвост
    my_append(RT, [H], R).              %   и дописать голову в конец

?- my_reverse([1, 2, 3], R).
R = [3, 2, 1].

Для каждого элемента вызывается append, что даёт квадратичную сложность. На практике используют версию с аккумулятором, но наивная нагляднее показывает идею.

Как работает под капотом

Откуда берутся все разбиения? Дело в выборе правила и бэктрекинге. При запросе my_append(A, B, [1,2,3]) Prolog сперва пробует базу my_append([], B, B): тогда A = [], B = [1,2,3] — первое решение. По требованию следующего ответа (через ;) он откатывается и пробует шаг my_append([H|T], B, [H|R]): голова H = 1, остаётся подзадача my_append(T, B, [2,3]), которая рекурсивно повторяет ту же развилку.

append(A, B, [1,2,3])
  пробуем базу:  A=[],        B=[1,2,3]      решение 1
  пробуем шаг:   H=1, дальше append(T,B,[2,3])
      база:      A=[1],       B=[2,3]        решение 2
      шаг:       H=2, дальше append(T,B,[3])
          база:  A=[1,2],     B=[3]          решение 3
          шаг:   H=3, дальше append(T,B,[])
              база: A=[1,2,3], B=[]          решение 4

Каждый узел дерева — это точка выбора между «закончить здесь» (база) и «снять ещё одну голову» (шаг). Перебирая эти точки, Prolog исчерпывает все варианты и затем выдаёт false — разбиений больше нет. Никакой «функции разбиения» не существует: разбиение — это обратный прогон того же определения, что и склейка.

Частые ошибки

Первая ошибка — писать my_append(T, B, R) с третьим аргументом не [H|R], а просто R в голове правила. Тогда голова H потеряется, и результат окажется неверным. Голова обязана появиться и в первом, и в третьем аргументе шага.

Вторая ошибка — путать порядок в last или reverse: написать my_append([X], _, L) вместо my_append(_, [X], L). Первое описывает первый элемент, а не последний — структура разбиения зеркальна, и порядок аргументов задаёт смысл.

Третья ошибка — ждать от наивного reverse хорошей производительности на больших списках. Вложенный append делает её квадратичной; для длинных данных переходите на версию с аккумулятором.

Итог

append/3 рекурсивно склеивает списки: база на [], шаг сохраняет голову спереди.
Тот же предикат при свободных аргументах генерирует все разбиения списка через бэктрекинг.
last и подобные предикаты можно описать декларативно через append, не обходя список вручную.
reverse через append нагляден, но квадратичен; для скорости нужен аккумулятор.
Разбиение — это не отдельный код, а обратный прогон определения append.