3.11. Последовательности |
61 |
(defun our-member-if (fn lst) (and (consp lst)
(if (funcall fn (car lst) lst
(our-member-if fn (cdr lst)))))
Функция adjoin – своего рода условный cons. Она присоединяет задан ный элемент к списку, но только если его еще нет в этом списке (т. е. не member):
>(adjoin ’b ’(a b c)) (A B C)
>(adjoin ’z ’(a b c)) (Z A B C)
Вобщем случае adjoin принимает те же аргументы по ключу, что и member.
Common Lisp определяет основные логические операции с множества ми, такие как объединение, пересечение, дополнение, для которых опре делены соответствующие функции: union, intersection, set-difference. Эти функции работают ровно с двумя списками и имеют те же аргумен ты по ключу, что и member.
>(union ’(a b c) ’(c b s)) (A C B S)
>(intersection ’(a b c) ’(b b c)) (B C)
>(set-difference ’(a b c d e) ’(b e)) (A C D)
Поскольку в множествах нет такого понятия, как упорядочение, эти функции не сохраняют порядок элементов в исходных списках. Напри мер, вызов set-difference из примера может с тем же успехом вернуть
(d c a).
3.11. Последовательности
Списки также можно рассматривать как последовательности элемен тов, следующих друг за другом в фиксированном порядке. В Common Lisp помимо списков к последовательностям также относятся векто ры. В этом разделе вы научитесь работать со списками как с последова тельностями. Более детально операции с последовательностями будут рассмотрены в разделе 4.4.
Длина последовательности определяется с помощью length:
> (length ’(a b c)) 3
Ранее мы писали урезанную версию этой функции, работающую толь ко со списками.
62 |
Глава 3. Списки |
Скопировать часть последовательности можно с помощью subseq. Второй аргумент (обязательный) задает начало подпоследовательности, а тре тий (необязательный) – индекс первого элемента, не подлежащего копи рованию.
>(subseq ’(a b c d) 1 2)
(B)
>(subseq ’(a b c d) 1) (B C D)
Если третий аргумент пропущен, то подпоследовательность заканчива ется вместе с исходной последовательностью.
Функция reverse возвращает последовательность, содержащую исход ные элементы в обратном порядке:
> (reverse ’(a b c)) (C B A)
С помощью reverse можно, например, искать палиндромы, т. е. последо вательности, читаемые одинаково в прямом и обратном порядке (на пример, (a b b a)). Две половины палиндрома с четным количеством аргументов будут зеркальными отражениями друг друга. Используя length, subseq и reverse, определим функцию mirror?1:
(defun mirror? (s)
(let ((len (length s))) (and (evenp len)
(let ((mid (/ len 2))) (equal (subseq s 0 mid)
(reverse (subseq s mid)))))))
Эта функция определяет, является ли список таким палиндромом:
> (mirror? ’(a b b a)) T
Для сортировки последовательностей в Common Lisp есть встроенная функция sort. Она принимает список, подлежащий сортировке, и функ цию сравнения от двух аргументов:
> (sort ’(0 2 1 3 8) #’>) (8 3 2 1 0)
С функцией sort следует быть осторожными, потому что она деструк тивна. Из соображений производительности sort не создает новый спи сок, а модифицирует исходный. Поэтому если вы не хотите изменять исходную последовательность, передайте в функцию ее копию.°
Используя sort и nth, запишем функцию, которая принимает целое чис ло n и возвращает n-й элемент в порядке убывания:
1Ричард Фейтман указал, что есть более простой способ проверки палиндро ма, а именно: (equal x (reverse x)). – Прим. перев.
3.12. Стопка |
63 |
(defun nthmost (n lst) |
|
(nth (- n 1)
(sort (copy-list lst) #’>)))
Мы вынуждены вычитать единицу, потому что nth индексирует элемен ты, начиная с нуля, а наша nthmost – с единицы.
> (nthmost 2 ’(0 2 1 3 8)) 3
Наша реализация nthmost не самая эффективная, но мы пока не будем вдаваться в тонкости ее оптимизации.
Функции every и some применяют предикат к одной или нескольким по следовательностям. Если передана только одна последовательность, они проверяют, удовлетворяет ли каждый ее элемент этому предикату:
>(every #’oddp ’(1 3 5))
T
>(some #’evenp ’(1 2 3))
T
Если задано несколько последовательностей, предикат должен прини мать количество аргументов, равное количеству последовательностей, и из каждой последовательности аргументы берутся по одному:
> (every #’> ’(1 3 5) ’(0 2 4)) T
Если последовательности имеют разную длину, кратчайшая из них огра ничивает диапазон проверки.
3.12. Стопка
Представление списков в виде ячеек позволяет легко использовать их в качестве стопки (stack). В Common Lisp есть два макроса для работы со списком как со стопкой: (push x y) кладет объект x на вершину стоп ки y, (pop x) снимает со стопки верхний элемент. Оба эти макроса можно определить с помощью функции setf. Вызов
(push obj lst)
транслируется в
(setf lst (cons obj lst))
а вызов
(pop lst)
в
(let ((x (car lst)) (setf lst (cdr lst)) x)
64 |
Глава 3. Списки |
Так, например
>(setf x ’(b))
(B)
>(push ’a x) (A B)
>x
(A B)
>(setf y x) (A B)
>(pop x)
A
>x
(B)
>y (A B)
Структура ячеек после выполнения приведенных выражений показана на рис. 3.9.
x = |
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
y = |
|
|
|
|
|
|
|
|
|
|
nil |
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
a |
|
|
|
|
b |
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис. 3.9. Эффект от push и pop
С помощью push можно также определить итеративный вариант функ ции reverse для списков:
(defun our-reverse (lst) (let ((acc nil))
(dolist (elt lst) (push elt acc))
acc))
В этом варианте мы начинаем с пустого списка и последовательно кла дем на него, как на стопку, элементы исходного. Последний элемент окажется на вершине стопки, то есть в начале списка.
Макрос pushnew похож на push, однако использует adjoin вместо cons:
> (let ((x ’(a b))) (pushnew ’c x) (pushnew ’a x) x)
(C A B)
Элемент a уже присутствует в списке, поэтому не добавляется.