Списки и Cons-ячейки

cons-ячейка является записью структуры, содержащей два элемента, называемых car и cdr. Cons-ячейки используются преимущественно для отображения списков.

Список рекурсивно определяется пустым списком или cons-ячейкой, у которой cdr элемент является списком. Таким образом, список является цепочкой cons-ячеек связанных с помощью их cdr элементов, заканчивающейся пустым списком с помощью nil. car элементы cons-ячеек называются элементами списка. Для каждого элемента списка существует cons-ячейка. Пустой список не имеет элементов вообще.

Список записывается с помощью элементов в необходимом порядке, разделяемых пробелом (пробел, таб, возврат каретки) и окружённых круглыми скобками.

(a b c) ;Список трёх элементов (2.0s0 (a 1) #\*) ;Список трёх элементов: короткого с плавающей точкой ; числа, другого списка, и строкового символа

Таким образом, пустой список nil может быть записан, как (), потому что является списком без элементов.

Список с точкой является списком, последняя cons-ячейка которого в cdr элементе содержит объект данных, а не nil (который не является cons-ячейкой, иначе исходная cons-ячейка не была бы последней). Такой список называется «списком с точкой» по причине используемой для него специальной записи: элементы списка записанные в двух последних позициях списка перед закрывающей круглой скобкой разделяются точкой (обрамленной с двух сторон пробелами). Тогда последнее значение будет содержаться в cdr элементе последней cons-ячейки. В особых случаях, одиночная cons-ячейка может быть записана с помощью car и cdr элементов, обрамленных в круглые скобки и разделённых с помощью точки, окружённой пробелами. Например:

(a . 4) ;cons-ячейка, car которой является символом ; и cdr которой равен целому числу (a b c . d) ;Список с точкой с тремя элементами, у последней ; cons-ячейки cdr равен символу d

Правильной записью также является что-то наподобие (a b . (c d)); она означает то же, что и (a b c d). Стандартный Lisp вывод никогда не распечатает список в первом виде, таким образом когда это возможно, он старается избавиться от записи с точкой.

Часто термин список употребляется и для обычных списков и для списков с точкой. Когда разница важна, для списка, заканчивающегося с помощью nil, будет употребляться термин «Ъ список». Большинство функций указывают, что оперируют списками, ожидая, что они Ъ. Везде в этой книге, если не указано иное, передача списка с точкой в такие функции является ошибкой. _________________________________________________________________

Заметка для реализации: Implementors are encouraged to use the equivalent of the predicate endp wherever it is necessary to test for the end of a list. Whenever feasible, this test should explicitly signal an error if a list is found to be terminated by a non-nil atom. However, such an explicit error signal is not required, because some such tests occur in important loops where eﬃciency is important. In such cases, the predicate atom may be used to test for the end of the list, quietly treating any non-nil list-terminating atom as if it were nil.

Иногда используется термин дерево для ссылки на некоторую cons-ячейку, которая содержит другие cons-ячейки в своих car и cdr элементах, которые также содержат cons-ячейки в своих элементах и так далее, пока не будут достигнуты элементы, не являющиеся cons-ячейками. Такие элементы, не являющиеся cons-ячейками называются листьями дерева.

Списки, списки с точкой и деревья, все вместе не завершают список типов данных, они просто являются удобной точкой для рассмотрения таких структур, как cons-ячейки. Существуют также другие термины, такие как, например, ассоциативный список. Ни один из этих типов данных не является Lisp’овым типом данных. Типом данных являются cons-ячейки, а также nil является объектом типа null. Lisp’овый тип данных список подразумевает объединение типов cons-ячеек и null, и по этой причине содержит в себе оба типа: Ъ список и список с точкой.

2.4 Списки и Cons-ячейки