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

11. Коллекции

Как и у большинства языков программирования, у Common Lisp есть стандартные типы данных, которые собирают множество значений в один объект. Каждый язык решает проблему коллекций немного по-разному, но базовые типы коллекций обычно сводятся к массивам с целочисленными индексами и таблицам, которые могут использоваться для отображения более или менее произвольных ключей в значения. Первые называются массивами, списками или кортежами, а вторые – хэш-таблицами, ассоциативными массивами, картами и словарями.

Конечно, Lisp знаменит своими списками, поэтому, согласно принципу "Онтогенез повторяет филогенез", большинство учебников по Lisp начинают объяснение коллекций со списков. Однако, такой подход часто приводит читателей к ошибочному выводу о том, что единственным типом коллекций в Lisp является список. Ухудшает положение еще и то, что списки Lisp – структуры настолько гибкие, что их возможно использовать для тех вещей, для которых в других языках используются массивы и хэш-таблицы. Но было бы ошибкой слишком сильно сосредотачиваться на списках; хотя списки и являются ключевой структурой данных для представления кода на Lisp в виде данных Lisp, во многих случаях другие структуры данных будут более подходящими.

Чтобы списки не затмили всё остальное, в этой главе я сосредоточусь на других типах коллекций Common Lisp: векторах и хэш-таблицах.1) Однако векторы и списки имеют достаточно много общих признаков, так что Common Lisp рассматривает их как подтипы более общей абстракции – последовательности. Таким образом, многие функции, описанные в этой главе, можно использовать как для векторов, так и для списков.

Векторы

Векторы Common Lisp являются базовой коллекцией с доступом по целочисленному индексу, и имеют две разновидности. Векторы с фиксированным размером похожи на массивы в языках, подобных Java: простая надстройка над областью памяти, которая хранит элементы вектора.2) С другой стороны, векторы с изменяемым размером, более похожи на векторы в Perl или Ruby, списки в Python, или на класс ArrayList в Java: они прячут детали реализации хранилища данных, позволяя векторам менять размер по мере добавления или удаления элементов.

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

(vector)     ==> #()
(vector 1) ==> #(1)
(vector 1 2) ==> #(1 2)

Синтаксис #(...) является способом записи векторов, используемый процедурами записи и чтения Lisp. Это позволяет вам сохранять и восстанавливать векторы путем их вывода на печать и последующего считывания. Вы можете использовать #(...) для записи векторов в вашем коде, но поскольку эффект изменения таких объектов не определен, то вы всегда должны использовать VECTOR, или более общую функцию MAKE-ARRAY для создания векторов, которые вы планируете изменять.

MAKE-ARRAY является более общей функцией, чем VECTOR, поскольку вы можете использовать ее как для создания массивов любой размерности, так и для создания векторов фиксированной и изменяемой длины. Единственным обязательным аргументом MAKE-ARRAY является список, содержащий размерности массива. Поскольку вектор – одномерный массив, то список будет содержать только одно число – размер вектора. Для удобства, MAKE-ARRAY может также принимать простое число вместо списка из одного элемента. Без предоставления дополнительных аргументов, MAKE-ARRAY создаст вектор с неинициализированными элементами, которые должны быть заданы до осуществления доступа к ним.3) Для создания вектора, с присвоением всем элементам определенного значения, вы можете использовать аргумент :initial-element. Таким образом, чтобы создать вектор из пяти элементов, которые все равны NIL, вы должны написать следующее:

(make-array 5 :initial-element nil) ==> #(NIL NIL NIL NIL NIL)

MAKE-ARRAY может также использоваться для создания векторов переменного размера. Вектор с изменяемым размером, является более сложным, чем вектор фиксированного размера; в добавление к отслеживанию памяти, используемой для хранения элементов и количества доступных ячеек, вектор с изменяемым размером также отслеживает число элементов, сохраненных в векторе. Это число хранится в указателе заполнения вектора (vector's fill pointer), так названного, поскольку это индекс следующей позиции, которая будет заполнена, когда вы добавите элемент в вектор.

Чтобы создать вектор с указателем заполнения, вы должны передать MAKE-ARRAY аргумент :fill-pointer. Например, следующий вызов MAKE-ARRAY создаст вектор с местом для пяти элементов; но он будет выглядеть пустым, поскольку указатель заполнения равен нулю:

(make-array 5 :fill-pointer 0) ==> #()

Для того, чтобы добавить элемент в конец вектора, вы можете использовать функцию VECTOR-PUSH. Она добавляет элемент в точку, указываемую указателем заполнения, и затем увеличивает его на единицу, возвращая индекс ячейки, куда был добавлен новый элемент. Функция VECTOR-POP возвращает последний добавленный элемент, уменьшая указатель заполнения на единицу.

(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* ==> #()

Однако, даже вектор с указателем заполнения, не является настоящим вектором с изменяемыми размерами. Вектор *x* может хранить максимум пять элементов. Для того, чтобы создать вектор с изменяемым размером, вам необходимо передать MAKE-ARRAY другой именованный аргумент: :adjustable.

(make-array 5 :fill-pointer 0 :adjustable t) ==> #()

Этот вызов создаст вектор, размер которого может изменяться по мере необходимости. Чтобы добавить элементы в такой вектор, вам нужно использовать функцию VECTOR-PUSH-EXTEND, которая работает также как и VECTOR-PUSH, за тем исключением, что она автоматически увеличит массив, если вы попытаетесь добавить элемент в уже заполненный вектор – вектор, чей указатель заполнения равен размеру выделенной памяти.4)

Подтипы векторов

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

С одним из них мы уже встречались: строки – это векторы, предназначенные для хранения знаков. Строки достаточно важны, чтобы они имели собственный синтаксис чтения/записи (двойные кавычки) и набор отдельных функций, которые мы обсуждали в предыдущей главе. Но, поскольку они также являются векторами, все функции работающие с векторами и которые мы будем обсуждать в следующих разделах, могут также использоваться для работы со строками. Эти функции дополнят библиотеку функций работы со строками новыми функциями для таких вещей, как поиск подстроки в строке, нахождение позиции знака в строке и т.п.

Строки, такие как "foo", подобны векторам, записанным с использованием синтаксиса #() – их размер фиксирован, и они не должны изменяться. Однако вы можете использовать функцию MAKE-ARRAY для создания строк с изменяемым размером, просто добавляя еще один именованный аргумент – :element-type. Этот аргумент принимает описание типа. Я не буду тут описывать типы, которые вы можете использовать; сейчас достаточно знать, что вы можете создать строку, путем передачи символа CHARACTER в качестве аргумента :element-type. Заметьте, что вам необходимо экранировать символ, чтобы он не считался именем переменной. Например, чтобы создать пустую строку, с изменяемым размером, вы можете написать вот так:

(make-array 5 :fill-pointer 0 :adjustable t :element-type 'character)  ""

Битовые векторы (специализированные векторы, чьи элементы могут иметь значение ноль или один) также отличаются от обычных векторов. Они также имеют специальный синтаксис чтения/записи, который выглядит вот так #*00001111, а также, достаточно большой набор функций (которые я не буду тут описывать) для выполнения битовых операций, таких как выполнение "и" для двух битовых массивов. Для создания такого вектора, вам нужно передать :element-type символ BIT.

Векторы как последовательности

Как уже упоминалось ранее, векторы и списки являются подтипами абстрактного типа "последовательность". Все функции, которые будут обсуждаться в следующих разделах, работают с последовательностями; в добавление к тому, что они применимы к векторам (и специализированным, и общего назначения), они также могут использоваться и со списками.

Двумя простейшими функциями для работы с последовательностями являются LENGTH, которая возвращает длину последовательности, и ELT, которая осуществляет доступ к отдельным элементам, используя целочисленный индекс. LENGTH получает последовательность в качестве единственного аргумента и возвращает число элементов в этой последовательности. Для векторов с указателем заполнения, это число будет равно значению указателя. ELT (сокращение слова элемент), получает два аргумента – последовательность и числовой индекс между нулем (включительно) и длиной последовательности (n-1) и возвращает соответствующий элемент. ELT выдаст ошибку, если индекс находится за границами последовательности. Подобно LENGTH, ELT рассматривает вектор с указателем заполнения, как имеющий длину, указанную этим указателем.

(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

ELT возвращает ячейку, для которой можно выполнить SETF, так что вы можете установить значение отдельного элемента с помощью вот такого кода:

(setf (elt *x* 0) 10)
*x* ==> #(10 2 3)

Функции для работы с элементами последовательностей

Хотя в теории, все операции над последовательностями могут быть сведены к комбинациям LENGTH, ELT, и SETF на результат ELT, но Common Lisp все равно предоставляет большую библиотеку функций для работы с последовательностями.

Одна группа функций позволит вам выполнить некоторые операции, такие как нахождение или удаление определенных элементов, без явного написания циклов. Краткая сводка этих функций приводится в таблице 11-1.

Table 11-1. Базовые функции для работы с последовательностями

Название Обязательные аргументы Возвращаемое значение
COUNT Объект и последовательность Число вхождений в последовательности
FIND Объект и последовательность Объект или NIL
POSITION Объект и последовательность Индекс ячейки в последовательности или NIL
REMOVE Удаляемый объект и последовательность Последовательность, из которой удалены указанные объекты
SUBSTITUTE Новый объект, заменяемый объект и последовательность Последовательность, в которой указанные объекты заменены на новые

Вот несколько простых примеров использования этих функций:

(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 #\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 #\x #\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

Заметьте, что REMOVE и SUBSTITUTE всегда возвращают последовательность того-же типа, что и переданный аргумент.

Вы можете изменить поведение этих функций используя различные именованные аргументы. Например, по умолчанию, эти функции ищут в последовательности точно такой же объект, что и переданный в качестве аргумента. Вы можете изменить это поведение двумя способами: во первых, вы можете использовать именованный аргумент :test для указания функции, которая принимает два аргумента, и возвращает логическое значение. Если этот аргумент указан, то он будет использоваться для сравнения каждого элемента, вместо стандартной проверки на равенство с помощью EQL.5) Во-вторых, используя именованный параметр :key вы можете передать функцию одного аргумента, которая будет вызвана для каждого элемента последовательности для извлечения значения, которое затем будет сравниваться с переданным объектом. Однако заметьте, что функции (например FIND), возвращающие элементы последовательности, все равно будут возвращать элементы, а не значения, извлеченные из этих элементов.

(count "foo" #("foo" "bar" "baz") :test #'string=)    ==> 1
(find 'c #((a 10) (b 20) (c 30) (d 40)) :key #'first) ==> (C 30)

Для ограничения действия этих функций в рамках только определенных пределов, вы можете указать граничные индексы, используя именованные аргументы :start и :end. Передача NIL в качестве значения :end (или его полное отсутствие) равносильно указанию длины последовательности.6)

Если указывается не равный NIL аргумент :from-end, то элементы последовательности проверяются в обратном порядке. Простое указание :from-end может затронуть результаты FIND и POSITION. Например:

(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)

Также использование :from-end может влиять на работу REMOVE и SUBSTITUTE при использовании с другим именованным параметром – :count, который используется для указания количества заменяемых или удаляемых элементов. Если вы указываете :count меньший, чем количество совпадающих элементов, то результат будет зависеть от того, с какого конца последовательности вы начинаете обработку:

(remove #\a "foobarbaz" :count 1)             ==> "foobrbaz"
(remove #\a "foobarbaz" :count 1 :from-end t) ==> "foobarbz"

И хотя :from-end не может изменить результат функции COUNT, его использование может влиять на порядок элементов, передаваемых функциям, указанным в параметрах :test и :key, которые возможно могут вызвать побочные эффекты. Например:

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

В таблице 11-2 приведены описания всех стандартных аргументов.

Table 11-2. Стандартные именованные аргументы функций работы с последовательностями

Аргумент Описание Значение по умолчанию
:test Функция двух аргументов, используемая для сравнения элементов (или значений, извлеченных функцией :key) с указанным объектом. EQL
:key Функция одного аргумента, используемая для извлечения значения из элемента последовательности. NIL указывает на использование самого элемента. NIL
:start Начальный индекс (включительно) обрабатываемой последовательности. 0
:end Конечный индекс (n-1) обрабатываемой последовательности. NIL указывает на конец последовательности. NIL
:from-end Если имеет истинное значение, то последовательность будет обрабатываться в обратном порядке, от конца к началу. NIL
:count Число, указывающее количество удаляемых или заменяемых элементов, или NIL для всех элементов (только для REMOVE и SUBSTITUTE). NIL

Аналогичные функции высшего порядка

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

(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) #\f))
#("foo" "bar" "baz" "foom")) ==> #("foo" "foom")

В соответствии со стандартом языка, функции с суффиксом -IF-NOT являются устаревшими. Однако, это требование само считается неразумным. Если стандарт будет пересматриваться, то скорее будет удалено это требование, а не функции с суффиксом -IF-NOT. Для некоторых вещей, REMOVE-IF-NOT может использоваться чаще, чем REMOVE-IF. За исключением своего отрицательно звучащего имени, в действительности REMOVE-IF-NOT является положительной функцией – она возвращает элементы, которые соответствуют предикату.7)

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

(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")

Семейство функций REMOVE также имеет четвертый вариант, функцию REMOVE-DUPLICATES, которая имеет один аргумент – последовательность, из которой удаляются все, кроме одного экземпляра, каждого дублированного элемента. Она может принимать те же самые именованные аргументы что и REMOVE, за исключением :count, поскольку она всегда удаляет все дубликаты.

(remove-duplicates #(1 2 1 2 3 1 2 3 4)) ==> #(1 2 3 4)

Работа с последовательностью целиком

Некоторое количество функций выполняют операции над последовательностями целиком. Это приводит к тому, что они проще чем функции, которые я описывал ранее. Например, COPY-SEQ и REVERSE получают по одному аргументу – последовательности, и возвращают новую последовательность того же самого типа. Последовательность, возвращенная COPY-SEQ содержит те же самые элементы, что и последовательность, аргумент этой функции, в то время как последовательность возвращенная REVERSE содержит те же самые элементы, но в обратном порядке. Заметьте, что ни одна из этих функций не копирует сами элементы, новым объектом является только возвращаемая последовательность.

Функция CONCATENATE создаёт новую последовательность, содержащую объединение любого числа последовательностей. Однако, в отличие от REVERSE и COPY-SEQ, которые просто возвращают последовательность того же типа, что и переданный аргумент, функции CONCATENATE должно быть явно указано, какой тип последовательности необходимо создать в том случае, если ее аргументы имеют разные типы. Первым аргументом функции является описание типа, подобный параметру :element-type функции MAKE-ARRAY. В этом случае, вероятнее всего вы будет использовать следующие символы для указания типа: VECTOR, LIST или STRING.9) Например:

(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" '(#\d #\e #\f)) ==> "abcdef"

Сортировка и слияние

Функции SORT и STABLE-SORT обеспечивают два метода сортировки последовательности. Они обе получают последовательность и функцию двух аргументов, и возвращают отсортированную последовательность.

(sort (vector "foo" "bar" "baz") #'string<) ==> #("bar" "baz" "foo")

Разница между этими функциями заключается в том, что STABLE-SORT гарантирует, что она не будет изменять порядок элементов, которые считаются одинаковыми, в то время как SORT гарантирует только, что результат будет отсортирован, так что некоторые одинаковые элементы могут быть поменяны местами.

Обе эти функции являются примерами так называемых деструктивных функций. Деструктивным функциям допускается (обычно в целях эффективности) модификация переданных аргументов тем или иным способом. Отсюда следует две вещи: во-первых, вы всегда должны что-то делать с возвращаемым значением этих функций (например присвоить его переменной, или передать его другой функции), и во-вторых, если вы хотите что-то ещё делать с передаваемым в деструктивную функцию аргументом, то вы должны передать его копию, а не оригинальное значение. Я расскажу о деструктивных функциях более подробно в следующей главе.

Обычно вы не беспокоитесь о несортированной версии последовательности, так что имеет смысл позволить SORT и STABLE-SORT менять последовательность в процессе ее сортировки. Но это значит, что вы должны запомнить, что вы должны писать:10)

(setf my-sequence (sort my-sequence #'string<))

вместо:

(sort my-sequence #'string<)

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

Функция MERGE принимает две последовательности и функцию-предикат, и возвращает последовательность, полученную путем слияния двух последовательностей в соответствии с предикатом. Она относится к функциям сортировки, так что, если каждая последовательность уже была отсортирована с использованием того же самого предиката, то и полученная последовательность также будет отсортирована. Также как и функции сортировки, MERGE принимает аргумент :key. Подобно CONCATENATE, и по тем же причинам, первым аргументом MERGE должно быть описание типа последовательности, которая будет получена в результате работы.

(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)

Работа с частями последовательностей

Другой набор функций позволит вам работать с частями последовательностей. Наиболее часто употребляемой функцией является SUBSEQ, которая выделяет часть последовательности начиная с определенного индекса и заканчивая другим индексом или концом последовательности. Например:

(subseq "foobarbaz" 3)   ==> "barbaz"
(subseq "foobarbaz" 3 6) ==> "bar"

Для результата SUBSEQ также можно выполнить SETF, но оно не сможет увеличить или уменьшить последовательность; если часть последовательности и новое значение имеют разные длины, то более короткое из них определяет то, как много знаков будет изменено.

(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"

Вы можете использовать функцию FILL для заполнения нескольких значений последовательности одним и тем же значением. Обязательными аргументами являются последовательность и значение, которым нужно заполнить элементы. По умолчанию, заполняется вся последовательность; вы можете использовать именованные аргументы :start и :end для ограничения границ заполнения.

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

(position #\b "foobarbaz") ==> 3
(search "bar" "foobarbaz") ==> 3

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

(mismatch "foobarbaz" "foom") ==> 3

Эта функция возвращает NIL если строки совпадают. MISMATCH может также принимать стандартные именованные аргументы: аргумент :key для указания функции для извлечения сравниваемых значений; аргумент :test для указания функции сравнения; и аргументы :start1, :end1, :start2 и :end2 для указания границ действия внутри последовательностей. Также, указание :from-end со значением T приводит к тому, что поиск осуществляется в обратном порядке, заставляя MISMATCH вернуть индекс позиции в первой последовательности, где начинается общий суффикс последовательностей.

(mismatch "foobar" "bar" :from-end t) ==> 3

Предикаты для последовательностей

Другими полезными функциями являются EVERY, SOME, NOTANY и NOTEVERY, которые пробегают по элементам последовательности выполняя заданный предикат. Первым аргументом всех этих функций является предикат, а остальные аргументы – последовательности. Предикат должен получать столько аргументов, сколько последовательностей будет передано функциям. Элементы последовательностей передаются предикату (по одному элементу за раз) пока не закончатся элементы, или не будет выполнено условие завершения: EVERY завершается, возвращая ложное значение, сразу как это значение будет возвращено предикатом. Если предикат всегда возвращает истинное значение, то функция также вернет истинное значение. SOME возвращает первое не NIL значение, возвращенное предикатом, или возвращает ложное значение, если предикат никогда не вернул истинного значения. NOTANY возвращает ложное значение, если предикат возвращает истинное значение, или истинное, если этого не произошло. А NOTEVERY возвращает истинное значение сразу, как только предикат возвращает ложное значение, или ложное, если предикат всегда возвращал истинное. Вот примеры проверок для одной последовательности:

(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

А эти вызовы выполняют попарное сравнение последовательностей:

(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

Функции отображения последовательностей

В заключение, последними из функций работы с последовательностями, будут рассмотрены функции отображения (mapping). Функция MAP, подобно функциям-предикатам для последовательностей, получает функцию нескольких аргументов, и несколько последовательностей. Но вместо логического значения, MAP возвращает новую последовательность, содержащую результаты применения функции к элементам последовательности. Также как для CONCATENATE и MERGE, MAP необходимо сообщить тип создаваемой последовательности.

(map 'vector #'* #(1 2 3 4 5) #(10 9 8 7 6)) ==> #(10 18 24 28 30)

Функция MAP-INTO похожа на MAP за исключением того, что вместо создания новой последовательности заданного типа, она помещает результаты в последовательность, заданную в качестве первого аргумента. Эта последовательность может иметь такой же тип, как одна из последовательностей, предоставляющих данные для функции. Например, для суммирования нескольких векторов (a, b и c) в один, вы должны написать:

(map-into a #'+ a b c)

Если последовательности имеют разную длину, то MAP-INTO изменяет столько элементов, сколько присутствует в самой короткой последовательности, включая ту, в которую помещаются результаты. Однако, если последовательность будет отображаться в вектор с указателем заполнения, то число изменяемых элементов будет определяться не указателем заполнения, а размером вектора. После вызова MAP-INTO, указатель заполнения будет установлен равным количеству изменённых элементов. Однако MAP-INTO не будет изменять размер векторов, которые допускают такую операцию.

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

(reduce #'+ #(1 2 3 4 5 6 7 8 9 10)) ==> 55

REDUCE является очень полезной функцией – когда вам нужно создать из последовательности одно значение, есть вероятность, что вы сможете сделать это с помощью REDUCE, и она часто приводит к лаконичной записи того, что вы хотите сделать. Например, для нахождения максимального значения в последовательности вы можете просто написать (reduce #'max numbers). REDUCE также принимает полный набор стандартных именованных аргументов (:key, :from-end, :start и :end), а также один, уникальный для REDUCE (:initial-value). Этот аргумент указывает значение, которое будет логически помещено до первого элемента последовательности (или после последнего, если вы также зададите :from-end истинное значение).

Хэш-таблицы

Другой коллекцией общего назначения предоставляемой Common Lisp является хэш-таблица. В то время как вектора являются структурами данных с доступом по целочисленному индексу, хэш-таблицы позволяют вам использовать в качестве индексов (ключей) любые объекты. Когда вы добавляете объекты в хэш-таблицу, вы сохраняете их с определенным ключом. Позднее вы можете использовать тот же самый ключ для доступа к значению. Или вы можете связать новое значение с тем же самым ключом – каждый ключ отображается в единственное значение.

Без указания дополнительных аргументов MAKE-HASH-TABLE создаёт хэш-таблицу, которая сравнивает ключи с использованием функции EQL. Это нормально до тех пор, пока вы не захотите использовать в качестве ключей строки, поскольку две строки с одинаковым содержимым, не обязательно равны в терминах EQL. В таком случае вы захотите использовать для сравнения функцию EQUAL, что вы можете сделать передав функции MAKE-HASH-TABLE символ EQUAL в качестве именованного аргумента :test. Кроме того, для аргумента :test можно использовать еще два символа: EQ и EQUALP. Конечно, эти символы являются именами стандартных функций сравнения объектов, которые я обсуждал в главе 4. Однако, в отличие от аргумента :test, передаваемого функциям работы с последовательностями, аргумент :test функции MAKE-HASH-TABLE не может использовать произвольную функцию – допустимы только значения EQ, EQL, EQUAL и EQUALP. Это происходит потому что хэш-таблицы в действительности нуждаются в двух функциях – функции сравнения и функции хэширования, которая вычисляет численный хэш-код из ключа способом, совместимым с тем как функция сравнения однозначно сравнивает два ключа. Хотя стандарт языка предоставляет хэш-таблицы, которые используют только стандартные функции сравнения, большинство реализаций обеспечивают некоторые механизмы для создания более тонко настраиваемых хэш-таблиц.

Функция GETHASH обеспечивает доступ к элементам хэш-таблиц. Она принимает два аргумента: ключ и хэш-таблицу, и возвращает значение, если оно найдено, или NIL в противном случае.11) Например:

(defparameter *h* (make-hash-table))
(gethash 'foo *h*) ==> NIL
(setf (gethash 'foo *h*) 'quux)
(gethash 'foo *h*) ==> QUUX

Поскольку GETHASH возвращает NIL если ключ не присутствует в таблице, то нет никакого способа узнать отсутствует ли ключ в таблице, или для данного ключа соответствует значение NIL. Функция GETHASH решает эту проблему за счет использования способа, который мы еще не обсуждали – возврат нескольких значений. В действительности GETHASH возвращает два значения: главное значение – значение для указанного ключа или NIL. Дополнительное значение имеет логический тип и указывает, присутствует ли значение в хэш-таблице. Из-за способа реализации возврата множественных значений, дополнительные значения просто отбрасываются, если только пользователь не обрабатывает эту ситуацию специальным образом, используя средства, которые "видят" множественные значения.

Я буду подробно обсуждать возврат множественных значений в главе 20, но сейчас я дам вам лишь общее представление о том, как использовать макрос MULTIPLE-VALUE-BIND для получения дополнительных значений, которые возвращает GETHASH. Макрос MULTIPLE-VALUE-BIND создаёт привязки переменных, как это делает LET, заполняя их множеством значений, возвращенных вызываемой функцией.

Следующие примеры показывают как вы можете использовать MULTIPLE-VALUE-BIND; связываемые переменные содержат значение и признак его наличия в таблице:

(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 , поскольку ключ не найден."

Поскольку установка значения в NIL оставляет ключ в таблице, вам понадобится другая функция для полного удаления пары ключ/значение. Функция REMHASH получает такие же аргументы как и GETHASH, и удаляет указанную запись. Вы также можете полностью очистить хэш-таблицу с помощью функции CLRHASH.

Функции для работы с записями в хэш-таблицах

Common Lisp предоставляет разные способы для работы с записями в хэш-таблицах. Простейшим из них является использование функции MAPHASH. Также как и функция MAP, функция MAPHASH принимает в качестве аргументов функцию двух аргументов и хэш-таблицу, и выполняет указанную функцию для каждой пары ключ/значение. Например, для вывода всех пар ключ/значение, вы можете использовать такой вызов MAPHASH:

(maphash #'(lambda (k v) (format t "~a => ~a~%" k v)) *h*)

Последствия добавления или удаления записей в хэш-таблице во время прохода по ее записям стандартом не указываются (и скорее всего это будет плохой практикой), за исключением двух случаев: вы можете использовать SETF вместе с GETHASH для изменения значения текущей записи, и вы можете использовать REMHASH для удаления текущей записи. Например, для удаления всех записей, чье значение меньше чем десять, вы можете записать вот так:

(maphash #'(lambda (k v) (when (< v 10) (remhash k *h*))) *h*)

Другим способом итерации по элементам хэш-таблицы является использование макроса LOOP, который будет описан в главе 22.12) Код использующий LOOP, реализующий то же, что и первый пример с MAPHASH, будет выглядеть вот так:

(loop for k being the hash-keys in *h* using (hash-value v)
do (format t "~a => ~a~%" k v))

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

1)Когда вы познакомитесь со всеми типами данных, которые есть в Common Lisp, вы также осознаете, что списки могут быть полезны для моделирования структур данных, которые позже будут заменены на что-то более эффективное, после того, как станет ясно, как именно данные будут использоваться.
2)Векторы называются векторами, а не массивами, как их аналоги в других языках программирования, поскольку Common Lisp поддерживает настоящие многомерные массивы. Одинаково корректно (хотя и несколько неуклюже) ссылаться на них как на одномерные массивы
3)Элементы массива "должны" быть заданы до того, как вы будете осуществлять доступ к ним, поскольку иначе поведение будет неопределенным; Lisp не обязан останавливать вас при совершении ошибок.
4)Хотя они часто используются вместе, аргументы :fill-pointer и :adjustable все равно являются независимыми друг от друга – вы можете создать массив с изменяемым размером без указателя заполнения. Однако, вы можете использовать VECTOR-PUSH и VECTOR-POP только с векторами, которые имеют указатель заполнения, а VECTOR-PUSH-EXTEND – только с векторами которые имеют переменный размер и указатель заполнения. Вы также можете использовать функцию ADJUST-ARRAY для изменения параметров массивов переменной длины, а не только изменения длины вектора.
5)Другой именованный параметр, :test-not указывает предикат, который будет использоваться точно также как и параметр :test, за тем исключением, что результат будет изменён на противоположное значение. Однако этот параметр считается устаревшим, и предпочтительным является использование функции COMPLEMENT. COMPLEMENT получает аргумент-функцию и возвращает функцию, которая получает то же самое количество аргументов, что и оригинальная, но возвращает результат, имеющий противоположное значение результату возвращаемому оригинальной функцией. Так что вы можете (и должны) писать вот так:
(count x sequence :test (complement #'some-test))
вместо:
(count x sequence :test-not #'some-test)
6)Заметьте однако, что для REMOVE и SUBSTITUTE указание :start и :end приводит к ограничению количества аргументов, подпадающих под удаление или замену; элементы до :start и после :end будут переданы без изменений.
7)Эта функция обеспечивает туже функциональность, что и grep в Perl и filter в Python.
8)Отличием предиката, передаваемого аргументу :test от аргумента-функции, передаваемого в функции с суффиксами -IF и -IF-NOT, является то, что предикат параметра :test имеет два аргумента и используется для сравнения элементов последовательности с конкретным объектом, в то время как предикаты для функций с суффиксами -IF и -IF-NOT имеют один аргумент, и используются для проверки только элементов последовательности. Если бы базовые варианты не существовали, то вы могли бы реализовать их с помощью функций с суффиксом -IF, путем указания объекта в функции-предикате.
(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)
9)Если вы указываете функции CONCATENATE, что она должна вернуть специализированный вектор, например, строку, то все элементы аргументов-последовательностей должны иметь тот же тип, что и элементы этого вектора.
10)Когда передаваемая последовательность является вектором, "разрушение" гарантирует изменение элементов по месту, так что вы можете выйти без сохранения возвращаемого значения. Однако, хорошим стилем будет обязательное использование возвращаемого значения, поскольку функции сортировки могут изменять списки произвольным образом.
11)По историческим причинам, порядок аргументов GETHASH отличается от порядка аргументов функции ELTELT получает коллекцию в качестве первого аргумента, а индекс – в качестве второго; а GETHASH наоборот: ключ – первым, а коллекцию – вторым.
12)Использование LOOP для работы с хэш-таблицами обычно основывается на использовании более примитивной формы, WITH-HASH-TABLE-ITERATOR, о которой вам не нужно беспокоиться; она была добавлена в язык специально для поддержки реализации таких вещей как LOOP и практически не нужна до тех пор, пока вы не соберетесь реализовать совершенно новый способ итерации по элементам хэш-таблиц.
Предыдущая Оглавление Следующая
@2009-2013 lisper.ru