В компьютерном программировании , cons
( / к ɒ п Z / или / к ɒ н ы / ) является одним из основной функции в большинстве диалектов языка программирования Lisp . cons
Минусы tructs объекты памяти , которые держат два значения или указатели на значения. Эти объекты называются (cons) ячейками, conses, неатомарными s-выражениями ("NATSes") или (cons) парами . На жаргоне Лиспа выражение «преобразовать x в y » означает создать новый объект с(cons x y)
. Результирующая пара имеет левую половину, называемую car
(первый элемент или содержимое адресной части регистра ), и правую половину (второй элемент или содержимое декрементной части регистра ), называемую cdr
.
Это слабо связано с объектно-ориентированным понятием конструктора , который создает новый объект с заданными аргументами, и более тесно связано с функцией конструктора системы алгебраических типов данных.
Слово «против» и выражения типа «против» также являются частью более общего жаргона функционального программирования . Иногда операторы, которые имеют аналогичное назначение, особенно в контексте обработки списков, произносятся как «минусы». (Хорошим примером является оператор :: в ML , Scala , F # и Elm или оператор : в Haskell , который добавляет элемент в начало списка.)
Использовать
Хотя cons-ячейки могут использоваться для хранения упорядоченных пар данных, они чаще используются для создания более сложных составных структур данных, особенно списков и двоичных деревьев .
Заказанные пары
Например, выражение Лиспа конструирует ячейку, содержащую 1 в своей левой половине (так называемое поле) и 2 в правой половине ( поле). В нотации Лиспа значение выглядит так:(cons 1 2)
car
cdr
(cons 1 2)
(1,2)
Обратите внимание на точку между 1 и 2; это указывает на то, что S-выражение является «пунктирной парой» (так называемая «cons-пара»), а не «списком».
Списки
В Лиспе списки реализованы поверх пар минусов. В частности, любая структура списка в Лиспе:
- Пустой список
()
, который обычно называется специальным объектомnil
. - Консольная ячейка, которая
car
является первым элементом списка иcdr
является списком, содержащим остальные элементы.
Это формирует основу простой, односвязный список структуру, содержимое которой можно манипулировать с cons
, car
и cdr
. Обратите внимание, что nil
это единственный список, который также не является парой минусов. В качестве примера рассмотрим список, элементы которого - 1, 2 и 3. Такой список можно создать в три этапа:
- Минусы 3
nil
, пустой список - Минусы 2 на результат
- Минусы 1 на результат
что эквивалентно единственному выражению:
( минусы 1 ( минусы 2 ( минусы 3 ноль )))
или его сокращение:
( список 1 2 3 )
В результате получается список:
(1. (2. (3. Nil)))
т.е.
* - * - * - ноль | | | 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 ноль
Используйте в разговоре
Минусы могут относиться к общему процессу выделения памяти , в отличие от использования деструктивных операций того типа, который использовался бы в императивном языке программирования. Например:
Я немного ускорил код, добавив побочные эффекты вместо смехотворных ошибок.
Функциональная реализация
Поскольку в Лиспе есть первоклассные функции , все структуры данных, включая cons-ячейки, могут быть реализованы с помощью функций. Например, на схеме :
( define ( cons x y ) ( lambda ( m ) ( m x y ))) ( define ( car z ) ( z ( lambda ( p q ) p ))) ( define ( cdr z ) ( z ( lambda ( p q) ) д )))
Этот метод известен как кодирование Чёрча . Он повторно реализует операции cons , car и cdr , используя функцию в качестве «cons-ячейки». Кодирование Чёрча - это обычный способ определения структур данных в чистом лямбда-исчислении , абстрактная теоретическая модель вычислений, которая тесно связана со схемой.
Эта реализация, хотя и интересна с академической точки зрения, непрактична, поскольку делает cons-ячейки неотличимыми от любой другой процедуры схемы, а также вносит ненужную вычислительную неэффективность.
Однако тот же тип кодирования может использоваться для более сложных алгебраических типов данных с вариантами, где он может даже оказаться более эффективным, чем другие виды кодирования. [1] Эта кодировка также имеет то преимущество, что ее можно реализовать на языке со статической типизацией, который не имеет вариантов, таких как Java , с использованием интерфейсов вместо лямбда-выражений.
Смотрите также
Рекомендации
- ^ «Архивная копия» (PDF) . Архивировано из оригинального (PDF) 31 марта 2010 года . Проверено 1 марта 2009 .CS1 maint: заархивированная копия как заголовок ( ссылка )
Внешние ссылки
- SDRAW , код Common Lisp для рисования структур cons-ячеек. От Дэвида С. Турецки.