Манипуляция элементами списков

Ещё одна простая задача заключается в манипуляции элементами списков (выделение элементов, получение из них новых списков и пр.). Она решается следующим набором функций.

Три указанные функции являются основными при манипуляции элементами списков. Их работа напрямую связана с организацией памяти в Lisp-машине. Очевидно, имея указатель на первую ячейку структуры списка, car возвращает указатель на голову, а cdr - на хвост. Что касается cons, он конструирует из двух указателей новую ячейку, получая структуру нового списка. Разумеется, в случае, например, присвоения результирующего значения какой-либо переменной, структуру списка необходимо скопировать дабы не вызывать побочного эффекта изменения одного списка при работе с другим. Приведём примеры работы с CAR и CDR:

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

Для облегчения работы с функциями CAR и CDR были введены ещё несколько функций. Дело в том, что зачастую надо достать элемент откуда-нибудь из середины, что приводит к большой вложенности вызовов, например, получим элемент E из списка (B (D E) F):

То же самое можно изложить с помощью функции, условно называемой CXXXXR, в которой XXXX собирается из вторых букв последовательно вложенных CAR и CDR, в нашем примере CADADR:

Таким образом, подобная функция просто представляет собой последовательное вычисление функций CAR и CDR. Сразу заметим, что они вычисляются справа налево, что и соответствует нормальному порядку вложенности. В большинстве реализаций Lisp число символов A и D в них не может быть больше 4х (в виду стремительного роста количества функций, реализующих оператор, при увеличении его длины).

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

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

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

Во многих реализациях Lisp функции CAR и CDR также имеют синонимы, называемые FIRST и REST. Их действие совершенно аналогично CAR и CDR. Также для удобства программиста иногда вводят функции SECOND,THIRD и так далее, вплоть до TENTH:

Обобщением подобных функций является функция NTH, выбирающая из списка элемент по его номеру (начиная от 0). Очевидно, (FIRST X) есть (NTH 0 X), (SECOND X) есть (NTH 1 X) и т.д. Если такого элемента нет, возвращается NIL. Как будет показано позднее при обсуждении типов данных языка Lisp, функция nth может использоваться не только для чтения элемента списка, в сочетании с setf она также может записывать в этот элемент новое значение.

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

Основные конструкции