Построение списков: list, cons, append

Учимся собирать списки тремя главными инструментами и понимать, что при этом происходит с памятью.

list создаёт новый список из аргументов, cons добавляет один элемент в начало списка, append склеивает несколько списков в один. Различие между ними — не в результате, а в том, какие ячейки создаются заново, а какие переиспользуются.

В прошлом уроке мы выяснили, что список — это цепочка cons-ячеек. Теперь научимся эти цепочки строить. Инструментов на первый взгляд несколько похожих — list, cons, append, — и новички часто путают, какой когда применять. Разобраться легко, если всё время держать в голове картину ячеек: тогда становится очевидно, что каждый инструмент делает с памятью и почему результаты различаются.

list: собрать список из элементов

Самый прямой способ — функция list. Она принимает любое число аргументов и строит из них новый правильный список, по ячейке на каждый аргумент, с завершающим nil. Аргументы предварительно вычисляются (в отличие от кавычки, которая берёт всё буквально), поэтому list удобен, когда элементы — это результаты вычислений, а не литералы.

;; list строит список из ВЫЧИСЛЕННЫХ аргументов:
(list 1 2 3)            ; => (1 2 3)
(list (+ 1 1) (* 2 3))  ; => (2 6)    (аргументы вычислены!)
(list 'a 'b 'c)         ; => (A B C)
(list)                  ; => NIL      (пустой список)

;; Сравните с кавычкой, которая НЕ вычисляет:
'((+ 1 1) (* 2 3))      ; => ((+ 1 1) (* 2 3))   (списки как есть)

Разница между (list (+ 1 1)) и '((+ 1 1)) — ровно та, что мы разбирали в уроке про кавычку: list вычисляет элементы (получаем (2)), а кавычка цитирует (получаем список из выражения ((+ 1 1))). Выбор между ними — это выбор «нужны ли мне вычисленные значения или буквальные данные».

cons: добавить в начало

Функция cons, как мы знаем, создаёт одну ячейку. Если её вторым аргументом передать список, получится новый список с добавленным в начало элементом — ведь новая ячейка просто указывает своим cdr на старый список. Это и есть канонический способ «приписать элемент к голове», и он очень дёшев: создаётся ровно одна ячейка, а исходный список не копируется.

;; cons добавляет элемент в начало (одна новая ячейка):
(cons 0 '(1 2 3))       ; => (0 1 2 3)
(cons 'x '(a b))        ; => (X A B)
(cons 1 nil)            ; => (1)        (добавили к пустому списку)

;; ВАЖНО: если второй аргумент НЕ список — выйдет точечная пара:
(cons 1 2)              ; => (1 . 2)    (атом во втором поле)
(cons 1 '(2))           ; => (1 2)      (а вот так — список)

Тонкость, на которой все спотыкаются: cons даёт список, только если его второй аргумент — список (или nil). Если второй аргумент — атом, получится точечная пара (1 . 2), а не список. Это прямое следствие того, что мы изучили: список держится на том, что cdr ведёт к следующей ячейке или к nil. Поэтому (cons 1 '(2)) даёт (1 2), а (cons 1 2) — пару.

append: склеить списки

Когда нужно соединить несколько списков в один, используют append. Она принимает несколько списков и возвращает новый список, содержащий все их элементы по порядку. Но здесь скрыт важный нюанс производительности и памяти: append копирует все списки, кроме последнего. Чтобы понять почему, снова представим ячейки.

;; append склеивает списки в один:
(append '(1 2) '(3 4))         ; => (1 2 3 4)
(append '(a) '(b) '(c))        ; => (A B C)
(append '(1 2) nil '(3))       ; => (1 2 3)
(append nil '(1 2))            ; => (1 2)

Чтобы соединить (1 2) и (3 4), нельзя просто заставить последнюю ячейку первого списка указывать на второй: это изменило бы исходный список (1 2), а append не имеет права портить свои аргументы. Поэтому append копирует ячейки всех списков, кроме последнего, и в копии последняя ячейка указывает на оригинал последнего списка. Последний список не копируется — он переиспользуется как есть. Отсюда правило: append тем дороже, чем длиннее начальные списки, потому что их приходится копировать целиком.

Разделяемая структура: списки делят хвосты

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

;; Два списка делят общий хвост:
(defparameter tail '(2 3))
(defparameter a (cons 1 tail))     ; a = (1 2 3)
(defparameter b (cons 9 tail))     ; b = (9 2 3)

;; a и b делят ОДИН и тот же хвост (2 3):
(eq (cdr a) (cdr b))               ; => T   (это одна и та же цепочка!)
(eq (cdr a) tail)                  ; => T

Здесь a и b физически делят одни и те же ячейки (2 3). Создание a и b через cons добавило лишь по одной новой ячейке в начало, а хвост остался общим. Это эффективно, но означает, что если деструктивно изменить хвост tail, изменения проявятся и в a, и в b сразу — ведь это буквально одни и те же ячейки. Деструктивным операциям и связанным с ними ловушкам посвящён отдельный урок этого раздела; пока запомните, что переиспользование хвостов — это и сила, и источник коварных багов.

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

Копирование и заготовки

Раз списки умеют делить структуру, иногда нужно явно сделать независимую копию, чтобы спокойно её менять, не задев оригинал. Для этого есть copy-list — она создаёт новый набор ячеек верхнего уровня с теми же элементами. Важно понимать её границу: copy-list копирует только «позвоночник» списка (его ячейки), но не копирует сами элементы. Если элементы — вложенные списки, копия и оригинал будут делить эти вложенные структуры. Для полного, рекурсивного копирования существует copy-tree, которая дублирует и вложенные списки.

;; copy-list делает независимую копию верхнего уровня:
(defparameter orig '(1 2 3))
(defparameter dup (copy-list orig))
(eq orig dup)              ; => NIL   (разные ячейки)
(equal orig dup)          ; => T     (но содержимое совпадает)

;; make-list создаёт список заданной длины из одинаковых элементов:
(make-list 4)             ; => (NIL NIL NIL NIL)
(make-list 3 :initial-element 0)   ; => (0 0 0)

Функция make-list полезна, когда нужна «заготовка» — список заданной длины, заполненный одинаковым значением, который затем будет постепенно заполнен. Обратите внимание на ключевой параметр :initial-element — это снова тот самый ключевой символ из прошлого раздела, задающий начальное значение. Эти инструменты — copy-list, copy-tree, make-list — дополняют тройку cons/list/append и вместе покрывают почти все потребности в создании списков. Знание о том, что copy-list копирует лишь верхний уровень, особенно важно: рассчитывая на полную копию, но получив поверхностную, легко случайно изменить общие вложенные данные.

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

Сведём поведение трёх инструментов в таблицу с точки зрения создаваемых ячеек — это и есть ключ к их правильному применению:

Операция	Что делает	Сколько ячеек создаёт
`(cons x lst)`	добавляет x в начало	одну новую ячейку
`(list a b c)`	строит список из элементов	по одной на элемент
`(append l1 l2)`	склеивает списки	копии всех, кроме последнего

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

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

Первая ошибка — пытаться добавить элемент в конец через cons. cons добавляет только в начало; запись (cons '(1 2 3) 4) не приклеит 4 в конец, а создаст странную структуру, где целый список лежит в car. Чтобы добавить в конец, нужен append с одноэлементным списком: (append '(1 2 3) '(4)). И помните, что это дорого (копирует начало), поэтому добавление в конец в Lisp избегают, когда могут.

Вторая ошибка — случайно получить точечную пару, перепутав cons и list. (cons 1 2) — это пара (1 . 2), а не список (1 2); чтобы получить список из двух элементов, нужно (list 1 2) или (cons 1 (cons 2 nil)). Если в выводе внезапно появилась точка — почти наверняка где-то cons получил атом вместо списка во второе поле.

Третья ошибка — забывать про разделяемую структуру. Раз cons и append переиспользуют хвосты, два списка могут незаметно делить ячейки. Пока вы только читаете списки, это безвредно и полезно. Но стоит применить деструктивную операцию к общему хвосту — и изменения «протекут» в другие списки. Безопасное правило новичка: предпочитать недеструктивные операции (cons, append, remove), которые строят новое, а деструктивные использовать осознанно, понимая, что они меняют существующие ячейки.

Итоги

list строит новый список из вычисленных аргументов (по ячейке на элемент); кавычка, в отличие от него, цитирует буквально.
cons добавляет один элемент в начало, создавая ровно одну ячейку; если второй аргумент не список, получается точечная пара.
append склеивает списки, копируя все, кроме последнего; поэтому он тем дороже, чем длиннее начальные списки.
Списки могут делить общий хвост (разделяемая структура) — это экономит память, но опасно при деструктивном изменении общих ячеек.
Рост «с головы» через cons дёшев; добавление в конец и многократный append дороги — типичный источник квадратичной медлительности.