PROFILPELAJAR.COM

В программировании 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-ячеек для списка (42 69 613), созданного при помощи функции `cons`:
(cons 42 (cons 69 (cons 613 nil)))
или записанного как `список`:
(list 42 69 613)

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

Пустой список, обозначаемый как (), является специальным объектом. Его также обычно называют nil.
Список из одного элемента представляет собой cons-пару, в первой ячейке которой присутствует его единственный элемент, а вторая ссылается на nil.
Список из двух и более элементов представляет собой 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, а также вносит ненужную вычислительную неэффективность. Впрочем, такой же подход может использоваться для более сложных алгебраических типов данных с вариантами. В этом случае, он, действительно, может оказаться более эффективным, чем другие способы представления данных в памяти^[2].

См. также

Примечания

↑ Е.И.Большакова, Н. В.Груздева. Основы программирования на языке Лисп. — Москва: Издательский отдел факультета ВМК МГУ имени М.В.Ломоносова; МАКС Пресс, 2010, 2010.
↑ Archived copy (неопр.). Дата обращения: 1 марта 2009. Архивировано из оригинала 31 марта 2010 года.