Cons

В программировании cons (/ ˈkɒnz / или / ˈkɒns /) является фундаментальной функцией в большинстве диалектов языка программирования Лисп. cons создает объекты памяти, которые содержат два значения или два указателя на значения^[1]. Название функции было образовано как сокращение от слова 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-пар. Конкретнее, структура любого списка в Лиспе выглядит следующим образом:

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^[en] и cdr^[en] с использованием «cons-ячеек». Кодирование Чёрча — это обычный способ определения структур данных в чистом лямбда-исчислении.

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

См. также

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

Примечания

Ссылки

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

Эта страница в последний раз была отредактирована 30 октября 2023 в 05:59.