Списки

  Рассматривая физическую форму представления списков, мы уже отмечали, что точечная пара, или списочная ячейка, состоит из двух частей: полей first и rest. Значением поля может быть произвольный объект (атом, буква, другой список, вектор, объект и т.д.). Список можно определить через nil и списочную пару следующим образом:

1. пустой список (), или nil, является списком;
2. каждая точечная пара, поле rest которой список, является списком.

  Таким образом список - это связанная через поле rest цепочка списочных ячеек, которая в поле rest последней ячейки содержит nil. Поля first этих ячеек представляют элементы списка.
  Набор действий со списками образует основной механизм представления данных в Лиспе, с помощью которого из объектов различных типов можно строить большие комплексы данных. Элементом списка так же, как и значением переменной, может быть произвольный объект. Используя списки, можно определять новые типы и структуры данных.

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

  ((a₁ . t₁) (a₂ . t₂) … (a_n . t_n))

  Первый элемент пары (first) называют ключом и второй (rest) - связанными с ключом данными. Обычно ключом является символ. Связанные с ним данные могут быть символами, списками или какими-нибудь другими объектами. С помощью а-списка можно объединить разнотипные, поименованные ключами компоненты данных в единый комплекс данных.
  В работе со списками пар нужно уметь строить списки, искать данные по ключу и обновлять их.

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

  (а-список pairlist ключи данные)

  Приведём пример:

>('словарь set '((один . 1)))
((один  . 1))
>('словарь set (словарь pairlist  '(три  два) '(3 2)))
((три  . 3)  (два . 2)  (один . 1))

  pairlist можно было бы определить следующим образом:

(nil  defmethod pairlist  (keyl datal)
  (nil  if  keyl
    (nil  cons
      (nil  cons  (keyl first)  (datal  first))
      (this pairlist  (keyl rest) (datal  rest)))
    this))

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

  (а-список assoc ключ)

которая ищет в списке пар данные соответствующие ключу, сравнивая искомый ключ с ключами пар слева направо. assoc можно было бы (просто) определить следующим образом:

(nil  defmethod assoc ())
('cons  defmethod assoc (a)
  (nil  if  (a  = ((this  first)  first))
    (this first)  ; значение - пара целиком
    ((this  rest) assoc a)))

  Например:

>(словарь  assoc 'два)
(два . 2)
>('cons defmethod значение  (слово)
  ((this  assoc слово) rest))
(lambda (слово)  ((this  assoc слово) rest)))
>(словарь  значение  'два)
2

  Заметьте, что в качестве значения assoc возвращает пару целиком, а не только искомые данные, или nil, если ключа нет. Есть ещё функция rassoc (обратная assoc), которая ищет ключ по заданным данным.

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

  (nil acons x y а-список) ≡ (nil cons (nil cons x y) а-список)

  Поскольку assoc просматривает список слева направо и доходит лишь до первой пары с искомым ключом, то более старые пары как бы остаются в тени более новых. Используемые таким образом а-списки хорошо решают, например, проблему поддержки меняющихся связей переменных и контекста вычисления.
  Преимуществом такого использования является простота изменения связей и возможность возврата к значениям старых связей. Недостатком является то, что поиск данных замедляется пропорционально длине списка.

  Если старое значение больше не потребуется, то а-список можно изменить, физически изменив данные, связанные с ключом. Это можно, например, сделать изменяющей значение поля rest псевдофункцией setrest:

  ((а-список assoc ключ) setrest новое-значение)

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