Операции со списками и ячейки, операции со строками

Так как список является одной из базовых структур данных в COMMON LISP, язык содержит основные конструкции для обработки списков. Именно им COMMON LISP обязан своим названием: «LISt Processor» (Обработчик списков). В отличие от первых версий LISP, COMMON LISP является языком общего назначения и предоставляет разработчикам широкий набор структур данных.

Наиболее простыми операциями для обработки списков являются CAR и CDR. Функция CAR возвращает первый элемент заданного списка, CDR возвращает все элементы, кроме первого. Работа функций иллюстрируется примерами ниже:

> (CAR f(A В С))

А

> (CDR f(A В С))

  • (В С)
  • (CAR А) — ошибка, так как атом А не является списком, (CAR ‘ ()) также ошибка. Два последних случая ошибочны и для CDR.

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

(CAR (CDR f(A В С)))

Наиболее простым конструктором списка является функция CONS. Функция создает список из двух своих аргументов. Первый из аргументов может быть либо атомом, либо списком, второй, как правило, является списком. Если вторым аргументом является список, функция вставляет свой первый параметр в качестве первого элемента этого списка:

> (CONS fA ‘ (В С))

(А в С)

> (CONS f(A В) f(C D))

((А В) (С D))

Список из одного элемента также может быть создан с помощью CONS:

(CONS fA А)) возвращает (А)

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

> (LIST fA fB fC)

(А В C)

Последний пример эквивалентен выражению

(CONS fA (CONS fB (CONS C '())))

Если описывать работу CONS на более низком уровне, то можно сказать, что CONS объединяет два объекта в один, называемый ячейкой. Ячейкой называется пара указателей, первый из которых возвращает функция CAR, второй — CDR. С помощью ячеек удобно объединять в пару объекты любых типов, в том числе и другие ячейки. Благодаря такой возможности с помощью CONS можно строить произвольные списки. Любой непустой список может считаться парой, содержащей первый элемент списка и остальную его часть. Таким образом, списки представляют собой набор связанных между собой ячеек.

Список, состоящий из одной ячейки, можно получить при создании списка из одного элемента с помощью CONS, используя атом и пустой список:

(CONS fA '())

либо

(CONS fA NIL)

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

Список, состоящий из одной ячейки

Рис. 7.3. Список, состоящий из одной ячейки

С помощью CAR и CDR можно получить объект, на который указывает соответствующий указатель ячейки:

> (CAR (CONS 'A f()))

A

> (CDR (CONS fA '()))

NIL

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

Рассмотрим пример создания вложенного списка:

> (CONS f(A В) f(C D))

((А в) (С D))

Списки, содержащие внутри себя подсписки, называются вложенными, списки, не содержащие внутри себя подсписки, называются плоскими.

Структура, соответствующая списку из последнего примера, показана на рис. 7.4. В данном примере CAR будет возвращать первый подсписок, a CDR второй.

Вложенный список, состоящий из двух плоских подсписков

Рис. 7.4. Вложенный список, состоящий из двух плоских подсписков

Функция COPY-LIST возвращает копию списка, указанного в качестве параметра. Новый список имеет те же значения элементов, но размещенные в других ячейках.

> (COPY-LIST f(A в с))

(А В С)

Функция APPEND предназначена для объединения произвольного количества списков в один. Функция копирует все свои параметры, кроме последнего параметра.

> (APPEND f(A В) r(C D))

(А В С D)

В COMMON LISP имеются функции, позволяющие получить доступ к произвольному элементу списка.

Функция NTH служит для доступа к элементу по порядковому номеру:

> (NTH 2 f(A В С))

с

Для получения остатка списка используется функция NTHCDR. Остаток включает элемент списка с нужным порядковым номером и все последующие:

> (NTHCDR 2 '(А В С D))

(С D)

Функции NTH и NTHCDR ведут отсчет элементов списка, начиная с 0, и базируются на функциях CAR и CDR.

Ячейки можно представить как двоичные деревья, в этом случае один из указателей ячейки соответствует правому поддереву, а другой левому. В языке COMMON LISP есть несколько встроенных функций для работы с деревьями. Также в языке есть базирующаяся на списках встроенная функциональность, позволяющая использовать различные структуры данных, в том числе множество, последовательность, стек, ассоциативный список. Рассмотрение данных возможностей языка выходят за пределы данного пособия, с ними можно ознакомиться в [4].

Как было отмечено, строкой в языке COMMON LISP является одномерный массив, состоящий из знаков. По этой причине к строкам применимы все операции работы с массивами. С помощью функции AREF можно получить знак по его порядковому номеру в строке:

> (AREF “ABCD” 3)

#D

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

> (CHAR “ABCD” 3)

#D

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >