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

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

car	Получение головы списка. Аргумент всегда список

cdr	Получение хвоста списка. Аргумент всегда список

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

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

>(CAR '(a b c)) A >(CAR '((a) (b) (c)) (A) >(CDR '(a b c)) (B C) >(CDR '((a) (b) (c)) ((B) (C)) >(CDR '(a)) NIL

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

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

>(CAR (CDR (CAR (CDR '(B (D E) F))))) E

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

>(CADADR '(B (D E) F)) E

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

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

>(CONS 'a 'b) (A . B) >(CONS 'a '(b)) (A B) >(CONS '(A) '(B)) ((A) B)

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

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

>(CAR '(A B)) A >(CONS (CAR '(A B)) NIL) (A)

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

>(SECOND '(a b c)) B >(THIRD '(a b c)) C

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

Nth	Возвращает элемент с индексом, заданным первым аргументом, из списка, заданного вторым аргументом

>(NTH 1 '((A)(B))) (B) >(NTH 2 '((A)(B))) NIL

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

list	Преобразует все свои аргументы в список

>(LIST 'A '(B C) 'D) (A (B C) D)