Permalink
Switch branches/tags
Nothing to show
Find file
Fetching contributors…
Cannot retrieve contributors at this time
830 lines (688 sloc) 69.4 KB
\chapter{Коллекции}
\label{ch:11}
\thispagestyle{empty}
Как и в большинстве языков программирования, в Common Lisp есть стандартные типы данных,
собирающие несколько значений в один объект. Каждый язык решает проблему коллекций
немного по-разному, но базовые типы коллекций обычно сводятся к типу массивов с целочисленными
индексами и типу таблиц, способных отображать более или менее
произвольные ключи в значения. Первые называются \textit{массивами}, \textit{списками} или \textit{кортежами}, а
вторые~-- \textit{хеш-таблицами}, \textit{ассоциативными массивами}, \textit{картами} и \textit{словарями}.
Конечно, Lisp знаменит своими списками, поэтому, согласно принципу <<Онтогенез повторяет
филогенез>>, большинство учебников по Lisp начинает объяснение коллекций со
списков. Однако такой подход часто приводит читателей к ошибочному выводу, что
список~-- \textit{единственный} тип коллекций в Lisp. Что ещё хуже,
списки Lisp~-- структуры, настолько гибкие, что их можно использовать для многих целей, для
которых в других языках используются массивы и хеш-таблицы. Но было бы ошибкой слишком
сильно сосредоточиваться на списках; хотя они и являются ключевой структурой данных для
представления Lisp-кода в виде Lisp-данных, во многих случаях более уместны другие структуры данных.
Чтобы списки не затмили всё остальное, в этой главе я сосредоточусь на других типах
коллекций Common Lisp: векторах и хеш-таблицах\pclfootnote{Когда вы познакомитесь со всеми
типами данных в Common Lisp, то увидите, что может быть полезно сначала моделировать
структуру данных с помощью списков, а затем, после того как станет ясно, как именно данные
будут использоваться, заменять списки на что-то более эффективное.}.
Однако векторы и списки имеют достаточно много общих признаков, так что Common Lisp
рассматривает их как подтипы более общей абстракции~-- последовательности. Таким образом,
многие функции, описанные в этой главе, можно использовать как для векторов, так и для
списков.
\section{Векторы}
Векторы~-- основной тип коллекций с доступом по целочисленному индексу в Common Lisp, и они
имеют две разновидности. Векторы с фиксированным размером похожи на массивы в языках,
подобных Java: простая надстройка над непрерывной областью памяти, хранящей элементы
вектора\pclfootnote{Векторы называются векторами, а не массивами, в отличие от их аналогов в других
языках программирования, так как Common Lisp поддерживает настоящие многомерные
массивы. Одинаково корректно (хотя и несколько неуклюже) ссылаться на них как на
\textit{одномерные массивы} (\textit{one-dimensional arrays}).}. С другой стороны,
векторы с изменяемым размером более похожи на векторы в Perl или Ruby, списки в Python
или на класс \lstinline{ArrayList} в Java: они скрывают конкретный способ хранения, позволяя
векторам менять размер по мере добавления или удаления элементов.
Вы можете создать вектор фиксированной длины, содержащий конкретные значения, с помощью
функции \lstinline{VECTOR}, которая принимает любое количество аргументов и возвращает
новый вектор фиксированного размера, содержащий переданные значения.
\begin{myverb}
(vector) ==> #()
(vector 1) ==> #(1)
(vector 1 2) ==> #(1 2)
\end{myverb}
Синтаксис \lstinline!#(...)!~-- способ записи векторов, используемый процедурами
записи и чтения Lisp. Этот синтаксис позволяет вам сохранять и загружать векторы,
выводя их на печать с помощью \lstinline{PRINT} и считывая с помощью \lstinline{READ}.
Вы можете использовать синтаксис \lstinline!#(...)! для
записи векторных литералов в вашем коде, но поскольку эффект изменения литералов не определён,
то для создания векторов, которые планируется изменять, вы всегда должны
использовать \lstinline{VECTOR} или более общую функцию \lstinline{MAKE-ARRAY}.
\lstinline{MAKE-ARRAY}~-- более общая функция, чем \lstinline{VECTOR}, поскольку её можно
применять для создания массивов любой размерности, а также для создания векторов
фиксированной и изменяемой длины. Единственным обязательным аргументом
\lstinline{MAKE-ARRAY} является список, содержащий размерности массива. Поскольку
вектор~-- одномерный массив, то список будет содержать только одно число~-- размер
вектора. Для удобства \lstinline{MAKE-ARRAY} может также принимать обычное число вместо
списка из одного элемента. Без указания дополнительных аргументов \lstinline{MAKE-ARRAY}
создаст вектор с неинициализированными элементами, которые будет необходимо
инициализировать перед использованием\pclfootnote{Элементы массива <<должны>> быть заданы
до того, как вы будете осуществлять доступ к ним, поскольку иначе поведение будет
неопределённым; Lisp не обязан останавливать вас при совершении ошибок.}. Для создания
вектора, с присвоением всем элементам определённого значения, вы можете использовать
аргумент \lstinline{:initial-element}. Таким образом, создать вектор из пяти элементов,
равных \lstinline{NIL}, можно так:
\begin{myverb}
(make-array 5 :initial-element nil) ==> #(NIL NIL NIL NIL NIL)
\end{myverb}
\lstinline{MAKE-ARRAY} также используется для создания векторов переменного размера.
Вектор с изменяемым размером несколько сложнее, чем вектор фиксированного размера;
помимо количества доступных ячеек и области памяти, выделенной под хранение элементов,
вектор с изменяемым размером также отслеживает, сколько элементов фактически
хранится в векторе. Это число хранится в \textit{указателе заполнения} (\textit{fill pointer})
вектора, названного так, поскольку это индекс позиции, которая будет заполнена следующей,
когда вы добавите элемент в вектор.
Чтобы создать вектор с указателем заполнения, вы должны передать \lstinline{MAKE-ARRAY}
аргумент \lstinline{:fill-pointer}. Например, следующий вызов \lstinline{MAKE-ARRAY} создаст вектор
с местом для пяти элементов; но он будет выглядеть пустым, поскольку указатель заполнения
равен нулю:
\begin{myverb}
(make-array 5 :fill-pointer 0) ==> #()
\end{myverb}
Чтобы добавить элемент в конец вектора, можно использовать функцию
\lstinline{VECTOR-PUSH}. Она добавляет элемент в позицию, указываемую указателем заполнения, и
затем увеличивает его на единицу, возвращая индекс ячейки, куда был добавлен новый
элемент. Функция \lstinline{VECTOR-POP} возвращает последний добавленный элемент, уменьшая
указатель заполнения на единицу.
\begin{myverb}
(defparameter *x* (make-array 5 :fill-pointer 0))
(vector-push 'a *x*) ==> 0
*x* ==> #(A)
(vector-push 'b *x*) ==> 1
*x* ==> #(A B)
(vector-push 'c *x*) ==> 2
*x* ==> #(A B C)
(vector-pop *x*) ==> C
*x* ==> #(A B)
(vector-pop *x*) ==> B
*x* ==> #(A)
(vector-pop *x*) ==> A
*x* ==> #()
\end{myverb}
Однако даже вектор с указателем заполнения на самом деле не является вектором с изменяемыми
размерами. Вектор \lstinline{*x*} может хранить максимум пять элементов. Для того чтобы
создать вектор с изменяемым размером, вам необходимо передать \lstinline{MAKE-ARRAY} другой
именованный аргумент: \lstinline{:adjustable}.
\begin{myverb}
(make-array 5 :fill-pointer 0 :adjustable t) ==> #()
\end{myverb}
Этот вызов создаст \textit{приспособляемый} (\textit{adjustable}) вектор, размер которого
может изменяться по мере необходимости. Чтобы
добавить элементы в такой вектор, вам нужно использовать функцию
\lstinline{VECTOR-PUSH-EXTEND}, которая работает так же, как и \lstinline{VECTOR-PUSH}, однако
она автоматически увеличит массив, если вы попытаетесь добавить элемент в
уже заполненный вектор~-- вектор, чей указатель заполнения равен размеру выделенной
памяти\footnote{Хотя аргументы \lstinline{:fill-pointer} и \lstinline{:adjustable} часто используются
вместе, но они независимы друг от друга~-- вы можете создать
массив с изменяемым размером без указателя заполнения. Однако вы можете использовать
\lstinline{VECTOR-PUSH} и \lstinline{VECTOR-POP} только с векторами, которые имеют указатель
заполнения, а \lstinline{VECTOR-PUSH-EXTEND}~-- только с векторами, которые имеют переменный
размер и указатель заполнения. Вы также можете использовать функцию \lstinline{ADJUST-ARRAY}
для изменения параметров массивов переменной длины, а не только изменения длины
вектора.}\hspace{\footnotenegspace}.
\section{Подтипы векторов}
Все векторы, с которыми мы уже встречались, были векторами \textit{общего назначения}
(\textit{general}), которые могут хранить объекты любого типа. Однако возможно и
создание \textit{специализированных} (\textit{specialized}) векторов,
которые предназначены для хранения элементов определённого типа. Одной из
причин использовать специализированные векторы является то, что они могут требовать
меньше памяти и обеспечивать более быстрый доступ к своим элементам, по сравнению с
векторами общего назначения. Однако давайте сосредоточимся на некоторых
специализированных векторах, которые сами по себе являются важными типами данных.
С одним из них мы уже встречались: строки~-- это векторы, предназначенные для хранения
знаков. Строки так важны, что для них предусмотрен собственный синтаксис чтения/записи
(двойные кавычки) и набор отдельных функций, которые мы обсуждали в предыдущей главе. Но
поскольку они также являются векторами, то все функции, работающие с векторами и которые мы
будем обсуждать в следующих разделах, могут также использоваться для работы со строками.
Эти функции дополнят библиотеку функций работы со строками новыми функциями для таких
операций, как поиск подстроки в строке, нахождение позиции знака в строке и т. п.
Строки, такие как \lstinline{"foo"}, подобны векторам, записанным с использованием синтаксиса
\lstinline!#()!~-- их размер фиксирован, и они не должны изменяться. Однако вы можете
использовать функцию \lstinline{MAKE-ARRAY} для создания строк с изменяемым размером, просто
добавив ещё один именованный аргумент~-- \lstinline{:element-type}. Этот аргумент принимает
описание \textit{типа} (\textit{type} descriptor). Я не буду тут описывать типы, которые
вы можете использовать; сейчас достаточно знать, что вы можете создать строку, передав символ
\lstinline{CHARACTER} в качестве аргумента \lstinline{:element-type}. Заметьте, что необходимо экранировать
символ, чтобы он не считался именем переменной. Например, чтобы создать пустую строку с
изменяемым размером, вы можете написать вот так:
\begin{myverb}
(make-array 5 :fill-pointer 0 :adjustable t :element-type 'character) ==> ""
\end{myverb}
Битовые векторы (специализированные векторы, чьи элементы могут иметь значение ноль или
один) также отличаются от обычных векторов. Они также имеют специальный синтаксис
чтения/записи, который выглядит вот так \lstinline!#*00001111!, а еще достаточно большой
набор функций (которые я не буду тут описывать) для выполнения битовых операций, таких как
выполнение <<и>> для двух битовых массивов. Для создания такого вектора нужно передать
в качестве \lstinline{:element-type} символ \lstinline{BIT}.
\section{Векторы как последовательности}
Как уже упоминалось ранее, векторы и списки являются подтипами абстрактного типа
\textit{последовательность} (\textit{sequence}). Все функции, которые будут обсуждаться
в следующих разделах, работают с последовательностями; они могут работать не только с векторами
(и специализированным, и общего назначения), но и со списками.
Две самые простые функции для работы с последовательностями~-- \lstinline{LENGTH},
возвращающая длину последовательности, и \lstinline{ELT}, осуществляющая доступ к
отдельным элементам по целочисленному индексу. \lstinline{LENGTH} получает
последовательность в качестве единственного аргумента и возвращает число элементов в этой
последовательности. Для векторов с указателем заполнения это число будет равно значению
указателя. \lstinline{ELT} (сокращение слова \textit{element}) получает два аргумента~--
последовательность и числовой индекс между нулём (включительно) и длиной
последовательности (не включительно)~-- и возвращает соответствующий элемент. \lstinline{ELT} выдаст ошибку,
если индекс находится за границами последовательности. Подобно \lstinline{LENGTH}, \lstinline{ELT}
рассматривает вектор с указателем заполнения как имеющий длину, заданную этим
указателем.
\begin{myverb}
(defparameter *x* (vector 1 2 3))
(length *x*) ==> 3
(elt *x* 0) ==> 1
(elt *x* 1) ==> 2
(elt *x* 2) ==> 3
(elt *x* 3) ==> error
\end{myverb}
\lstinline{ELT} возвращает ячейку, для которой можно выполнить \lstinline{SETF}, так что вы можете
установить значение отдельного элемента с помощью вот такого кода:
\begin{myverb}
(setf (elt *x* 0) 10)
*x* ==> #(10 2 3)
\end{myverb}
\section{Функции для работы с элементами последовательностей}
Хотя в теории все операции над последовательностями могут быть сведены к комбинациям
\lstinline{LENGTH}, \lstinline{ELT} и \lstinline{SETF} на результат \lstinline{ELT}, Common Lisp все равно
предоставляет большую библиотеку функций для работы с последовательностями.
Одна группа функций позволит вам выполнить некоторые операции, такие как нахождение или
удаление определённых элементов, без явного написания циклов. Краткая сводка этих функций
приводится в таб.~\ref{table:11-1}.
\begin{table}[h]
\centering{}
\begin{tabular}{|c|p{50mm}|p{55mm}|}
\hline
Название &\multicolumn{1}{c|}{Обязательные аргументы} &\multicolumn{1}{c|}{Возвращаемое значение} \\
\hline
\code{COUNT} &Объект и последовательность &Число вхождений в последовательности\\
\code{FIND} &Объект и последовательность &Объект или \code{NIL}\\
\code{POSITION} &Объект и последовательность &Индекс ячейки в последовательности или \code{NIL}\\
\code{REMOVE} &Удаляемый объект и последовательность &Последовательность, из которой удалены указанные объекты\\
\code{SUBSTITUTE} &Новый объект, заменяемый объект и последовательность &Последовательность, в которой указанные объекты заменены на новые\\
\hline
\end{tabular}
\caption{Базовые функции для работы с последовательностями}
\label{table:11-1}
\end{table}
Вот несколько простых примеров использования этих функций:
\begin{myverb}
(count 1 #(1 2 1 2 3 1 2 3 4)) ==> 3
(remove 1 #(1 2 1 2 3 1 2 3 4)) ==> #(2 2 3 2 3 4)
(remove 1 '(1 2 1 2 3 1 2 3 4)) ==> (2 2 3 2 3 4)
(remove #\bslash{}a "foobarbaz") ==> "foobrbz"
(substitute 10 1 #(1 2 1 2 3 1 2 3 4)) ==> #(10 2 10 2 3 10 2 3 4)
(substitute 10 1 '(1 2 1 2 3 1 2 3 4)) ==> (10 2 10 2 3 10 2 3 4)
(substitute #\bslash{}x #\bslash{}b "foobarbaz") ==> "fooxarxaz"
(find 1 #(1 2 1 2 3 1 2 3 4)) ==> 1
(find 10 #(1 2 1 2 3 1 2 3 4)) ==> NIL
(position 1 #(1 2 1 2 3 1 2 3 4)) ==> 0
\end{myverb}
Заметьте, что \lstinline{REMOVE} и \lstinline{SUBSTITUTE} всегда возвращают последовательность
того же типа, что и переданный аргумент.
Вы можете изменить поведение этих функций с помощью различных именованных аргументов.
Например, по умолчанию эти функции ищут в последовательности точно такой же объект, что и
переданный в качестве аргумента. Вы можете изменить это поведение двумя способами: во-первых,
вы можете использовать именованный аргумент \lstinline{:test} для указания функции,
которая принимает два аргумента и возвращает логическое значение. Если этот аргумент
указан, то он будет использоваться для сравнения каждого \textit{элемента} с эталонным вместо стандартной
проверки на равенство с помощью \lstinline{EQL}\footnote{Другой именованный параметр,
\lstinline{:test-not}, указывает предикат, который будет использоваться точно так же, как и
параметр \lstinline{:test}, но результат будет изменён на
противоположное значение. Однако этот параметр считается устаревшим, и предпочтительным
является использование функции \lstinline{COMPLEMENT}. \lstinline{COMPLEMENT} получает
аргумент-функцию и возвращает функцию, которая получает то же самое количество
аргументов, что и оригинальная, но возвращает результат, имеющий противоположное
значение результату, возвращаемому оригинальной функцией. Так что вы можете (и должны)
писать вот так:
\begin{myverb}
(count x sequence :test (complement #'some-test))
\end{myverb}
\noindent{}вместо:
\begin{myverb}
(count x sequence :test-not #'some-test)
\end{myverb}
}\hspace{\footnotenegspace}. Во-вторых, используя именованный параметр \lstinline{:key}, вы можете передать функцию одного
аргумента, с помощью которой из каждого элемента последовательности будет извлекаться \textit{ключ},
который затем будет сравниваться с переданным объектом. Однако заметьте, что
функции (например, \lstinline{FIND}), возвращающие элементы последовательности, все равно будут
возвращать элементы, а не ключи, извлечённые из этих элементов.
\begin{myverb}
(count "foo" #("foo" "bar" "baz") :test #'string=) ==> 1
(find 'c #((a 10) (b 20) (c 30) (d 40)) :key #'first) ==> (C 30)
\end{myverb}
Для ограничения действия этих функций в рамках только определённых пределов вы можете
указать граничные индексы, используя именованные аргументы \lstinline{:start} и \lstinline{:end}.
Передача \lstinline{NIL} в качестве значения \lstinline{:end} (или его полное отсутствие)
равносильно указанию длины последовательности\footnote{Заметьте, однако, что для
\lstinline{REMOVE} и \lstinline{SUBSTITUTE} указание \lstinline{:start} и \lstinline{:end} приводит к
ограничению количества аргументов, подпадающих под удаление или замену; элементы до
\lstinline{:start} и после \lstinline{:end} будут переданы без изменений.}\hspace{\footnotenegspace}.
Если указывается не равный \lstinline{NIL} аргумент \lstinline{:from-end}, то элементы
последовательности проверяются в обратном порядке. Простое указание \lstinline{:from-end}
может затронуть результаты \lstinline{FIND} и \lstinline{POSITION}. Например:
\begin{myverb}
(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first) ==> (A 10)
(find 'a #((a 10) (b 20) (a 30) (b 40)) :key #'first :from-end t) ==> (A 30)
\end{myverb}
Также использование \lstinline{:from-end} может влиять на работу \lstinline{REMOVE} и
\lstinline{SUBSTITUTE} при использовании с другим именованным параметром~-- \lstinline{:count},
который применяется для указания количества заменяемых или удаляемых элементов. Если вы
указываете \lstinline{:count} меньший, чем количество совпадающих элементов, то результат будет
зависеть от того, с какого конца последовательности вы начинаете обработку:
\begin{myverb}
(remove #\bslash{}a "foobarbaz" :count 1) ==> "foobrbaz"
(remove #\bslash{}a "foobarbaz" :count 1 :from-end t) ==> "foobarbz"
\end{myverb}
И хотя \lstinline{:from-end} не может изменить результат функции \lstinline{COUNT}, его
использование может влиять на порядок элементов, передаваемых функциям, указанным в
параметрах \lstinline{:test} и \lstinline{:key}, которые, возможно, могут вызвать побочные эффекты.
Например:
\begin{myverb}
CL-USER> (defparameter *v* #((a 10) (b 20) (a 30) (b 40)))
*V*
CL-USER> (defun verbose-first (x) (format t "Looking at ~s~%" x) (first x))
VERBOSE-FIRST
CL-USER> (count 'a *v* :key #'verbose-first)
Looking at (A 10)
Looking at (B 20)
Looking at (A 30)
Looking at (B 40)
2
CL-USER> (count 'a *v* :key #'verbose-first :from-end t)
Looking at (B 40)
Looking at (A 30)
Looking at (B 20)
Looking at (A 10)
2
\end{myverb}
В~таб.~\ref{table:11-2} приведены описания всех стандартных аргументов.
\begin{table}[h]
\centering{}
\begin{tabular}{|c|p{87mm}|>{\centering}p{20mm}|}
\hline
Аргумент &\multicolumn{1}{c|}{Описание} &Значение по умолчанию\\
\hline
\code{:test} &Функция двух аргументов, используемая для сравнения элементов (или их ключей, извлечённых функцией \code{:key}) с указанным объектом &\code{EQL}\\
\code{:key} &Функция одного аргумента, используемая для извлечения ключа из элемента последовательности. \code{NIL} указывает на использование самого элемента &\code{NIL}\\
\code{:start} &Начальный индекс (включительно) обрабатываемой последовательности &\code{0}\\
\code{:end} &Конечный индекс (не включительно) обрабатываемой последовательности. \code{NIL} указывает на конец последовательности &\code{NIL}\\
\code{:from-end} &Если имеет истинное значение, то последовательность будет обрабатываться в обратном порядке, от конца к началу &\code{NIL}\\
\code{:count} &Число, указывающее количество удаляемых или заменяемых элементов, или \code{NIL} для всех элементов (только для \code{REMOVE} и \code{SUBSTITUTE}) &\code{NIL}\\
\hline
\end{tabular}
\caption{Стандартные именованные аргументы функций работы с последовательностями}
\label{table:11-2}
\end{table}
\section{Аналогичные функции высшего порядка}
Для каждой из функций, которая была описана выше, Common Lisp также предоставляет два
набора \textit{функций высшего порядка} (\textit{higher-order functions}), которые вместо
аргумента, используемого для сравнения,
получают функцию, которая вызывается для каждого элемента последовательности. Первый
набор функций имеет те же имена, что и функции из базового набора, но с добавлением
суффикса \lstinline{-IF}. Эти функции подсчитывают, ищут, удаляют и заменяют элементы, для
которых аргумент-функция возвращает истинное значение. Другой набор функций отличается
тем, что использует суффикс \lstinline{-IF-NOT}, и выполняет те же операции, но для элементов,
для которых функция \textit{не} возвращает истинного значения.
\begin{myverb}
(count-if #'evenp #(1 2 3 4 5)) ==> 2
(count-if-not #'evenp #(1 2 3 4 5)) ==> 3
(position-if #'digit-char-p "abcd0001") ==> 4
(remove-if-not #'(lambda (x) (char= (elt x 0) #\bslash{}f))
#("foo" "bar" "baz" "foom")) ==> #("foo" "foom")
\end{myverb}
В~соответствии со стандартом языка функции с суффиксом \lstinline{-IF-NOT} являются
устаревшими. Однако это требование само считается неразумным. Если стандарт будет
пересматриваться, то, скорее, будет удалено это требование, а не функции с суффиксом
\lstinline{-IF-NOT}. Для некоторых вещей \lstinline{REMOVE-IF-NOT} может использоваться чаще, чем
\lstinline{REMOVE-IF}. За исключением своего отрицательно звучащего имени, в действительности
\lstinline{REMOVE-IF-NOT} является положительной функцией~-- она возвращает элементы, которые
соответствуют предикату\footnote{Эта функция обеспечивает ту же функциональность, что и
\lstinline{grep} в Perl и \lstinline{filter} в Python.}\hspace{\footnotenegspace}.
Оба варианта функций принимают те же именованные аргументы, что и базовые функции, за
исключением аргумента \lstinline{:test}, который не нужен, поскольку главный аргумент сам
является функцией\footnote{Отличием предиката, передаваемого аргументу \lstinline{:test}, от
аргумента-функции, передаваемого в функции с суффиксами \lstinline{-IF} и \lstinline{-IF-NOT},
является то, что предикат параметра \lstinline{:test} имеет два аргумента и используется для
сравнения элементов последовательности с конкретным объектом, в то время как предикаты
для функций с суффиксами \lstinline{-IF} и \lstinline{-IF-NOT} имеют один аргумент и используются
для проверки только элементов последовательности. Если бы базовые варианты не
существовали, то вы могли бы реализовать их с помощью функций с суффиксом \lstinline{-IF}
путём указания объекта в функции-предикате.
\begin{myverb}
(count char string) ===
(count-if #'(lambda (c) (eql char c)) string)
(count char string :test #'CHAR-EQUAL) ===
(count-if #'(lambda (c) (char-equal char c)) string)
\end{myverb}
}\hspace{\footnotenegspace}. При указании аргумента \lstinline{:key} функции передаётся значение, извлечённое функцией
аргумента \lstinline{:key}, а не сам элемент.
\begin{myverb}
(count-if #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first) ==> 2
(count-if-not #'evenp #((1 a) (2 b) (3 c) (4 d) (5 e)) :key #'first) ==> 3
(remove-if-not #'alpha-char-p
#("foo" "bar" "1baz") :key #'(lambda (x) (elt x 0))) ==> #("foo" "bar")
\end{myverb}
Семейство функций \lstinline{REMOVE} также имеет четвёртый вариант, функцию
\lstinline{REMOVE-DUPLICATES}, которая имеет один аргумент~-- последовательность, из которой
удаляются все, кроме одного экземпляра, каждого дублированного элемента. Она может
принимать те же самые именованные аргументы, что и \lstinline{REMOVE}, за исключением
\lstinline{:count}, поскольку она всегда удаляет все дубликаты.
\begin{myverb}
(remove-duplicates #(1 2 1 2 3 1 2 3 4)) ==> #(1 2 3 4)
\end{myverb}
\section{Работа с последовательностью целиком}
Несколько функций оперируют над последовательностями целиком. Обычно
они проще, чем функции, которые я описывал ранее. Например,
\lstinline{COPY-SEQ} и \lstinline{REVERSE} получают по одному аргументу~-- последовательности~-- и
возвращают новую последовательность того же самого типа. Последовательность, возвращённая
\lstinline{COPY-SEQ}, содержит те же самые элементы, что и исходная,
а последовательность, возвращённая \lstinline{REVERSE}, содержит те же
самые элементы, но в обратном порядке. Заметьте, что ни одна из этих функций не копирует
сами элементы, заново создаётся только возвращаемая последовательность.
Функция \lstinline{CONCATENATE} создаёт новую последовательность, содержащую объединение произвольного
числа последовательностей. Однако, в отличие от \lstinline{REVERSE} и \lstinline{COPY-SEQ}, которые
просто возвращают последовательность того же типа, что и переданный аргумент, функции
\lstinline{CONCATENATE} должно быть явно указано, какой тип последовательности необходимо
создать в том случае, если её аргументы имеют разные типы. Первым аргументом функции
является описание типа, подобного параметру \lstinline{:element-type} функции \lstinline{MAKE-ARRAY}.
В~этом случае, вероятнее всего, вы будете использовать следующие символы для указания типа:
\lstinline{VECTOR}, \lstinline{LIST} или \lstinline{STRING}\footnote{Если вы указываете функции
\lstinline{CONCATENATE}, что она должна вернуть специализированный вектор, например строку,
то все элементы аргументов-последовательностей должны иметь тот же тип, что и элементы
этого вектора.}\hspace{\footnotenegspace}. Например:
\begin{myverb}
(concatenate 'vector #(1 2 3) '(4 5 6)) ==> #(1 2 3 4 5 6)
(concatenate 'list #(1 2 3) '(4 5 6)) ==> (1 2 3 4 5 6)
(concatenate 'string "abc" '(#\bslash{}d #\bslash{}e #\bslash{}f)) ==> "abcdef"
\end{myverb}
\section{Сортировка и слияние}
Функции \lstinline{SORT} и \lstinline{STABLE-SORT} обеспечивают два метода сортировки
последовательности. Они обе получают последовательность и функцию двух аргументов и
возвращают отсортированную последовательность.
\begin{myverb}
(sort (vector "foo" "bar" "baz") #'string<) ==> #("bar" "baz" "foo")
\end{myverb}
Разница между этими функциями заключается в том, что \lstinline{STABLE-SORT} гарантирует, что
она не будет изменять порядок элементов, которые считаются эквивалентными, в то время как
\lstinline{SORT} гарантирует только, что результат будет отсортирован, так что некоторые
эквивалентные элементы могут быть поменяны местами.
Обе эти функции представляют собой примеры так называемых \textit{разрушающих} (\textit{destructive}) функций. Разрушающим
функциям разрешено (обычно в целях эффективности) модифицировать переданные аргументы тем
или иным образом. Отсюда следуют две вещи: во-первых, вы обязательно должны что-то сделать с
возвращаемым значением этих функций (например, присвоить его переменной или передать его
другой функции), и во-вторых, если вы ещё планируете работать с передаваемым в
разрушающую функцию аргументом, вы должны передавать его копию, а не сам объект.
Я расскажу о разрушающих функциях более подробно в следующей главе.
Обычно после того, как последовательность отсортирована, её неотсортированная версия
больше не нужна, так что имеет смысл
позволить \lstinline{SORT} и \lstinline{STABLE-SORT} разрушать последовательность в процессе её
сортировки. Но это значит, что вы должны не забывать писать так\pclfootnote{Когда
передаваемая последовательность является вектором, <<разрушение>> означает изменение
элементов на месте, так что вы можете обойтись без сохранения возвращаемого значения.
Однако хорошим стилем будет обязательное использование возвращаемого значения,
поскольку функции сортировки могут изменять списки произвольным образом.}:
\begin{myverb}
(setf my-sequence (sort my-sequence #'string<))
\end{myverb}
\noindent{}вместо:
\begin{myverb}
(sort my-sequence #'string<)
\end{myverb}
Обе эти функции принимают именованный аргумент \lstinline{:key}, который, так же как и аргумент
\lstinline{:key} в других функциях работы с последовательностями, должен быть функцией и
использоваться для извлечения значений, которые будут передаваться предикату сортировки
вместо оригинальных элементов. Извлечённые значения используются только для определения
порядка элементов; возвращённая последовательность будет содержать сами элементы, а не
извлечённые значения.
Функция \lstinline{MERGE} принимает две последовательности и функцию-предикат и возвращает
последовательность, полученную путём слияния двух последовательностей в соответствии с
предикатом. Она связана с функциями сортировки: если каждая последовательность
уже была отсортирована с использованием того же самого предиката, то и полученная
последовательность также будет отсортирована. Так же как и функции сортировки,
\lstinline{MERGE} принимает аргумент \lstinline{:key}. Подобно \lstinline{CONCATENATE}, и по тем же
причинам, первым аргументом \lstinline{MERGE} должно быть описание типа последовательности,
которая будет получена в результате работы.
\begin{myverb}
(merge 'vector #(1 3 5) #(2 4 6) #'<) ==> #(1 2 3 4 5 6)
(merge 'list #(1 3 5) #(2 4 6) #'<) ==> (1 2 3 4 5 6)
\end{myverb}
\section{Работа с частями последовательностей}
Еще один набор функций позволяет работать с частями последовательностей. Основная из
таких функций~-- \lstinline{SUBSEQ}, которая выделяет часть последовательности,
начиная с определённого индекса и заканчивая другим индексом или концом
последовательности. Например:
\begin{myverb}
(subseq "foobarbaz" 3) ==> "barbaz"
(subseq "foobarbaz" 3 6) ==> "bar"
\end{myverb}
Для результата \lstinline{SUBSEQ} также можно выполнить \lstinline{SETF}, но таким образом нельзя увеличить
или уменьшить последовательность; если часть последовательности и новое значение имеют
разные длины, то более короткое из них определяет то, как много знаков будет изменено.
\begin{myverb}
(defparameter *x* (copy-seq "foobarbaz"))
(setf (subseq *x* 3 6) "xxx") ; subsequence and new value are same length
*x* ==> "fooxxxbaz"
(setf (subseq *x* 3 6) "abcd") ; new value too long, extra character ignored.
*x* ==> "fooabcbaz"
(setf (subseq *x* 3 6) "xx") ; new value too short, only two characters changed
*x* ==> "fooxxcbaz"
\end{myverb}
Вы можете использовать функцию \lstinline{FILL} для заполнения нескольких значений
последовательности одним и тем же значением. Обязательные аргументы~--
последовательность и значение, которым нужно заполнить элементы. По умолчанию
заполняется вся последовательность; вы можете использовать именованные аргументы
\lstinline{:start} и \lstinline{:end} для ограничения границ заполнения.
Если вам нужно найти одну последовательность внутри другой, то вы можете использовать
функцию \lstinline{SEARCH}, которая работает так же, как и функция \lstinline{POSITION}, но первым
аргументом является последовательность, а не единичное значение.
\begin{myverb}
(position #\bslash{}b "foobarbaz") ==> 3
(search "bar" "foobarbaz") ==> 3
\end{myverb}
Для того чтобы, напротив, найти позицию, в которой две последовательности с общим
префиксом начинают различаться, вы можете использовать функцию \lstinline{MISMATCH}. Она
принимает две последовательности и возвращает индекс первой пары неравных элементов.
\begin{myverb}
(mismatch "foobarbaz" "foom") ==> 3
\end{myverb}
Эта функция возвращает \lstinline{NIL}, если строки совпадают. \lstinline{MISMATCH} может также
принимать стандартные именованные аргументы: аргумент \lstinline{:key} для указания функции
извлечения сравниваемых значений; аргумент \lstinline{:test} для указания функции сравнения и
аргументы \lstinline{:start1}, \lstinline{:end1}, \lstinline{:start2} и :\lstinline{end2} для указания границ
действия внутри последовательностей. Также указание \lstinline{:from-end} со значением
\lstinline{T} приводит к тому, что поиск осуществляется в обратном порядке, заставляя
\lstinline{MISMATCH} вернуть индекс позиции в первой последовательности, где начинается общий
суффикс последовательностей.
\begin{myverb}
(mismatch "foobar" "bar" :from-end t) ==> 3
\end{myverb}
\section{Предикаты для последовательностей}
Также существуют полезные функции \lstinline{EVERY}, \lstinline{SOME}, \lstinline{NOTANY} и
\lstinline{NOTEVERY}, которые пробегают по элементам последовательности, проверяя заданный
предикат. Первым аргументом всех этих функций является предикат, а остальные аргументы~--
последовательности. Предикат должен получать столько аргументов, сколько
последовательностей будет передано функциям. Элементы последовательностей передаются
предикату (по одному элементу за раз), пока не закончатся элементы или не будет выполнено
условие завершения: \lstinline{EVERY} завершается, возвращая ложное значение, сразу, как только это
значение будет возвращено предикатом. Если предикат всегда возвращает истинное значение,
то функция также вернёт истинное значение. \lstinline{SOME} возвращает первое не-\lstinline{NIL}
значение, возвращённое предикатом, или возвращает ложное значение, если предикат никогда
не вернул истинного значения. \lstinline{NOTANY} возвращает ложное значение, если предикат
возвращает истинное значение, или истинное, если этого не произошло. А \lstinline{NOTEVERY}
возвращает истинное значение сразу, как только предикат возвращает ложное значение, или
ложное, если предикат всегда возвращал истинное. Вот примеры проверок для одной
последовательности:
\begin{myverb}
(every #'evenp #(1 2 3 4 5)) ==> NIL
(some #'evenp #(1 2 3 4 5)) ==> T
(notany #'evenp #(1 2 3 4 5)) ==> NIL
(notevery #'evenp #(1 2 3 4 5)) ==> T
\end{myverb}
А эти вызовы выполняют попарное сравнение последовательностей:
\begin{myverb}
(every #'> #(1 2 3 4) #(5 4 3 2)) ==> NIL
(some #'> #(1 2 3 4) #(5 4 3 2)) ==> T
(notany #'> #(1 2 3 4) #(5 4 3 2)) ==> NIL
(notevery #'> #(1 2 3 4) #(5 4 3 2)) ==> T
\end{myverb}
\vfill{}
\section{Функции отображения последовательностей}
В~заключение обзора функций работы с последовательностями рассмотрим
функции отображения (mapping). Функция \lstinline{MAP}, подобно функциям-предикатам для
последовательностей, получает функцию нескольких аргументов и несколько
последовательностей. Но вместо логического значения \lstinline{MAP} возвращает новую
последовательность, содержащую результаты применения функции к элементам
последовательности. Так же как для \lstinline{CONCATENATE} и \lstinline{MERGE}, \lstinline{MAP}
необходимо сообщить тип создаваемой последовательности.
\begin{myverb}
(map 'vector #'* #(1 2 3 4 5) #(10 9 8 7 6)) ==> #(10 18 24 28 30)
\end{myverb}
Функция \lstinline{MAP-INTO} похожа на \lstinline{MAP}, за исключением того, что вместо создания
новой последовательности заданного типа она помещает результаты в последовательность,
заданную в качестве первого аргумента. Эта последовательность может иметь такой же тип,
как одна из последовательностей, предоставляющих данные для функции. Например, для
суммирования нескольких векторов (\lstinline{a}, \lstinline{b} и \lstinline{c}) в один вы должны
написать:
\begin{myverb}
(map-into a #'+ a b c)
\end{myverb}
Если последовательности имеют разную длину, то \lstinline{MAP-INTO} изменяет столько элементов,
сколько присутствует в самой короткой последовательности, включая ту, в которую помещаются
результаты. Однако если последовательность будет отображаться в вектор с указателем
заполнения, то число изменяемых элементов будет определяться не указателем заполнения, а
размером вектора. После вызова \lstinline{MAP-INTO} указатель заполнения будет установлен
равным количеству изменённых элементов. Однако \lstinline{MAP-INTO} не будет изменять размера
векторов, которые допускают такую операцию.
Напоследок рассмотрим функцию \lstinline{REDUCE},
которая реализует другой вид отображения: она выполняет отображение для
одной последовательности, применяя функцию двух аргументов сначала к первым двум элементам
последовательности, а после первого вызова последовательно применяя её к полученному
результату и следующим элементам. Таким образом, следующее выражение сложит числа от
единицы до десяти:
\begin{myverb}
(reduce #'+ #(1 2 3 4 5 6 7 8 9 10)) ==> 55
\end{myverb}
\lstinline{REDUCE}~-- удивительно полезная функция: если вам нужно создать из
последовательности одно значение, вполне вероятно, что вы сможете сделать это с помощью
\lstinline{REDUCE}, и такая запись зачастую оказывается весьма лаконичной.
Например, для нахождения максимального значения в последовательности вы можете просто
написать \lstinline!(reduce #'max numbers)!. \lstinline{REDUCE} также принимает полный набор
стандартных именованных аргументов (\lstinline{:key}, \lstinline{:from-end}, \lstinline{:start} и
\lstinline{:end}), а также один, уникальный для \lstinline{REDUCE} (\lstinline{:initial-value}). Этот
аргумент указывает значение, которое будет логически помещено до первого элемента
последовательности (или после последнего, если вы также зададите \lstinline{:from-end} истинное
значение).
\section{Хеш-таблицы}
Еще одна коллекция общего назначения в Common Lisp~-- хеш-таблица. В~отличие от векторов,
позволяющих осуществлять доступ по целочисленному индексу,
хеш-таблицы позволяют использовать в качестве индексов (ключей) любые объекты.
Добавляя объекты в хеш-таблицу, вы сохраняете их с определённым ключом. Позднее вы
можете использовать тот же самый ключ для доступа к значению. Или вы можете связать
с тем же самым ключом новое значение~-- каждый ключ отображается в единственное значение.
Без указания дополнительных аргументов \lstinline{MAKE-HASH-TABLE} создаёт хеш-таблицу, которая
сравнивает ключи с использованием функции \lstinline{EQL}. Это нормально до тех пор, пока вы
не захотите использовать в качестве ключей строки, поскольку две строки с одинаковым
содержимым не обязательно равны в терминах \lstinline{EQL}. В~таком случае следует
использовать для сравнения функцию \lstinline{EQUAL}: это можно сделать, передав функции
\lstinline{MAKE-HASH-TABLE} символ \lstinline{EQUAL} в качестве именованного аргумента \lstinline{:test}.
Кроме того, для аргумента \lstinline{:test} можно использовать ещё два символа: \lstinline{EQ} и
\lstinline{EQUALP}. Конечно, эти символы являются именами стандартных функций сравнения
объектов, которые я обсуждал в главе~\ref{ch:04}. Однако, в отличие от аргумента \lstinline{:test},
передаваемого функциям работы с последовательностями, аргумент \lstinline{:test} функции
\lstinline{MAKE-HASH-TABLE} не может использовать произвольную функцию~-- допустимы только
значения \lstinline{EQ}, \lstinline{EQL}, \lstinline{EQUAL} и \lstinline{EQUALP}. Это происходит потому, что
на самом деле хеш-таблице нужны две функции~-- функция сравнения и функция
\textit{хеширования}, которая получает из ключа числовой хеш-код способом, совместимым с
функцией сравнения. Хотя стандарт языка предоставляет
только хеш-таблицы, использующие стандартные функции сравнения, большинство
реализаций позволяет тем или иным образом создавать более тонко настраиваемые
хеш-таблицы.
Функция \lstinline{GETHASH} обеспечивает доступ к элементам хеш-таблиц. Она принимает два
аргумента: ключ и хеш-таблицу~-- и возвращает значение, если оно найдено, или \lstinline{NIL} в
противном случае\footnote{По историческим причинам порядок аргументов \lstinline{GETHASH}
отличается от порядка аргументов функции \lstinline{ELT}~-- \lstinline{ELT} получает коллекцию в
качестве первого аргумента, а индекс~-- в качестве второго; а \lstinline{GETHASH} наоборот:
ключ~-- первым, а коллекцию~-- вторым.}\hspace{\footnotenegspace}. Например:
\begin{myverb}
(defparameter *h* (make-hash-table))
(gethash 'foo *h*) ==> NIL
(setf (gethash 'foo *h*) 'quux)
(gethash 'foo *h*) ==> QUUX
\end{myverb}
Поскольку \lstinline{GETHASH} возвращает \lstinline{NIL}, если ключ не присутствует в таблице, то нет
никакого способа отличить ключ, отсутствующий в таблице, от ключа, по которому хранится
значение \lstinline{NIL}. Функция \lstinline{GETHASH} решает эту проблему за счёт использования
способа, который мы ещё не обсуждали,~-- возврата нескольких значений. В~действительности
\lstinline{GETHASH} возвращает два значения: главное значение~-- значение для указанного ключа
или \lstinline{NIL}; дополнительное значение имеет логический тип и указывает, присутствует ли
значение в хеш-таблице. Из-за способа реализации возврата множественных значений
дополнительные значения просто отбрасываются, если только пользователь не обрабатывает эту
ситуацию специальным образом, используя средства, которые <<видят>> множественные значения.
Я буду подробно обсуждать возврат множественных значений в главе~\ref{ch:20}, но сейчас я
дам вам лишь общее представление о том, как использовать макрос \lstinline{MULTIPLE-VALUE-BIND}
для получения дополнительных значений, которые возвращает \lstinline{GETHASH}. Макрос
\lstinline{MULTIPLE-VALUE-BIND} создаёт привязки переменных, как это делает \lstinline{LET},
заполняя их множеством значений, возвращённых вызываемой функцией.
Следующие примеры показывают, как вы можете использовать \lstinline{MULTIPLE-VALUE-BIND};
связываемые переменные содержат значение и признак его наличия в таблице:
\begin{myverb}
(defun show-value (key hash-table)
(multiple-value-bind (value present) (gethash key hash-table)
(if present
(format nil "Значение ~a присутствует в таблице." value)
(format nil "Значение равно ~a, поскольку ключ не найден." value))))
(setf (gethash 'bar *h*) nil) ; создаёт ключ со значением NIL
(show-value 'foo *h*) ==> "Значение QUUX присутствует в таблице."
(show-value 'bar *h*) ==> "Значение NIL присутствует в таблице."
(show-value 'baz *h*) ==> "Значение равно NIL , поскольку ключ не найден."
\end{myverb}
Поскольку установка значения в \lstinline{NIL} оставляет ключ в таблице, вам понадобится другая
функция для полного удаления пары ключ/значение. Функция \lstinline{REMHASH} получает такие же
аргументы, как и \lstinline{GETHASH}, и удаляет указанную запись. Вы также можете полностью
очистить хеш-таблицу с помощью функции \lstinline{CLRHASH}.
\section{Функции для работы с записями в хеш-таблицах}
Common Lisp предоставляет разные способы для работы с записями в хеш-таблицах. Простейшим
из них является использование функции \lstinline{MAPHASH}. Так же как и функция \lstinline{MAP},
функция \lstinline{MAPHASH} принимает в качестве аргументов функцию двух аргументов и
хеш-таблицу и выполняет указанную функцию для каждой пары ключ/значение. Например, для
распечатки всех пар ключ/значение вы можете использовать такой вызов \lstinline{MAPHASH}:
\begin{myverb}
(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)
\end{myverb}
Последствия добавления или удаления записей в хеш-таблице во время прохода по её записям
стандартом не указываются (и скорее всего, окажутся печальными), за исключением двух
случаев: вы можете использовать \lstinline{SETF} вместе с \lstinline{GETHASH} для изменения значения
текущей записи, и вы можете использовать \lstinline{REMHASH} для удаления текущей записи.
Например, для удаления всех записей, чьё значение меньше, чем десять, вы можете записать
вот так:
\begin{myverb}
(maphash #'(lambda (k v) (when (< v 10) (remhash k *h*))) *h*)
\end{myverb}
Еще один способ итерации по элементам хеш-таблицы~-- использование макроса
\lstinline{LOOP}, который будет описан в главе~\ref{ch:22}\footnote{Использование \lstinline{LOOP} для
работы с хеш-таблицами обычно основывается на использовании более примитивной формы,
\lstinline{WITH-HASH-TABLE-ITERATOR}, о которой вам не нужно беспокоиться; она была добавлена
в язык специально для поддержки реализации таких вещей, как \lstinline{LOOP}, и практически не
нужна до тех пор, пока вы не соберётесь реализовать совершенно новый способ итерации по
элементам хеш-таблиц.}\hspace{\footnotenegspace}. С использованием \lstinline{LOOP} код, реализующий то же, что и первый
пример с \lstinline{MAPHASH}, будет выглядеть вот так:
\begin{myverb}
(loop for k being the hash-keys in *h* using (hash-value v)
do (format t "~a => ~a~%" k v))
\end{myverb}
Я мог бы рассказать еще очень многое о коллекциях, не являющихся списками, в Common
Lisp. Например, я совсем не рассказал про многомерные массивы или про библиотеку функций
для работы с битовыми массивами. Однако того, что я рассказал в этой главе, должно быть
достаточно для основных применений. Теперь пора взглянуть на
структуру данных, давшую имя языку Lisp,~-- списки.
%%% Local Variables:
%%% mode: latex
%%% TeX-master: "pcl-ru"
%%% TeX-open-quote: "<<"
%%% TeX-close-quote: ">>"
%%% End: