Нотация списков [H|T]

Список в Prolog — это рекурсивная структура из головы и хвоста, и почти вся работа со списками строится на одной нотации [H|T].

Список — упорядоченная последовательность элементов; в Prolog это либо пустой список [], либо пара «голова и хвост», записываемая как [H|T].

Если в большинстве языков список — это массив с индексами, то в Prolog список — это вложенная структура, очень похожая на односвязный список. Понимать его устройство критично: без чёткого образа того, что такое голова и хвост, рекурсивные предикаты будут казаться магией. Давайте разберём нотацию до самого дна.

Зачем нужна особая нотация

Списки встречаются буквально везде: разобрать строку, перебрать кандидатов, накопить результат, представить множество фактов. Prolog даёт компактный синтаксис, который одновременно служит и для построения списка, и для его разбора. Одна и та же запись [H|T] в одном месте программы соберёт список из головы и хвоста, а в другом — расщепит существующий список на первый элемент и остаток. Эта двойственность и делает Prolog таким выразительным.

Из чего состоит список

Самый простой список — пустой: []. Это атом, базовый кирпич, на котором заканчивается любая рекурсия. Непустой список записывают, перечисляя элементы в квадратных скобках:

[]                  % пустой список
[1]                 % список из одного элемента
[1, 2, 3]           % список из трёх чисел
[a, b, c]           % список из атомов
[1, foo, [2,3], X]  % элементы могут быть любыми термами

Элементы могут быть чем угодно: числами, атомами, переменными и даже другими списками. Список — это контейнер для произвольных термов.

Голова и хвост

Главная нотация — вертикальная черта: [H|T]. Слева от черты — голова (первый элемент), справа — хвост (список из оставшихся элементов). Хвост — это всегда список, даже если он пустой.

[1, 2, 3]  это то же самое, что  [1 | [2, 3]]
[2, 3]     это то же самое, что  [2 | [3]]
[3]        это то же самое, что  [3 | []]

Видно матрёшку: каждый список — это голова плюс хвост, который сам устроен так же, пока мы не упрёмся в []. Можно перечислить несколько голов сразу: [A, B | T] берёт первые два элемента и остаток.

Сопоставление списков по образцу

Унификация делает нотацию [H|T] рабочим инструментом. Когда Prolog сопоставляет список с образцом, он раскладывает его на части и связывает переменные. Разберём на запросах:

?- [X | T] = [10, 20, 30].
X = 10,
T = [20, 30].

?- [X, Y | _] = [10, 20, 30].
X = 10,
Y = 20.

?- [_, _, Z | _] = [10, 20, 30, 40].
Z = 30.

?- [X] = [10, 20, 30].
false.

Разберём каждый случай. Образец [X|T] вытаскивает голову в X и весь хвост в T. Образец [X, Y | _] берёт первые два элемента, а остаток отбрасывает в анонимную переменную _ (нам неважно, что там). Образец [_, _, Z | _] пропускает два элемента и связывает третий. А вот [X] = [10, 20, 30] терпит неудачу: образец [X] — это список ровно из одного элемента (то есть [X | []]), а справа три элемента, хвост не может унифицироваться с [].

Пустой список как образец

Отдельно стоит образец []. Он сопоставляется только с пустым списком и ни с чем больше. Это та самая граница, где рекурсия останавливается:

?- [] = [].
true.

?- [] = [1].
false.

?- [H | T] = [].
false.

Запомните пару фактов: [] унифицируется только с [], а образец [H|T] требует непустого списка — у пустого списка нет головы. Именно поэтому базовый случай предиката почти всегда работает с [], а рекурсивный шаг — с [H|T].

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

Квадратные скобки — это синтаксический сахар. На самом деле список [1, 2, 3] внутри Prolog хранится как вложенная структура из функтора с именем '[|]' (в старых системах — '.') и двумя аргументами: голова и хвост.

[1, 2, 3]  внутри это  '[|]'(1, '[|]'(2, '[|]'(3, [])))

То есть [H|T] — это просто читаемая запись для '[|]'(H, T). Можно нарисовать дерево:

   '[|]'
   /   \
  1   '[|]'
      /   \
     2   '[|]'
         /   \
        3    []

Эта структура объясняет всё: почему доступ к голове мгновенный (она в корне), а доступ к последнему элементу требует рекурсивного спуска до самого низа. Список — это вложенные пары, и унификация просто сопоставляет деревья узел за узлом. Понимая это представление, вы перестаёте удивляться, почему append работает за линейное время, а добавление в начало — за константное.

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

Первая и самая частая: путать запятую и вертикальную черту. [H, T] — это список из ровно двух элементов, а [H | T] — голова и хвост-список. Эти образцы ведут себя совершенно по-разному, и подмена ломает рекурсию.

Вторая ошибка: ждать, что хвост — это элемент. Хвост всегда список. В [1 | T] для списка [1, 2, 3] переменная T станет [2, 3], а не 2. Чтобы получить именно второй элемент, нужен образец [_, X | _].

Третья ошибка: применять образец [H|T] к пустому списку и удивляться неудаче. Это не баг — у [] просто нет головы. Всегда предусматривайте отдельное правило для [].

Итог

• Список — это либо [], либо пара [H|T] из головы и хвоста-списка.
• Нотация [H|T] служит и для сборки, и для разбора списка через унификацию.
• Образцы вроде [X|_], [X,Y|_], [_,_,Z|_] вытаскивают нужные элементы по позиции.
• [] унифицируется только с пустым списком; [H|T] требует непустого.
• Под капотом список — вложенная структура '[|]'(H, T), заканчивающаяся на [].