Рекурсивная обработка: member и length

Почти любой предикат над списком — это рекурсия с базой на пустом списке и шагом на [H|T]; разберём её на member, length и sum_list.

Рекурсия над списком — приём, при котором предикат описывает результат для пустого списка (база) и сводит непустой список к его хвосту (шаг), пока не дойдёт до [].

В Prolog нет циклов for и while. Их роль играет рекурсия по структуре списка. Это не ограничение, а сильная сторона: рекурсивное определение часто короче и точнее описывает «что такое результат», чем пошаговый цикл. Освоив один шаблон, вы сможете писать почти любой обход списка.

Шаблон рекурсии над списком

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

member/2 — проверка принадлежности

Предикат member(X, L) истинен, когда X — элемент списка L. Реализуем его сами:

my_member(X, [X | _]).        % база: X — голова списка
my_member(X, [_ | T]) :-      % шаг: ищем X в хвосте
    my_member(X, T).

Читается декларативно. Первое правило: X входит в список, если он стоит в голове. Второе: X входит в список, если входит в хвост — голову при этом игнорируем через _. Базы с [] здесь нет специально: если список пуст, ни одно правило не сработает, и запрос даст false — что и значит «элемента нет».

?- my_member(b, [a, b, c]).
true.

?- my_member(z, [a, b, c]).
false.

?- my_member(X, [a, b, c]).
X = a ;
X = b ;
X = c ;
false.

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

length/2 — длина списка

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

my_length([], 0).             % база: пустой список — длина 0
my_length([_ | T], N) :-      % шаг: голова есть, считаем хвост
    my_length(T, N0),
    N is N0 + 1.

Ключевой момент — is. Это арифметика: N is N0 + 1 вычисляет правую часть и связывает результат с N. Сначала рекурсия спускается до [], получает там 0, а затем на обратном ходе прибавляет по единице за каждый уровень.

?- my_length([a, b, c], N).
N = 3.

sum_list — сумма элементов

Тот же шаблон, но вместо счётчика накапливаем сумму чисел:

my_sum([], 0).               % сумма пустого списка — 0
my_sum([H | T], Sum) :-      % сумма = голова + сумма хвоста
    my_sum(T, Rest),
    Sum is H + Rest.

?- my_sum([10, 20, 30], S).
S = 60.

Структура идентична length: разница лишь в том, что мы прибавляем H, а не единицу. Это и есть универсальность шаблона — поменяв одну строчку, получаем новый предикат.

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

Проследим трассировку my_sum([10, 20, 30], S). Рекурсия идёт вглубь, пока список не опустеет, а затем сворачивается обратно:

my_sum([10,20,30], S)
  -> my_sum([20,30], R1),  S  is 10 + R1
     -> my_sum([30], R2),  R1 is 20 + R2
        -> my_sum([], R3),  R2 is 30 + R3
           <- R3 = 0          (база сработала)
        <- R2 is 30 + 0  = 30
     <- R1 is 20 + 30 = 50
  <- S  is 10 + 50 = 60

Видно две фазы. На спуске («вглубь») предикат откладывает вычисления is и идёт к более короткому списку. На подъёме («обратно»), начиная с базы R3 = 0, накопленные равенства вычисляются снизу вверх. Именно поэтому база обязана давать конкретное значение (0): без неё цепочке не от чего оттолкнуться, и подъём не начнётся. Каждый вызов держит свой кадр в стеке, пока ждёт результата от вложенного вызова.

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

Первая ошибка — забыть базовый случай. Без правила my_length([], 0) рекурсия дойдёт до пустого списка, не найдёт подходящего правила и вернёт false вместо ответа. База — это не формальность, а точка опоры всей рекурсии.

Вторая ошибка — спутать = и is. Запись N = N0 + 1 НЕ считает: она унифицирует N с термом-выражением N0 + 1 буквально, как со структурой +(N0, 1). Для арифметики нужен именно is, который вычисляет правую часть.

Третья ошибка — ставить N is N0 + 1 до рекурсивного вызова. На момент вычисления N0 ещё не связан, и Prolog бросит ошибку «arguments are not sufficiently instantiated». Сначала рекурсия (она свяжет N0), потом арифметика.

Итог

• Рекурсия над списком = база на [] плюс шаг на [H|T], сводящий задачу к хвосту.
• member/2 без базы на [] сам генерирует элементы при свободной переменной.
• length/2 и sum_list накапливают результат на обратном ходе рекурсии.
• Арифметику делает is, а не =; вычислять можно только связанные переменные.
• Рекурсивный вызов ставьте ДО арифметики, иначе аргумент окажется несвязанным.