В данной статье рассказывается про списки. Списки это базовая компонента языка lisp. Именно для обработки списков был разработан lisp. Другие структуры данных появились позже. Однако, так ли просты списки как это кажется на первый взгляд? Об этом вы узнаете в этой статье.
Списки
На самом деле список это не монолитная структура как массив. Это и очевидно. Во многих языках программирования есть такая структура данных как список и состоит она из ячеек или элементов списка, которые ссылаются друг на друга. Другими словами базовой структурой данных является пара ссылок или cons-ячейка. Одна из этих ссылок определяет данные — ссылается на них. Другая на следующую ячейку, либо на nil. Из таких структур можно строить не только списки, но и, например, деревья. Для работы с такими парами в lisp существует свой набор функций:
(cons 1 2) ; (1 . 2) (car (cons 1 2)) ; 1 (cdr (cons 1 2)) ; 2 (cons 1 nil) ; (1) (cons 1 (cons 2 nil)) ; (1 2) (cons 1 (cons 2 (cons 3 nil))) ; (1 2 3)
Возможно с знанием об этих ячейках будет проще понять статью про обработку коллекций. Кстати, всего существует 28 c*r функций. Между c и r можно вставить до 4 символов — либо a, либо d. Например cadadr.
Обработка списков
| Название | Обязательные аргументы | Возвращаемое значение |
| COUNT | Объект и последовательность | Число вхождений в последовательности |
| FIND | Объект и последовательность | Объект или NIL |
| POSITION | Объект и последовательность | Индекс ячейки в последовательности или NI |
| 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
Функции высшего порядка
Здесь я уже не буду приводить много примеров. Смысл в том, что к функциям предыдущего размера (например count), добавляются постфиксы -if, -if-not. При вызове таких функций одним из аргументов передаётся функция условия. И есть ещё одна функция — remove-duplicates. Ей ничего лишнего не передаётся, она просто удаляет повторяющиеся значения. Вот так это работает:
(count-if #'evenp #(1 2 3 4 5)) ; 2 чётных (count-if-not #'evenp #(1 2 3 4 5)) ; 3 нечётных (remove-duplicates #(1 2 1 2 3 1 2 3 4)) ; #(1 2 3 4)
Работа со всей последовательностью
Так же есть функции высшего порядка, которые работают со всей последовательностью, это функции сортировки, слияния и т.п. Сразу приведу примеры:
(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 (vector "foo" "bar" "baz") #'string<) ; #("bar" "baz" "foo")
(setf my-sequence (sort my-sequence #'string<)) ; Не забывайте сохранять результат сортировки
(merge 'vector #(1 3 5) #(2 4 6) #'<) ; #(1 2 3 4 5 6)
Работа с частью последовательности
Теперь несколько функций для работы с частями последовательностей:
(defparameter *x* (copy-seq "foobarbaz")) (setf (subseq *x* 3 6) "xxx") ; "fooxxxbaz" (setf (subseq *x* 3 6) "abcd") ; "fooabcbaz" (вставилось не всё) (setf (subseq *x* 3 6) "xx") ; "fooxxcbaz" (position #\b "foobarbaz") ; 3 ищет character (search "bar" "foobarbaz") ; 3 ищет строку (mismatch "foobarbaz" "foom") ; 3 начал несовпадать с 3-го элемента (mismatch "foobar" "bar" :from-end t) ; 3, то же но с конца
Предикаты
Кроме этих функций есть предикаты:
(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
Функции отображения
Последним примером функций высшего порядка являются функции отображения:
(map 'vector #'* #(1 2 3 4 5) #(10 9 8 7 6)) ; #(10 18 24 28 30) (map-into a #'+ a b c) ; отображает последовательность в себя (reduce #'+ #(1 2 3 4 5 6 7 8 9 10)) ; 55
Другие функции для обработки списков
| Функция | Описание |
| LAST | Возвращает последнюю cons-ячейку в списке. Если вызывается с целочисленным аргументом n, возвращает n ячеек. |
| BUTLAST | Возвращает копию списка без последней cons-ячейки. Если вызывается с целочисленным аргументом n, исключает последние n ячеек. |
| NBUTLAST | Утилизирующая версия BUTLAST; может изменять переданный список-аргумент, не имеет строго заданных побочных эффектов. |
| LDIFF | Возвращает копию списка до заданной cons-ячейки. |
| TAILP | Возвращает TRUE если переданный объект является cons-ячейкой, которая является частью списка. |
| LIST* | Строит список, содержащий все переданные аргументы кроме последнего, после этого присваивает CDR последней cons-ячейки списка последнему аргументу. Т.е. смесь LIST и APPEND. |
| MAKE-LIST | Строит список из n элементов. Начальные элементы списка NIL или значение заданное аргументом :initial-element. |
| REVAPPEND | Комбинация REVERSE и APPEND; инвертирует первый аргумент как REVERSE и добавляет второй аргумент. Не имеет строго заданных побочных эффектов. |
| NRECONC | Утилизирующая версия предыдущей функции; инвертирует первый аргумент как это делает NREVERSE и добавляет второй аргумент. Не имеет строгих побочных эффектов. |
| CONSP | Предикат для тестирования является ли объект cons-ячейкой. |
| ATOM | Предикат для тестирования является ли объект не cons-ячейкой. |
| LISTP | Предикат для тестирования является ли объект cons-ячейкой или NIL |
| NULL | Предикат для тестирования является ли объект NIL. Функционально эквивалентен функции NOT, но стилистически лучше использовать NULL при тестировании является ли список NIL, NOT для проверки булевого выражения FALSE |