206 |
Глава 12. Структура |
> whole (A B E)
Разумеется, то же самое будет происходить и для двух списков, имею щих общий хвост.
Изменение двух объектов одновременно не всегда является ошибкой. Иногда это именно то, что нужно. Однако если такое изменение проис ходит непреднамеренно, оно может привести к некорректной работе программы. Опытные программисты умеют избегать подобных ошибок и немедленно распознавать такие ситуации. Если список без видимой причины меняет свое содержимое, вероятно, он имеет разделяемую структуру.
Опасна не сама разделяемая структура, а возможность ее изменения. Чтобы гарантировать отсутствие подобных ошибок, просто избегайте использования setf (а также аналогичных операторов типа pop, rplaca и других) для списков. Если изменяемость списков все же требуется, то необходимо выяснить, откуда взялся изменяемый список, чтобы убе диться, что он не делит структуру с чем-то, что нельзя менять. Если же это не так или вам неизвестно происхождение списка, то модифициро вать необходимо не сам список, а его копию.
Нужно быть вдвойне осторожным при использовании функций, напи санных кем-то другим. Пока не установлено обратное, имейте в виду, что все, что передается функции:
1.Может быть передано деструктивным операторам.
2.Может быть сохранено где-либо, и изменение этого объекта приведет к изменению в других частях кода, использующего данный объект.1
Вобоих случаях правильным решением является копирование аргу ментов.
ВCommon Lisp вызов любой функции, выполняющейся во время про хода по структуре (например, функции-аргумента mapcar или remove-if), не должен менять эту структуру. В противном случае последствия вы полнения такого кода не определены.
12.3.Пример: очереди
Разделяемые структуры – это не только повод для беспокойства. Ино гда они могут быть полезны. В этом разделе показано, как с помощью разделяемых структур представить очереди. Очередь – это хранилище объектов, из которого они могут быть извлечены по одному в том же
1Например, в Common Lisp попытка изменения строки, используемой как имя символа, считается ошибкой. И поскольку нам неизвестно, копирует ли intern свой аргумент-строку перед созданием символа, мы должны пред положить, что модификация любой строки, которая передавалась в intern, приведет к ошибке.
12.3. Пример: очереди |
207 |
порядке, в котором они были туда записаны. Такую модель принято именовать FIFO – сокращение от «первым пришел, первым ушел» («first in, first out»).
С помощью списков легко представить стопку, так как добавление и по лучение элементов происходит с одного конца. Задача представления очереди более сложна, поскольку добавление и извлечение объектов про исходит с разных концов. Для эффективной ее реализации необходимо каким-то образом обеспечить управление обоими концами списка.
Одна из возможных стратегий приводится на рис. 12.6, где показана очередь из трех элементов: a, b и c. Очередью считаем точечную пару, состоящую из списка и последней ячейки этого же списка. Будем назы вать их начало и конец. Чтобы получить элемент из очереди, необходи мо просто извлечь начало. Чтобы добавить новый элемент, необходимо создать новую ячейку, сделать ее cdr конца очереди и затем сделать ее же концом.
q1 =
nil
a |
b |
с |
Рис. 12.6. Структура очереди
Такую стратегию реализует код на рис. 12.7.
(defun make-queue () (cons nil nil))
(defun enqueue (obj q) (if (null (car q))
(setf (cdr q) (setf (car q) (list obj))) (setf (cdr (cdr q)) (list obj)
(cdr q) (cdr (cdr q))))
(car q))
(defun dequeue (q) (pop (car q)))
Рис. 12.7. Реализация очередей
Она используется следующим образом:
> (setf q1 (make-queue)) (NIL)
208 |
Глава 12. Структура |
> (progn (enqueue ’a q1) (enqueue ’b q1) (enqueue ’c q1))
(A B C)
Теперь q1 представляет очередь, изображенную на рис. 12.6:
> q1
((A B C) C)
Попробуем забрать из очереди несколько элементов:
>(dequeue q1)
A
>(dequeue q1)
B
>(enqueue ’d q1) (C D)
12.4.Деструктивные функции
Common Lisp включает в себя несколько функций, которые могут изме нять структуру списков и за счет этого работать быстрее. Они называ ются деструктивными. И хотя эти функции могут изменять ячейки, переданные им в качестве аргументов, они делают это не ради побоч ных эффектов.
Например, delete является деструктивным аналогом remove. Хотя ей и позволено портить переданный список, она не дает никаких обеща ний, что так и будет делать. Посмотрим, что происходит в большинстве реализаций:
>(setf lst ’(a r a b i a)) (A R A B I A)
>(delete ’a lst)
(R B I) > lst
(A R B I)
Как и в случае с remove, чтобы зафиксировать побочный эффект, необхо димо использовать setf:
(setf lst (delete ’a lst))
Примером того, как деструктивные функции модифицируют списки, яв ляется nconc, деструктивная версия append.1 Приведем ее версию для двух аргументов, демонстрирующую, каким образом сшиваются списки:
(defun nconc2 (x y) (if (consp x)
1Буква n в имени nconc соответствует «non-consing». Имена многих деструк тивных функций начинаются с n.
12.5. Пример: двоичные деревья поиска |
209 |
(progn
(setf (cdr (last x)) y) x)
y))
cdr последней ячейки первого списка становится указателем на второй список. Полноценная версия для произвольного числа аргументов при водится в приложении B.
Функция mapcan похожа на mapcar, но соединяет в один список возвра щаемые значения (которые должны быть списками) с помощью nconc:
> (mapcan #’list ’(a b c)
’(1 2 3 4)) (A 1 B 2 C 3)
Эта функция может быть определена следующим образом:
(defun our-mapcan (fn &rest lsts)
(apply #’nconc (apply #’mapcar fn lsts)))
Используйте mapcan с осторожностью, учитывая ее деструктивный ха рактер. Она соединяет возвращаемые списки с помощью nconc, поэтому их лучше больше нигде не задействовать.
Функция mapcan полезна, в частности, в задачах, интерпретируемых как сбор всех узлов одного уровня некоего дерева. Например, если children возвращает список чьих-то детей, тогда мы сможем определить функ цию для получения списка внуков так:
(defun grandchildren (x) (mapcan #’(lambda (c)
(copy-list (children c))) (children x)))
Данная функция применяет copy-list к результату вызова children, так как он может возвращать уже существующий объект, а не производить новый.
Также можно определить недеструктивный вариант mapcan:
(defun mappend (fn &rest lsts)
(apply #’append (apply #’mapcar fn lsts)))
Используя mappend, мы можем обойтись без вызовов copy-list в опреде лении grandchildren:
(defun grandchildren (x)
(mappend #’children (children x)))
12.5.Пример: двоичные деревья поиска
Внекоторых ситуациях уместнее использовать деструктивные опера ции, нежели недеструктивные. В разделе 4.7 было показано, как управ
210 |
Глава 12. Структура |
лять двоичными деревьями поиска (BST). Все использованные там функ ции были недеструктивными, но если нужно применить BST на практи ке, такая осторожность излишня.
На рис. 12.8 приведена деструктивная версия bst-insert (стр. 86). Она принимает точно такие же аргументы и возвращает точно такое же зна чение, как и исходная версия. Единственным отличием является то, что она может изменять дерево, передаваемое вторым аргументом.
(defun bst-insert! (obj bst <) (if (null bst)
(make-node :elt obj) (progn (bsti obj bst <)
bst)))
(defun bsti (obj bst <)
(let ((elt (node-elt bst))) (if (eql obj elt)
bst
(if (funcall < obj elt) (let ((l (node–l bst)))
(if l
(bsti obj l <) (setf (node–l bst)
(make-node :elt obj)))) (let ((r (node-r bst)))
(if r
(bsti obj r <) (setf (node-r bst)
(make-node :elt obj))))))))
Рис. 12.8. Двоичные деревья поиска: деструктивная вставка
В разделе 2.12 было предупреждение о том, что деструктивные функ ции вызываются не ради побочных эффектов. Поэтому если вы хотите построить дерево с помощью bst-insert!, вам нужно вызывать ее так же, как если бы вы вызывали настоящую bst-insert:
>(setf *bst* nil) NIL
>(dolist (x ’(7 2 9 8 4 1 5 12))
(setf *bst* (bst-insert! x *bst* #’<)))
NIL
Вы могли бы также определить аналог push для BST, но это довольно сложно и выходит за рамки данной книги. (Для любопытных такой макрос определяется на стр. 429.°)
12.5. Пример: двоичные деревья поиска |
211 |
На рис. 12.91 представлен деструктивный вариант функции bst-delete, которая связана с bst-remove (стр. 89) так же, как delete связана с remove. Как и delete, она не подразумевает вызов ради побочных эффектов. Ис пользовать bst-delete необходимо так же, как и bst-remove:
>(setf *bst* (bst-delete 2 *bst* #’<)) #<7>
>(bst-find 2 *bst* #’<)
NIL
(defun bst-delete (obj bst <) (if (null bst)
nil
(if (eql obj (node-elt bst)) (del-root bst)
(progn
(if (funcall < obj (node-elt bst))
(setf (node-l bst) (bst-delete obj (node-l bst) <)) (setf (node-r bst) (bst-delete obj (node-r bst) <)))
bst))))
(defun del-root (bst)
(let ((l (node-l bst)) (r (node-r bst)))
(cond ((null l) r) |
|
((null r) l) |
|
(t |
(if (zerop (random 2)) |
|
(cutnext r bst nil) |
(cutprev l bst nil))))))
(defun cutnext (bst root prev) (if (node-l bst)
(cutnext (node-l bst) root bst)
(if prev |
|
(progn |
|
(setf (node-elt root) |
(node-elt bst) |
(node-l prev) |
(node-r bst)) |
root) |
|
(progn |
|
(setf (node-l bst) |
(node-l root)) |
bst)))) |
|
(defun cutprev (bst root prev) (if (node-r bst)
(cutprev (node-r bst) root bst) (if prev
(progn
(setf (node-elt root) (node-elt bst)
1Данный листинг содержит исправленную версию bst-delete. За подробно стями обращайтесь к сноске на стр. 89. – Прим. перев.