В программировании на компьютере ( cons/ ˈ k ɒ n z / или / ˈ k ɒ n s / ) является фундаментальной функцией в большинстве диалектов языка программирования Lisp . cons конструирует объекты памяти , которые содержат два значения или указатели на два значения. Эти объекты называются (cons) ячейками, cons, неатомарными s-выражениями («NATSes») или (cons) парами . На жаргоне Lisp выражение «to cons x into y » означает построить новый объект с помощью . Полученная пара имеет левую половину, называемую ( первый элемент или содержимое адресной части регистра ), и правую половину , называемую (второй элемент или содержимое декрементной части регистра ).(cons x y)carcdr
Он слабо связан с объектно-ориентированным понятием конструктора , который создает новый объект по заданным аргументам, и более тесно связан с функцией конструктора алгебраической системы типов данных .
Слово "cons" и выражения типа "to cons into" также являются частью более общего жаргона функционального программирования . Иногда операторы , имеющие схожее назначение, особенно в контексте обработки списков, произносятся как "cons". (Хорошим примером является ::оператор в ML , Scala , F# , Lean , Coq и Elm или :оператор в Haskell , который добавляет элемент в начало списка.)
Хотя cons-ячейки можно использовать для хранения упорядоченных пар данных, они чаще используются для построения более сложных составных структур данных, в частности списков и двоичных деревьев .
Например, выражение Lisp создает ячейку, содержащую 1 в левой половине (так называемое поле) и 2 в правой половине ( поле). В нотации Lisp значение выглядит так:(cons 1 2)carcdr(cons 1 2)
(1 . 2)
Обратите внимание на точку между 1 и 2; она указывает на то, что S-выражение представляет собой «точечную пару» (так называемую «пару минус»), а не «список».
cons:( минусы 42 ( минусы 69 ( минусы 613 ноль ))) list:( список 42 69 613 ) В Lisp списки реализованы поверх cons-пар. Более конкретно, любая структура списка в Lisp является либо:
(), представляющий собой специальный объект, обычно называемый nil.carявляется первым элементом списка и которая cdrявляется списком, содержащим остальные элементы.Это формирует основу простой, односвязной структуры списка, содержимое которой можно изменять с помощью cons, carи cdr. Обратите внимание nil, что это единственный список, который не является парой cons. В качестве примера рассмотрим список, элементами которого являются 1, 2 и 3. Такой список можно создать в три шага:
nil, пустой списокчто эквивалентно одному выражению:
( минусы 1 ( минусы 2 ( минусы 3 ноль ))) или его сокращение:
( список 1 2 3 ) Результирующее значение представляет собой список:
(1 . (2 . (3 . ноль)))
то есть
*--*--*--ноль | | | 1 2 3
что обычно сокращается до:
(1 2 3)
Таким образом, consможет использоваться для добавления одного элемента в начало существующего связанного списка. Например, если x — это список, который мы определили выше, то будет создан список:(cons 5 x)
(5 1 2 3)
Еще одна полезная процедура работы со списками — append , которая объединяет два существующих списка (т. е. объединяет два списка в один).
Бинарные деревья , которые хранят данные только в своих листьях , также легко строятся с помощью cons. Например, код:
( минусы ( минусы 1 2 ) ( минусы 3 4 )) Результаты в дереве:
((1 . 2) . (3 . 4))
то есть
* / \ * */ \ / \1 2 3 4
Технически, список (1 2 3) в предыдущем примере также является бинарным деревом, которое, как оказалось, особенно несбалансированно. Чтобы увидеть это, просто переставьте диаграмму:
*--*--*--ноль | | | 1 2 3
к следующему эквиваленту:
* / \ 1 * / \ 2 * / \ 3 ноль
Минусы могут относиться к общему процессу выделения памяти , в отличие от использования деструктивных операций, которые использовались бы в императивном языке программирования. [ требуется ссылка ] Например:
Я немного ускорил код, добавив побочные эффекты вместо того, чтобы делать его нелепо медленным.
Поскольку в Lisp есть функции первого класса , все структуры данных, включая cons-ячейки, могут быть реализованы с помощью функций. Например, в Scheme :
( определить ( cons x y ) ( lambda ( m ) ( m x y ))) ( определить ( car z ) ( z ( lambda ( p q ) p ))) ( определить ( cdr z ) ( z ( lambda ( p q ) q ))) Эта техника известна как кодирование Чёрча . Она повторно реализует операции cons , car и cdr , используя функцию в качестве «ячейки cons». Кодирование Чёрча — это обычный способ определения структур данных в чистом лямбда-исчислении , абстрактной теоретической модели вычислений, которая тесно связана со Scheme.
Такая реализация, хотя и интересна с академической точки зрения, непрактична, поскольку она делает cons-ячейки неотличимыми от любой другой процедуры Scheme, а также вносит ненужную вычислительную неэффективность.
Однако тот же тип кодирования может использоваться для более сложных алгебраических типов данных с вариантами, где он может оказаться даже более эффективным, чем другие виды кодирования. [1] Это кодирование также имеет то преимущество, что его можно реализовать в статически типизированном языке, не имеющем вариантов, таком как Java , с использованием интерфейсов вместо лямбда-выражений.