Cons

В программировании cons (/ ˈkɒnz / или / ˈkɒns /) является фундаментальной функцией в большинстве диалектов языка программирования Лисп. cons создает объекты памяти, которые содержат два значения или два указателя на значения. Название функции было образовано как сокращение от слова construct, то есть конструирование. Имелось ввиду, что cons конструирует в памяти новый объект из имеющихся двух. Эти объекты также называют cons-ячейками, cons-ами, неатомарными S-выражениями («NATS») или cons-парами. В английском языке, в жаргоне ЛИСП-программистов, слово cons используется также в качестве глагола. Выражение «to cons x onto y» равнозначно «сконструировать новый объект при помощи следующего кода: (cons x y)».

Среди пользователей функциональных языков программирования и в контексте работы со списками, «cons» также используется как жаргонное наименование аналогичных по назначению операторов аналогичного назначения, которые записываются совершенно по-другому. Хорошими примерами являются операторы :: в языках ML, Scala, F# и Elm или оператор : в языке Haskell, которые добавляют элемент в голову списка.

Использование

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

Упорядоченные пары

Например, выражение Лиспа (cons 1 2) конструирует ячейку, содержащую 1 в своей левой половине (так называемое поле car) и 2 в правой половине (поле cdr). В нотации Лиспа значение (cons 1 2) выглядит так:

(1. 2)

Обратите внимание на точку между 1 и 2; это указывает на то, что S-выражение является «точечной парой» (так называемая «cons-пара»), а не «списком».

Списки

диаграмма cons-ячеек для списка (42 69 613), созданного при помощи функции cons:

(cons 42 (cons 69 (cons 613 nil)))

или записанного как список:

(list 42 69 613)

В Лиспе списки реализованы поверх cons-пар. Конкретнее, структура любого списка в Лиспе выглядит следующим образом:

1. Пустой список, обозначаемый как (), является специальным объектом. Его также обычно называют nil.
2. Список из одного элемента представляет собой cons-пару, в первой ячейке которой присутствует его единственный элемент, а вторая ссылается на nil.
3. Список из двух и более элементов представляет собой cons-пару, первый элемент которой является первым элементом списка, а вторая ссылается на список, являющийся хвостом основного списка.

Показанное представление является простейшей формой однонаправленного списка, с содержимым которого легко манипулировать при помощи команд cons, car, cdr. Например, представим список с элементами 1, 2 и 3. Такой список может быть создан в три шага:

   Cons (3 nil)    
   Cons (2 результат предыдущей операции)
   Cons (1 результат предыдцщей операции)

или то же самое, одним выражением:

(cons 1 (cons 2 (cons 3 nil)))

та же последовательность операций cons представляется сокращённо:

(list 1 2 3)

в результате мы создаем список:

(1 . (2 . (3 . nil)))

со следующей структурой:

 *--*--*--nil
 |  |  |
 1  2  3

сокращённо он может быть записан следующим образом:

(1 2 3)

Исходя из вышенаписанного, cons можно использовать для добавления нового элемента в начало существующего связанного списка. Например, если x — это список, который мы определили выше, то (cons 5 x) создаст список:

(5 1 2 3)

Деревья

Бинарные деревья, которые хранят данные только в своих листьях, также легко реализуются при помощи cons. Пример:

(cons (cons 1 2) (cons 3 4))

создаёт представление дерева в виде списка:

((1 . 2) . (3 . 4))

то есть

   *
  / \
 *   *
/ \ / \
1 2 3 4

Технически список (1 2 3) в предыдущем примере также является несбалансированным двоичным деревом. Чтобы убедиться в этом, просто перерисуем диаграмму

 *--*--*--nil
 |  |  |
 1  2  3

в эквивалентную:

   *
  / \
 1   *
    / \
   2   *
      / \
     3  nil

Функциональная реализация

Поскольку Lisp включает функции первого класса, все структуры данных, включая cons-ячейки, могут быть реализованы с использованием функций. Пример на языке Scheme:

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))
(define (cdr z)
  (z (lambda (p q) q)))

Эта техника известна как «кодирование Чёрча». Она позволяет переопределить реализацию операций cons, car и cdr с использованием «cons-ячеек». Кодирование Чёрча — это обычный способ определения структур данных в чистом лямбда-исчислении.

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

См. также

• Лисп
• CAR и CDR
• Конструктор
• Алгебраический тип данных
• Hash consing

Ссылки

• SDRAW, Код на Common Lisp, предназначенный для отрисовки структур данных, составленных из cons-ячеек. Автор — David S. Touretzky.