common-lisp
Консоли и списки
Поиск…
Списки как конвенция
Некоторые языки включают структуру данных списка. Common Lisp и другие языки семейства Lisp широко используют списки (а имя Lisp основано на идее LISt-процессора). Однако Common Lisp фактически не содержит примитивный тип данных списка. Вместо этого списки существуют по соглашению. Конвенция зависит от двух принципов:
- Символ nil - пустой список.
- Непустым списком является ячейка cons, чей автомобиль является первым элементом списка и чей cdr является остальной частью списка.
Это все, что есть в списках. Если вы прочитали пример, называемый What is cons cell? , то вы знаете, что ячейка cons, автомобиль которой X, а cdr - Y, может быть записана как (X, Y) . Это означает, что мы можем написать несколько списков на основе вышеизложенных принципов. Список элементов 1, 2 и 3 просто:
(1 . (2 . (3 . nil)))
Однако, поскольку списки настолько распространены в семействе языков Lisp, существуют специальные соглашения о печати за пределами простой пунктирной пары для cons-ячеек.
- Символ nil также может быть записан как () .
- Когда cdr одной cons-ячейки является другим списком (либо (), либо ячейкой cons), вместо того, чтобы писать одну cons-ячейку с точечной парной нотацией, используется «запись списка».
Обозначение списка показано наиболее четко несколькими примерами:
(x . (y . z)) === (x y . z)
(x . NIL) === (x)
(1 . (2 . NIL)) === (1 2)
(1 . ()) === (1)
Идея состоит в том, что элементы списка записываются в последовательном порядке в круглых скобках до тех пор, пока не будет достигнут окончательный cdr в списке. Если конечный cdr равен nil (пустой список), тогда записывается окончательная скобка. Если конечный cdr не равен nil (в этом случае список называется неправильным списком ), то записывается точка, а затем записывается окончательный cdr.
Что такое ячейка cons?
Ячейка cons, также известная как пунктирная пара (из-за ее напечатанного представления), представляет собой просто пару из двух объектов. Ячейка cons создается функцией cons
, а элементы в паре извлекаются с помощью функций car
и cdr
.
(cons "a" 4)
Например, это возвращает пару, чей первый элемент (который может быть извлечен car
) является "a"
, а второй элемент (который может быть извлечен cdr
) равен 4
.
(car (cons "a" 4))
;;=> "a"
(cdr (cons "a" 4))
;;=> 3
Символьные ячейки могут быть напечатаны в виде точечной пары :
(cons 1 2)
;;=> (1 . 2)
Консервные ячейки также могут быть прочитаны в виде точечных парных обозначений, так что
(car '(x . 5))
;;=> x
(cdr '(x . 5))
;;=> 5
(Печатная форма cons-ячеек также может быть немного сложнее. Подробнее об этом см. В примере о cons-ячейках в виде списков.)
Это оно; cons cells - это только пары элементов, созданных функцией cons
, и элементы могут быть извлечены car
и cdr
. Из-за их простоты ячейки cons могут быть полезным строительным блоком для более сложных структур данных.
Эскизные экраны
Для лучшего понимания семантики conses и списков часто используется графическое представление таких структур. Ячейка cons обычно представлена двумя контактами, содержащими две стрелки, указывающие на значения car
и cdr
, или непосредственно значения. Например, результат:
(cons 1 2)
;; -> (1 . 2)
могут быть представлены одним из этих чертежей:
Обратите внимание, что эти представления являются чисто концептуальными и не означают, что значения содержатся в ячейке или указываются из ячейки: в общем, это зависит от реализации, типа значений, уровня оптимизации и т. Д. . В остальной части примера мы будем использовать первый вид чертежа, который является наиболее часто используемым.
Так, например:
(cons 1 (cons 2 (cons 3 4))) ; improper “dotted” list
;; -> (1 2 3 . 4)
представлен как:
в то время как:
(cons 1 (cons 2 (cons 3 (cons 4 nil)))) ;; proper list, equivalent to: (list 1 2 3 4)
;; -> (1 2 3 4)
представлен как:
Вот древовидная структура:
(cons (cons 1 2) (cons 3 4))
;; -> ((1 . 2) 3 . 4) ; note the printing as an improper list
В последнем примере показано, как это обозначение может помочь нам понять важные семантические аспекты языка. Во-первых, мы пишем выражение, подобное предыдущему:
(cons (cons 1 2) (cons 1 2))
;; -> ((1 . 2) 1 . 2)
которые могут быть представлены обычным образом:
Затем мы пишем другое выражение, которое, по-видимому, эквивалентно предыдущему, и это подтверждается печатным представлением результата:
(let ((cell-a (cons 1 2)))
(cons cell-a cell-a))
;; -> ((1 . 2) 1 . 2)
Но, если мы рисуем диаграмму, мы можем видеть, что семантика выражения различна, поскольку cell-a
та же ячейка является значением как части car
части cdr
внешних cons
(это - cell-a
является общей ) :
и тот факт, что семантика двух результатов на самом деле отличается на уровне языка, может быть проверена следующими тестами:
(let ((c1 (cons (cons 1 2) (cons 1 2)))
(c2 (let ((cell-a (cons 1 2)))
(cons cell-a cell-a))))
(list (eq (car c1) (cdr c1))
(eq (car c2) (cdr c2)))
;; -> (NIL T)
Первый eq
является ложным, так как car
и cdr
c1
структурно равны (это верно equal
), но не являются «идентичными» (т. Е. «Одна и та же общая структура»), а во втором тесте результат верен, поскольку car
и cdr
c2
идентичны , то есть они имеют одинаковую структуру .