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