Войти
В компьютерном программировании, cons(или ) является фундаментальной функцией в большинстве диалектов языка программирования Lisp. conscons обрабатывает объекты памяти, которые содержат два значения или указатели на значения. Эти объекты называются (cons) ячейками, conses, неатомарными s-выражениями («NATSes») или (cons) парами. На жаргоне Лиспа выражение «преобразовать x в y» означает создать новый объект с помощью (cons x y). Полученная пара имеет левую половину, называемую car (первый элемент или содержимое адресного регистра ), и правую половину (вторая элемент, или содержимое регистра декремента ), называемого cdr.
. Он слабо связан с объектно-ориентированным понятием конструктор, который создает новый объект с заданными аргументами и более тесно связан с функцией конструктора системы алгебраического типа данных.
Слово «против» и выражения типа «против» также являются частью более общего жаргона функционального программирования. Иногда операторы , имеющие аналогичное назначение, особенно в контексте обработки списков, произносятся как «минусы». (Хорошим примером является оператор ::в 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:
(list 42 69 613)
В Лиспе списки реализованы поверх пар cons. В частности, любая структура списка в Лиспе:
(), который представляет собой специальный объект, обычно называемый nil.carявляется первым элементом списка, а cdrкоторого является списком, содержащим остальные элементы.Это формирует основу простой структуры односвязного списка, содержимое которой можно манипулировать с помощью cons, carи cdr. Обратите внимание, что nil- единственный список, который также не является парой минусов. В качестве примера рассмотрим список с элементами 1, 2 и 3. Такой список можно создать в три этапа:
nil, пустой список, что эквивалентно единственному выражению:
(cons 1 (cons 1 (cons 3 nil)))
или его сокращению:
(список 1 2 3)
Результирующим значением является список:
(1. (2. (3. Nil)))
т.е.
* - * - * - ноль | | | 1 2 3
, который обычно сокращается как:
(1 2 3)
Таким образом, consможно использовать для добавления одного элемента в перед существующим связанным списком. Например, если x - это список, который мы определили выше, то (cons 5 x)создаст список:
(5 1 2 3)
Другой полезный список процедура append, которая объединяет два существующих списка (т. е. объединяет два списка в один).
Бинарные деревья, которые хранят данные только в своих листьях, также легко создаются с помощью cons. Например, код:
(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 имеет first- class functions, все структуры данных, включая cons-ячейки, могут быть реализованы с помощью функций. Например, в схеме Схема :
(define (cons xy) (lambda (m) (mxy))) (define (car z) (z (lambda (pq) p))) (define (cdr z) (z (lambda (pq) q)))
Этот метод известен как кодирование Чёрча. Он повторно реализует операции cons, car и cdr, используя функцию как «cons-ячейку». Кодирование Чёрча - это обычный способ определения структур данных в чистом лямбда-исчислении, абстрактной теоретической модели вычислений, которая тесно связана со Scheme.
Эта реализация, хотя и интересна с академической точки зрения, непрактична, потому что она делает cons-ячейки неотличимыми от любой другой процедуры схемы, а также вносит ненужную вычислительную неэффективность.
Однако тот же тип кодирования может использоваться для более сложных алгебраических типов данных с вариантами, где он может даже оказаться более эффективным, чем другие виды кодирования. Эта кодировка также имеет то преимущество, что ее можно реализовать на языке со статической типизацией, который не имеет вариантов, таких как Java, с использованием интерфейсов вместо лямбда-выражений.
