common-lisp
Типы списков

Обычные списки

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

(list 1 2 3)
;=> (1 2 3)

(first (list 1 2 3))
;=> 1

(rest (list 1 2 3))
;=> (2 3)

Существует множество функций, которые работают в «простых» списках, поскольку они только заботятся об элементах списка. К ним относятся find , mapcar и многие другие. (Многие из этих функций также будут работать над 17.1 концепциями последовательности для некоторых из этих функций.

Списки ассоциаций

Обычные списки полезны для представления последовательности элементов, но иногда более полезно представлять тип ключа для сопоставления значений. Common Lisp предоставляет несколько способов сделать это, включая настоящие хеш-таблицы (см. 18.1 «Хэш-таблицы» ). Существует два основных способа или представление ключей для сопоставлений значений в Common Lisp: списки свойств и списки ассоциаций . В этом примере описаны списки ассоциаций.

Список ассоциаций, или alist, является «простым» списком, элементами которого являются пунктирные пары, в которых автомобиль каждой пары является ключом, а cdr каждой пары является ассоциированным значением. Например,

(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))

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

(cdr (first (member 'mary *age* :key 'car)))
;=> 23

Функция- член возвращает хвост списка, начиная с ячейки cons, чей автомобиль является mary , то есть ((mary 23) (tim. 72)) , сначала возвращает первый элемент этого списка, который является (mary. 23) , а cdr возвращает правую часть этой пары, которая равна 23 . Хотя это один из способов доступа к значениям в списке ассоциаций, целью такого соглашения, как списки ассоциаций, является абстрагирование от основного представления (списка) и предоставление функций более высокого уровня для работы с структурой данных.

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

(assoc 'tim *ages*)
;=> (tim . 72)

Поскольку результат всегда будет ячейкой cons, если элемент присутствует, если ассоциатор возвращает nil , то элемент не был в списке:

(assoc 'bob *ages*)
;=> nil

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

(setf (cdr (assoc 'john *ages*) 35)

(incf (cdr (assoc 'john *ages*)))

incf работает в этом случае, потому что он основан на setf .

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

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

(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))

В список ассоциаций можно добавить одну пару ключей и значений, используя acons :

(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))

Функция- посредник выполняет поиск по списку слева направо, что означает, что возможно «замаскировать» значения в списке ассоциаций, не удаляя их из списка или не обновляя структуру структуры списка, просто добавляя новые элементы в список начало списка. Для этого предусмотрена функция acons :

(defvar *ages* (pairlis '(john mary tim) '(34 23 72)))

(defvar *new-ages* (acons 'mary 29 *ages*))

*new-ages*
;=> ((mary . 29) (john . 34) (mary . 23) (tim . 72))

И теперь поиск для mary вернет первую запись:

(assoc 'mary *new-ages*)
;=> 29

Списки свойств

Обычные списки полезны для представления последовательности элементов, но иногда более полезно представлять тип ключа для сопоставления значений. Common Lisp предоставляет несколько способов сделать это, включая настоящие хеш-таблицы (см. 18.1 «Хэш-таблицы» ). Существует два основных способа или представление ключей для сопоставлений значений в Common Lisp: списки свойств и списки ассоциаций . В этом примере описаны списки свойств.

Список свойств или plist - это «простой» список, в котором переменные значения интерпретируются как ключи и их связанные значения. Например:

(defparameter *ages* (list 'john 34 'mary 23 'tim 72))

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

(second (member 'mary *age*))
;=> 23

Функция- член возвращает хвост списка, начинающийся с mary , то есть (mary 23 tim 72) , а второй возвращает второй элемент этого списка, то есть 23 . Хотя это один из способов доступа к значениям в списке свойств, назначение такого списка, как списки свойств, состоит в том, чтобы абстрагироваться от основного представления (списка) и предоставлять функции более высокого уровня для работы с структурой данных.

Для списков свойств функция поиска - getf , которая принимает список свойств, ключ (обычно называемый индикатором ) и необязательное значение по умолчанию для возврата, если список свойств не содержит значения для ключа.

(getf *ages* 'tim)
;=> 72

(getf *ages* 'bob -1)
;=> -1

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

(setf (getf *ages* 'john) 35)

(incf (getf *ages* 'john))

incf работает в этом случае, потому что он основан на setf .

Чтобы просмотреть несколько свойств в списке свойств как один раз, используйте get-properties .

Функция getf выполняет поиск по списку слева направо, что означает, что возможно «замаскировать» значения в списке свойств, не удаляя их из списка или не обновляя ни одну структуру структуры списка. Например, используя список * :

(defvar *ages* '(john 34 mary 23 tim 72))

(defvar *new-ages* (list* 'mary 29 *ages*))

*new-ages*
;=> (mary 29 john 34 mary 23 tim 72)

И теперь поиск для mary вернет первую запись:

(getf *new-ages* 'mary)
;=> 29