Обход и доступ: first, rest, nth и списки как стек

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

Список Lisp — связная структура, поэтому его обходят последовательно: либо рекурсией по схеме «голова и хвост», либо итеративными конструкциями dolist и loop. Доступ к произвольному элементу через nth линеен, а добавление и снятие с головы через push и pop мгновенны — поэтому список естественно работает как стек.

Мы знаем, из чего сделаны списки и как их строить. Теперь — самое практическое: как по ним ходить и доставать данные. Поскольку список связный, способы обхода и их стоимость напрямую вытекают из структуры ячеек, которую мы изучили. Этот урок свяжет теорию cons-ячеек с повседневными приёмами обработки данных.

Рекурсия: естественный способ обхода

Самый «лисповый» способ пройти по списку — рекурсия по уже знакомой схеме «голова и хвост». Берём car (голову), что-то с ней делаем, затем рекурсивно вызываем себя на cdr (хвосте). База рекурсии — пустой список nil, на котором обработка останавливается. Эта схема настолько естественна для связного списка, что почти все базовые списочные функции концептуально устроены именно так.

;; Рекурсивный подсчёт суммы элементов списка:
(defun my-sum (lst)
  (if (null lst)              ; база: пустой список
      0
      (+ (car lst)            ; голова
         (my-sum (cdr lst)))))  ; рекурсия по хвосту

(my-sum '(1 2 3 4 5))   ; => 15

;; Рекурсивный подсчёт длины:
(defun my-length (lst)
  (if (null lst)
      0
      (+ 1 (my-length (cdr lst)))))

(my-length '(a b c))    ; => 3

Прочитайте my-sum вслух: «если список пуст — сумма ноль; иначе — голова плюс сумма хвоста». Это прямое отражение структуры: список либо пуст, либо состоит из головы и хвоста-списка. Рекурсия по car/cdr — фундаментальный навык, и понимание, что хвост сам является списком, делает её очевидной.

Итеративный обход: dolist и loop

Рекурсия концептуально красива, но на практике для простого перебора чаще используют итеративные конструкции. Самая простая — dolist: она по очереди связывает переменную с каждым элементом списка и выполняет тело. Более мощная и универсальная — loop, настоящий мини-язык для циклов, умеющий перебирать, накапливать, фильтровать и собирать результаты.

;; dolist перебирает элементы по одному:
(defun print-all (lst)
  (dolist (x lst)
    (print x)))

;; loop умеет перебирать и собирать результат:
(loop for x in '(1 2 3 4) sum x)            ; => 10
(loop for x in '(1 2 3 4) collect (* x x))  ; => (1 4 9 16)
(loop for x in '(5 2 8 1) maximize x)       ; => 8

Здесь видно различие диалектов. Common Lisp намеренно богат: dolist, dotimes, огромный loop и другие итеративные формы встроены в стандарт. Scheme, верный минимализму, не имеет встроенного loop и предпочитает выражать итерацию хвостовой рекурсией (которую гарантированно оптимизирует, в отличие от Common Lisp). Это иллюстрирует общую философскую разницу: Common Lisp даёт готовые мощные конструкции, Scheme — минимум примитивов, из которых вы строите нужное.

Доступ к элементам: first, rest, nth

Для доступа к элементам есть удобные именованные функции. first ... tenth дают первый-десятый элементы (синонимы для car, cadr и так далее), rest — хвост (синоним cdr), а nth — элемент по индексу (с нуля). Важнейшее, что нужно осознать: nth — это не мгновенный доступ, как индексация массива. Чтобы добраться до n-го элемента, nth проходит по цепочке cdr n раз, то есть его стоимость линейна.

;; Именованный доступ к началу списка:
(first  '(a b c d e))   ; => A
(second '(a b c d e))   ; => B
(rest   '(a b c d e))   ; => (B C D E)
(last   '(a b c d e))   ; => (E)     (последняя ЯЧЕЙКА, не элемент!)

;; nth — доступ по индексу (с нуля), но он ЛИНЕЙНЫЙ:
(nth 0 '(a b c d e))    ; => A
(nth 2 '(a b c d e))    ; => C       (прошёл по cdr дважды)
(length '(a b c d e))   ; => 5       (тоже линейный — считает ячейки)

Подчеркнём ловушку: (nth 1000 lst) для длинного списка реально проходит тысячу ячеек. Если в вашем алгоритме часто нужен доступ по индексу, список — неподходящая структура; для этого есть векторы (массивы) с мгновенным доступом. Список оптимален для последовательной обработки, а не для случайного доступа. Заметьте также, что last возвращает последнюю ячейку (то есть список из одного элемента (E)), а не сам элемент, — чтобы получить элемент, берут (car (last lst)) или используют first от развёрнутого списка.

Поиск в списке

Часто нужно не просто пройти список, а найти в нём элемент или проверить наличие. Для этого есть member (ищет элемент и возвращает хвост, начиная с него), find (возвращает сам найденный элемент), position (возвращает индекс). Все они, разумеется, линейны — иначе и быть не может для связного списка.

;; Поиск в списке:
(member 3 '(1 2 3 4 5))   ; => (3 4 5)   хвост, начиная с найденного
(find 3 '(1 2 3 4 5))     ; => 3         сам элемент
(position 3 '(1 2 3 4 5)) ; => 2         индекс (с нуля)
(member 9 '(1 2 3))       ; => NIL       не найдено

Обратите внимание на изящную деталь: member возвращает не t, а хвост списка с найденного места. Это полезнее, чем просто «да/нет», и заодно работает как проверка: непустой хвост — истина, nil — ложь. Снова двойная природа nil из прошлого раздела делает код лаконичным: (if (member x lst) ...) читается как «если x есть в списке».

Список как стек: push и pop

Здесь всё сходится воедино. Мы знаем, что добавление в начало (cons) и снятие головы (car + переход на cdr) — операции мгновенные. А что такое стек? Структура, где кладут и снимают с одного конца. Значит, список — идеальный стек, если работать с его головой. Common Lisp даёт для этого удобные макросы push (положить элемент в начало) и pop (снять и вернуть первый элемент), которые модифицируют переменную-список.

;; Список как стек: push кладёт в начало, pop снимает с начала
(defparameter stack '())

(push 1 stack)     ; stack теперь (1)
(push 2 stack)     ; stack теперь (2 1)
(push 3 stack)     ; stack теперь (3 2 1)

(pop stack)        ; => 3   (снят с вершины), stack теперь (2 1)
(pop stack)        ; => 2   stack теперь (1)
stack              ; => (1)

Это не случайное совпадение, а прямое следствие устройства списка: голова — самый дешёвый конец, поэтому она и служит вершиной стека. push внутри — это просто cons с переприсваиванием переменной, а pop — взятие car с переходом переменной на cdr. Понимание, что стек на списке естественен, а очередь (где берут с другого конца) — нет, помогает выбирать правильные структуры данных.

Обход через преобразование: знакомство с mapcar

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

;; mapcar применяет функцию к каждому элементу и собирает результат:
(mapcar #'1+ '(1 2 3 4))         ; => (2 3 4 5)   прибавили 1 к каждому
(mapcar #'(lambda (x) (* x x))
        '(1 2 3 4))              ; => (1 4 9 16)  возвели в квадрат

;; mapcar может идти по нескольким спискам параллельно:
(mapcar #'+ '(1 2 3) '(10 20 30))   ; => (11 22 33)   поэлементная сумма

Сравните это с ручной рекурсией из начала урока: там мы явно писали базу, голову и хвост, а здесь — лишь сказали, что делать с элементом. Оба подхода обходят список последовательно по ячейкам и потому одинаковы по стоимости, но mapcar выразительнее и короче для типовых преобразований. Знак #' перед именем функции — это способ «взять функцию как значение» в Common Lisp, прямое следствие того, что он Lisp-2; этой важной теме посвящён отдельный урок следующего раздела.

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

Все перечисленные операции упираются в одно фундаментальное свойство: список можно проходить только вперёд, по одной ячейке за шаг, следуя по cdr. Отсюда чёткая карта стоимостей. Доступ к голове, push, pop — это работа с одной ячейкой, поэтому мгновенны (константная стоимость). А nth, length, member, find, обход целиком — все линейны, потому что в худшем случае проходят весь список. Эта карта — не абстракция, а практический инструмент: глядя на алгоритм, можно заранее сказать, во что обойдётся работа со списком.

Именно поэтому опытные программисты на Lisp строят алгоритмы так, чтобы работать с головой списка и обходить его последовательно, избегая повторного доступа по индексу. Если же задача по сути требует случайного доступа или работы с обоих концов, выбирают другую структуру — вектор или специализированную очередь. Список — не универсальный контейнер «на всё», а структура с конкретным профилем: дёшев на голове, линеен в глубине.

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

Первая ошибка — использовать nth в цикле по индексу, как делают в массивных языках: (dotimes (i (length lst)) (nth i lst)). Это катастрофа по производительности: и length, и каждый nth линейны, так что весь цикл квадратичен. Правильно перебирать список через dolist или loop ... in, которые идут по ячейкам один раз.

Вторая ошибка — путать last и «последний элемент». (last lst) возвращает последнюю ячейку — список из одного элемента, а не сам элемент. Чтобы получить значение последнего элемента, нужно (car (last lst)). Многие, ожидая элемент, получают список (E) и недоумевают.

Третья ошибка — пытаться сделать из списка очередь, добавляя в конец через append в цикле. Список хорош как стек (работа с головой), но плох как очередь (где нужен и другой конец): добавление в конец линейно, и цикл становится квадратичным. Для очереди в Lisp используют либо пару указателей на оба конца, либо просто копят элементы с головы через push, а в конце разворачивают reverse — это держит сложность линейной.

Итоги

• Списки обходят рекурсией по схеме «голова (car) и хвост (cdr)» с базой на пустом списке, либо итеративно через dolist и loop.
• Common Lisp богат итеративными формами (dolist, loop); Scheme минималистично выражает циклы хвостовой рекурсией, которую гарантированно оптимизирует.
• first/rest дёшевы, но nth, length, member, find линейны — список не подходит для частого доступа по индексу.
• push и pop работают с головой и мгновенны, поэтому список — естественный стек; last возвращает последнюю ячейку, а не элемент.
• Карта стоимостей: голова — мгновенно, глубина — линейно; для случайного доступа или очереди берут другие структуры (векторы, пары указателей).