Регистрация | Войти
Lisp — программируемый язык программирования
Предыдущая Оглавление Следующая

13. Не только списки: другие применения cons-ячеек

Как вы увидели в предыдущей главе, списочный тип данных является иллюзией, созданной множеством функций, которые манипулируют cons-ячейками. Common Lisp также предоставляет функции, позволяющие вам обращаться со структурами данных, созданными из cons-ячеек, как c деревьями, множествами, и таблицами поиска (lookup tables). В этой главе я дам вам краткий обзор некоторых из этих структур данных и оперирующих с ними функций. Как и в случае функций, работающих со списками, многие из них будут полезны когда вы начнете писать более сложные макросы, где потребуется обращаться с кодом Lisp как с данными.

Деревья

Рассматривать структуры созданные из cons-ячеек как деревья так же естественно, как рассматривать их как списки. Ведь что такое список списков, как не другое представление дерева? Разница между функцией, которая обращается с группой cons-ячеек как со списком, и функцией, обращающейся с той же группой cons-ячеек, как с деревом, определяется тем, какие ячейки обходят эти функции при поиске значений для дерева или списка. Те сons-ячейки, которые обходит функция работы со списком, называются списочной структурой, и располагаются начиная от первой cons-ячейки и затем следуя ссылкам по CDR, пока не достигнут NIL. Элементами списка являются объекты, на которые ссылаются CAR'ы cons-ячеек списочной структуры. Если cons-ячейка в списочной структуре имеет CAR, который ссылается на другую cons-ячейку, то та ячейка, на которую ведет ссылка, считается головой и элементом внешнего списка.1) Древовидная структура, с другой стороны, при обходе следует ссылкам как по CAR, так и по CDR, пока они указывают на другие cons-ячейки. Таким образом, значениями в древовидной структуре являются атомы – такие значения, которые не являются cons-ячейками, и на которые ссылаются CAR'ы или CDR'ы cons-ячеек в древовидной структуре.

Например, следующая стрелочная диаграмма показывает cons-ячейки, составляющие список из списков: ((1 2) (3 4) (5 6)). Списочная структура включает в себя только три cons-ячейки внутри пунктирного блока, тогда как древовидная структура включает все ячейки.

Изображение

Чтобы увидеть разницу между функцией, работающей со списком, и функцией, работающей с деревом, вы можете рассмотреть как функции COPY-LIST и COPY-TREE будут копировать эту группу cons-ячеек. COPY-LIST, как функция, работающая со списком, копирует cons-ячейки, которые составляют списочную структуру. Другими словами, она создает новые cons-ячейки соответственно для каждой из cons-ячеек пунктирного блока. CAR'ы каждой новой ячейки ссылаются на тот же объект, что и CAR'ы оригинальных cons-ячеек в списочной структуре. Таким образом, COPY-LIST не копирует подсписки (1, 2), (3 4), или (5 6), как показано на этой диаграмме:

Изображение

COPY-TREE, с другой стороны, создает новые cons-ячейки для каждой из cons-ячеек на диаграмме и соединяет их вместе в одну структуру, как показано на следующей диаграмме:

Изображение

Там где cons-ячейки в оригинале ссылаются на атомарное значение, соответствующие им cons-ячейки в копии будут ссылаться на то же значение. Таким образом, единственными объектами, на которые ссылаются как оригинальное дерево, так и его копия, созданная COPY-TREE, будут числа 5, 6, и символ NIL.

Еще одна функция, которая обходит как CAR'ы так и CDR'ы cons-ячеек дерева это TREE-EQUAL, которая сравнивает два дерева, и считает их равными, если их структуры имеют одинаковую форму и если их листья равны относительно EQL (или если они удовлетворяют условию, задаваемому через именованный аргумент :test).

Прочими ориентированными на деревья функциями являются работающие с деревьями аналоги функций для последовательностей SUBSTITUTE и NSUBSTITUTE, и их -IF и -IF-NOT варианты. Функция SUBST, как и SUBSTITUTE, принимает новый элемент, старый элемент и дерево (в отличие от последовательности), вместе с именованными аргументами :key и :test, и возвращает новое дерево с той же формой, что и исходное, но все вхождения старого элемента заменяются новым. Например:

CL-USER> (subst 10 1 '(1 2 (3 2 1) ((1 1) (2 2))))
(10 2 (3 2 10) ((10 10) (2 2)))

SUBST-IF аналогична SUBSTITUTE-IF. Но вместо старого элемента, она принимает одноаргументную функцию, которая вызывается с аргументом в виде каждого атомарного значения в дереве, и всякий раз, когда она возвращает истину, текущая позиция в новом дереве заменяется новым значением. SUBST-IF-NOT действует также, за исключением того, что заменяются те значения, где функция возвращает NIL. NSUBST, NSUBST-IF, и NSUBST-IF-NOT - это утилизирующие аналоги соответствующих версий SUBST-функций. Как и с другими утилизирующими функциями, вам следует использовать эти функции только как замещение (после профилирования) их недеструктивных аналогов, в ситуациях, где вы уверены, что нет опасности повреждения разделяемой структуры. В частности, вы должны продолжать сохранять возвращаемые значения этих функций, пока у вас нет гарантии, что результат будет равен, по предикату EQ, оригинальному дереву. 2)

Множества

Множества также могут быть реализованы посредством cons-ячеек. Фактически, вы можете обращаться с любым списком как с множеством - Common Lisp предоставляет несколько функций для выполнения теоретико-множественных операций над списками. Тем не менее вам следует помнить, что из-за особенности устройства списков эти операции становятся тем менее и менее эффективными, чем больше становится множество.

Впрочем, используя встроенные функции для работы с множествами легко писать оперирующий с множествами код. И для небольших множеств они могут быть более эффективными, чем их альтернативы. Если профилирование показывает вам, что производительность этих функций является узким местом вашего кода, вы всегда можете заменить множества на основе списков множествами, основанными на хэш-таблицах или битовых векторах.

Для создания множества вы можете использовать функцию ADJOIN. ADJOIN принимает в качестве аргументов элемент и список, представляющий множество, и возвращает список, содержащий этот элемент вместе со всеми элементами исходного множества. Для того, чтобы определить, присутствует ли элемент в множестве, функция просматривает список, и если элемент не найден, то ADJOIN создает новую cons-ячейку, содержащую этот элемент, ссылающуюся на исходный список, и возвращает ее. В противном случае она возвращает исходный список.

ADJOIN также принимает именованные аргументы :key и :test, которые используются при определении - присутствует ли элемент в исходном списке. Подобно CONS, ADJOIN не воздействует на исходный список – если вы хотите модифицировать определенный список, вам нужно присвоить значение, возвращаемое ADJOIN, тому месту, в котором хранился исходный список. Деструктивный макрос PUSHNEW сделает это для вас автоматически.

CL-USER> (defparameter *set* ())
*SET*
CL-USER> (adjoin 1 *set*)
(1)
CL-USER> *set*
NIL
CL-USER> (setf *set* (adjoin 1 *set*))
(1)
CL-USER> (pushnew 2 *set*)
(2 1)
CL-USER> *set*
(2 1)
CL-USER> (pushnew 2 *set*)
(2 1)

Вы можете проверить, принадлежит ли данный элемент множеству с помощью функции MEMBER и родственных ей функций MEMBER-IF и MEMBER-IF-NOT. Эти функции похожи на функции для работы с последовательностями - FIND, FIND-IF, и FIND-IF-NOT, за исключением того, что они используются только со списками. Вместо того, чтобы вернуть элемент, когда он присутствует в множестве, они возвращают cons-ячейку содержащую элемент - другими словами, подсписок начинающийся с заданного элемента. Если искомый элемент отсутствует в списке, все три функции возвращают NIL.

Оставшиеся ориентированные на множества функции предоставляют операции с группами элементов: INTERSECTION, UNION, SET-DIFFERENCE, и SET-EXCLUSIVE-OR. Каждая из этих функций принимает два списка и именованные аргументы :key и :test и возвращает новый список, представляющий множество, полученное выполнением соответствующей операции над двумя списками. INTERSECTION возвращает список, содержащий все аргументы из обоих списков. UNION возвращает список, содержащий один экземпляр каждого уникального элемента из двух своих аргументов.3) SET-DIFFERENCE возвращает список, содержащий все элементы из первого аргумента, которые не встречаются во втором аргументе. И SET-EXCLUSIVE-OR возвращает список, содержащий элементы, находящиеся только в одном либо в другом списках, переданных в качестве аргументов, но не в обоих одновременно. Каждая из этих функций также имеет утилизирующий аналог, имя которого получается добавлением N в качестве префикса.

В заключение, функция SUBSETP принимает в качестве аргументов два списка и обычные именованные аргументы :key и :test и возвращает истину, если первый список является подмножеством второго - то есть, если каждый элемент первого списка также присутствует во втором списке. Порядок элементов в списках значения не имеет.

CL-USER> (subsetp '(3 2 1) '(1 2 3 4))
T
CL-USER> (subsetp '(1 2 3 4) '(3 2 1))
NIL

Таблицы поиска: ассоциативные списки и списки свойств

Помимо деревьев и множеств вы можете создавать таблицы, которые отображают ключи на значения вне cons-ячеек. Обычно используются две разновидности основанных на cons-ячейках таблиц поиска, об обеих я вскользь упоминал в предыдущих главах. Это ассоциативные списки (association lists или alists) и списки свойств (property lists или plists). Вам не стоит использовать списки свойств или ассоциативные списки для больших таблиц - для них нужно использовать хэш-таблицы, но стоит знать, как работать с ними обоими, так как для небольших таблиц они могут быть более эффективны, чем хэш-таблицы, и еще потому, что у них есть несколько полезных собственных свойств. Ассоциативный список - это структура данных, которая отображает ключи на значения, а также поддерживает обратный поиск, находя ключ по заданному значению. Ассоциативные списки также поддерживают возможность добавления отображений ключ/значение, которые скрывают существующие отображения таким образом, что скрывающие отображения могут быть позже удалены и первоначальные отображения снова станут видимы.

Если смотреть глубже, то на самом деле ассоциативный список - это просто список, чьи элементы сами является cons-ячейками. Каждый элемент можно представлять как пару ключ/значение с ключом в CAR cons-ячейки и значением в CDR. К примеру, следующая стрелочная диаграмма представляет ассоциативный список, состоящий из отображения символа A в номер 1, B в номер 2, и C в номер 3:

Изображение

Если значение CDR не является списком, то cons-ячейки, представляющие пары ключ/значение, будут точечными парами в терминах s-выражений. Ассоциативный список, представленный на предыдущей диаграмме, к примеру, будет напечатан вот так:

((A . 1) (B . 2) (C . 3))

Главная процедура поиска для ассоциативных списков это ASSOC, которая принимает ключ и ассоциативный список в качестве аргументов, и возвращает первую cons-ячейку, чей CAR соответствует ключу или является NIL, если совпадения не найдено.

CL-USER> (assoc 'a '((a . 1) (b . 2) (c . 3)))
(A . 1)
CL-USER> (assoc 'c '((a . 1) (b . 2) (c . 3)))
(C . 3)
CL-USER> (assoc 'd '((a . 1) (b . 2) (c . 3)))
NIL

Чтобы получить значение, соответствующее заданному ключу, вам следует просто передать результат ASSOC СDR'у.

CL-USER> (cdr (assoc 'a '((a . 1) (b . 2) (c . 3))))
1

По умолчанию заданный ключ сравнивается с ключами в ассоциативном списке, используя предикат EQL, но вы можете изменить его с помощью стандартной комбинации из именованных аргументов :key и :test. Например, если вы хотите использовать строковые ключи, то можете написать так:

CL-USER> (assoc "a" '(("a" . 1) ("b" . 2) ("c" . 3)) :test #'string=)
("a" . 1)

Без явного задания в качестве :test предиката STRING= ASSOC вероятно вернул бы NIL, потому что две строки с одинаковым содержимым необязательно равны относительно EQL.

CL-USER> (assoc "a" '(("a" . 1) ("b" . 2) ("c" . 3)))
NIL

Поскольку при поиске ASSOC просматривает список с начала, одна пара ключ/значение в ассоциативном списке может скрывать другие пары с тем же ключом, но находящиеся дальше в списке.

CL-USER> (assoc 'a '((a . 10) (a . 1) (b . 2) (c . 3)))
(A . 10)

Вы можете добавить пару в начало списка с помощью функции CONS, как здесь:

(cons (cons 'new-key 'new-value) alist)

Однако для удобства Common Lisp предоставляет функцию ACONS, которая позволяет вам написать так:

(acons 'new-key 'new-value alist)

Подобно CONS, ACONS является функцией и, следовательно, не может модифицировать место, откуда был передан исходный ассоциативный список. Если вы хотите модифицировать ассоциативный список, вам нужно написать так:

(setf alist (acons 'new-key 'new-value alist))

или так:

(push (cons 'new-key 'new-value) alist)

Очевидно, время затраченное на поиск в ассоциативном списке при использовании ASSOC, является функцией от того, насколько глубоко в списке находится соответствующая пара. В худшем случае для определения, что никакая пара не соответствует искомой, ASSOC требуется просмотреть каждый элемент списка. Тем не менее, поскольку основной механизм работы ассоциативных списков довольно прост, то на небольших таблицах ассоциативный список может превзойти в производительности хэш-таблицу. Также ассоциативные списки могут дать вам большую гибкость при выполнении поиска. Ранее я отмечал, что ASSOC принимает именованные аргументы :key и :test. Если они не соответствуют вашим требованиям, вы можете использовать функции ASSOC-IF и ASSOC-IF-NOT, которые возвращают первую пару ключ/значение, чей CAR удовлетворяет (или не удовлетворяет, в случае ASSOC-IF-NOT) предикату, передаваемому вместо ключа. Еще три функции - RASSOC, RASSOC-IF, и RASSOC-IF-NOT действуют так же, как и соответствующие аналогичные ASSOC-функции, за исключением того, что они используют значение в CDR каждого элемента как ключ, совершая обратный поиск.

Функция COPY-ALIST похожа на COPY-TREE за исключением того, что вместо копирования всей древовидной структуры, она копирует только те cons-ячейки, которые составляют списочную структуру, плюс те cons-ячейки, на которые ссылаются CAR'ы этих ячеек. Другими словами, исходный ассоциативный список и его копия будут оба содержать одинаковые объекты как в виде ключей, так и значений, даже если ключи или значения будут состоять из cons-ячеек.

Наконец вы можете создать ассоциативный список из двух различных списков ключей и значений с помощью функции PAIRLIS. Получившийся ассоциативный список может содержать пары либо в том порядке, в каком они были в исходных списках, либо в обратном порядке. Например, вы можете получить такой результат:

CL-USER> (pairlis '(a b c) '(1 2 3))
((C . 3) (B . 2) (A . 1))

Или вы можете получить следующее:

CL-USER> (pairlis '(a b c) '(1 2 3))
((A . 1) (B . 2) (C . 3))

Другой разновидностью таблицы поиска является список свойств (property list или сокращенно plist), который вы использовали для представления строк базы данных в Главе 3. Структурно список свойств есть просто обычный список с ключами и значениями в виде чередующихся величин. К примеру, список свойств отображающий A, B, и C, на 1, 2, и 3 это просто список (A 1 B 2 C 3). На стрелочной диаграмме он выглядит так:

Изображение

Впрочем, списки свойств являются менее гибкими, чем ассоциативные списки. В действительности, список свойств поддерживает только одну фундаментальную операцию поиска, функцию GETF, которая принимает список свойств и ключ, и возвращает связанное с ключом значение, или NIL, если ключ не найден. GETF также принимает необязательный третий аргумент, который возвращается вместо NIL, если ключ не найден.

В отличие от ASSOC, которая использует EQL как проверочный предикат по умолчанию и позволяет использовать другой проверочный предикат в виде именованного аргумента :test, GETF всегда использует EQ для проверки, совпадает ли переданный ей ключ с ключами списка свойств. Следовательно, вам никогда не следует использовать числа или знаки в качестве ключей в списке свойств; как вы видели в Главе 4, поведение EQ для этих типов данных фактически не определено. На практике, ключи в списке свойств почти всегда являются символами, с тех пор как списки свойств были впервые изобретены для реализации "свойств" символов, то есть произвольных отображений между именами и значениями.

Вы можете использовать SETF вместе с GETF для установки переменной с заданным ключом. SETF также обращается с GETF немного особым образом, при котором первый аргумент GETF считается модифицируемым. Таким образом вы можете вызвать SETF поверх GETF для добавления новых пар ключ/значение к существующему списку свойств.

CL-USER> (defparameter *plist* ())
*PLIST*
CL-USER> *plist*
NIL
CL-USER> (setf (getf *plist* :a) 1)
1
CL-USER> *plist*
(:A 1)
CL-USER> (setf (getf *plist* :a) 2)
2
CL-USER> *plist*
(:A 2)

Чтобы удалить пару ключ/значение из списка свойств, вы можете использовать макрос REMF, который присваивает месту, переданному в качестве своего первого аргумента, список свойств, содержащий все пары ключ/значение, за исключением заданной. Он возвращает истину если заданный ключ был найден.

CL-USER> (remf *plist* :a)
T
CL-USER> *plist*
NIL

Как и GETF, REMF всегда использует EQ для сравнения заданного ключа с ключами в списке свойств.

Поскольку списки свойств часто используются в ситуациях, когда вы хотите извлечь несколько значений свойств из одного и того же списка, Common Lisp предоставляет функцию GET-PROPERTIES, которая делает более эффективным извлечение нескольких значений из одного списка свойств. Она принимает список свойств и список ключей для поиска, и возвращает, в виде множества значений (multiple values), первый найденный ключ, соответствующее ему значение, и голову списка, начинающегося с этого ключа. Это позволяет вам обработать список свойств, извлекая из него нужные свойства, без продолжительного повторного поиска с начала списка. К примеру, следующая функция эффективно обрабатывает, используя гипотетическую функцию process-property, все пары ключ/значение в списке свойств для заданного списка ключей:

(defun process-properties (plist keys)
  (loop while plist do
        (multiple-value-bind (key value tail) (get-properties plist keys)
          (when key (process-property key value))
          (setf plist (cddr tail))
)
)
)

Последней особенностью списков свойств является их отношение к символам: каждый символический объект имеет связанный список свойств, который может быть использован для хранения информации о символе. Список свойств может быть получен с помощью функции SYMBOL-PLIST. Тем не менее, обычно вам редко необходим весь список свойств; чаще вы будете использовать функцию GET, которая принимает символ и ключ и выполняет роль сокращенной записи для GETF с аргументами в виде того же ключа и списка символов, возвращаемого SYMBOL-PLIST.

(get 'symbol 'key) === (getf (symbol-plist 'symbol) 'key)

Как с GETF, к возвращаемому значению GET можно применить SETF, так что вы можете присоединить произвольную информацию к символу, как здесь:

(setf (get 'some-symbol 'my-key) "information")

Чтобы удалить свойство из списка свойств символа, вы можете использовать либо REMF поверх SYMBOL-PLIST или удобную функцию REMPROP 4)

(remprop 'symbol 'key) === (remf (symbol-plist 'symbol) 'key)

Возможность связывать произвольную информацию с именами довольно удобна, если вы занимаетесь какого-либо рода символическим программированием. К примеру, один макрос, который вы напишете в Главе 24, будет связывать информацию с именами, которую другие экземпляры того же макроса будут извлекать и использовать при генерации собственных расширений.

DESTRUCTURING-BIND

Последний инструмент для разделки и нарезки списков, о котором я должен рассказать, поскольку он понадобится вам в дальнейших главах - это макрос DESTRUCTURING-BIND. Этот макрос предоставляет способ деструктурировать произвольные списки, подобно тому, как списки параметров макроса могут разбирать на части свои списки аргументов. Основной скелет DESTRUCTURING-BIND таков:

(destructuring-bind (parameter*) list
  body-form*
)

Список параметров может включать любые из типов параметров, поддерживаемых в списках параметров макросов, таких как: &optional, &rest и &key.5) Как и в списке параметров макроса, любой параметр может быть заменен на вложенный деструктурирующий список параметров, который разделяет список на составные части, иначе список целиком был бы связан с заменённым параметром. Форма list вычисляется один раз и возвращает список, который затем деструктурируется и соответствующие значения связываются с переменными в списке параметров. Затем по порядку вычисляются все body-form с учётом значений связанных переменных. Вот несколько простых примеров:

(destructuring-bind (x y z) (list 1 2 3)
(list :x x :y y :z z)) ==> (:X 1 :Y 2 :Z 3)
(destructuring-bind (x y z) (list 1 (list 2 20) 3)
(list :x x :y y :z z)) ==> (:X 1 :Y (2 20) :Z 3)
(destructuring-bind (x (y1 y2) z) (list 1 (list 2 20) 3)
(list :x x :y1 y1 :y2 y2 :z z)) ==> (:X 1 :Y1 2 :Y2 20 :Z 3)
(destructuring-bind (x (y1 &optional y2) z) (list 1 (list 2 20) 3)
(list :x x :y1 y1 :y2 y2 :z z)) ==> (:X 1 :Y1 2 :Y2 20 :Z 3)
(destructuring-bind (x (y1 &optional y2) z) (list 1 (list 2) 3)
(list :x x :y1 y1 :y2 y2 :z z)) ==> (:X 1 :Y1 2 :Y2 NIL :Z 3)
(destructuring-bind (&key x y z) (list :x 1 :y 2 :z 3)
(list :x x :y y :z z)) ==> (:X 1 :Y 2 :Z 3)
(destructuring-bind (&key x y z) (list :z 1 :y 2 :x 3)
(list :x x :y y :z z)) ==> (:X 3 :Y 2 :Z 1)

Единственный вид параметра, который вы можете использовать как с DESTRUCTURING-BIND, так и в списках параметров макросов, о котором я не упомянул в Главе 8, это параметр &whole. Если он указан, то располагается первым в списке параметров, и связывается со всей формой списка целиком.6) После параметра &whole, другие параметры могут появляться как обычно, и извлекать определенные части списка, как если бы параметр &whole отсутствовал. Пример использования &whole вместе с DESTRUCTURING-BIND выглядит так:

(destructuring-bind (&whole whole &key x y z) (list :z 1 :y 2 :x 3)
(list :x x :y y :z z :whole whole))
==> (:X 3 :Y 2 :Z 1 :WHOLE (:Z 1 :Y 2 :X 3))

Вы будете использовать параметр &whole в одном из макросов, составляющих часть библиотеки для генерации HTML, которую вы разработаете в Главе 31. Однако мне нужно рассмотреть еще несколько вопросов, прежде чем вы приступите к ней. После двух глав довольно лисповских тем про cons-ячейки, вы можете перейти к более скучным вопросам о том, как работать с файлами и именами файлов.

1)Возможно создать цепь списочных ячеек, где CDR последней ячейки будет не NIL, а неким другим атомом. Такая конструкция будет называться точечным списком (dotted list), потому что последняя списочная ячейка является точечной парой.
2)Казалось бы, семейство NSUBST-функций не только может, но и в действительности модифицирует дерево прямо на месте. Однако имеется один крайний случай: когда переданное "дерево" фактически является атомом, оно не может быть модифицировано по месту, тогда результатом NSUBST будет являться отличный от аргумента объект: (nsubst 'x 'y 'y) X.
3)UNION принимает только один элемент из каждого списка, но если один из двух списков содержит дублирующиеся элементы, результат может также содержать дубликаты.
4)Также возможно напрямую выполнить SETF над значением, возвращаемым SYMBOL-PLIST. Однако это плохая идея, поскольку различный код может добавлять различные свойства к символам списка свойств с различными целями. Если один кусок кода затирает весь список свойств символа, он может помешать работе другого кода, который добавил свои свойства к списку.
5)Списки параметров макроса поддерживают один тип параметра, который не поддерживает DESTRUCTURING-BIND - это &environment. Тем не менее я не обсуждал этот тип параметра в Главе 8, и сейчас вам не стоит об этом беспокоиться.
6)Когда параметр &whole используется в списке параметров макроса, то форма с которой он связан соответствует всей форме макроса, включая имя макроса
Предыдущая Оглавление Следующая
@2009-2013 lisper.ru