минусы

Эта статья о функции программирования на Лиспе. Чтобы узнать о других значениях, см. «Минусы» (значения) .

В компьютерном программировании , cons ( / ˈ k ɒ n z / или / ˈ k ɒ n s / ) — фундаментальная функция в большинстве диалектов языка программирования Lisp . cons const создает объекты памяти, которые содержат два значения или указатели на два значения. Эти объекты называются (cons) ячейками, conses, неатомарными s-выражениями («NATS») или парами (cons) . На жаргоне Лиспа выражение «сконструировать x на y » означает создание нового объекта с помощью (cons x y). Получившаяся пара имеет левую половину, называемую car (первый элемент или содержимое адресной части регистра ) и правую половину , называемую cdr (второй элемент содержимое декрементной части регистра ) или .

Оно слабо связано с объектно-ориентированным понятием конструктора , который создает новый объект с заданными аргументами, и более тесно связано с функцией-конструктором системы алгебраических типов данных .

Слово «минусы» и такие выражения, как «to cons on», также являются частью более общего жаргона функционального программирования . Иногда операторы , преследующие аналогичную цель, особенно в контексте обработки списков, называются «минусами». (Хорошим примером является :: оператор в ML , Scala , F# , Lean , Coq и Elm или : оператор в Haskell , который добавляет элемент в начало списка.)

Использовать

Хотя cons-ячейки можно использовать для хранения упорядоченных пар данных, они чаще используются для создания более сложных составных структур данных, особенно списков и двоичных деревьев .

Заказанные пары

Например, выражение Лиспа (cons 1 2) строит ячейку, содержащую 1 в левой половине (так называемая car поле) и 2 в его правой половине ( cdr поле). В нотации Лиспа значение (cons 1 2) выглядит так:

(1 . 2)

Обратите внимание на точку между 1 и 2; это указывает на то, что S-выражение представляет собой «пунктирную пару» (так называемую «пару минусов»), а не «список».

Списки

Диаграмма ячеек минусов для списка (42 69 613), написанная с помощью cons:

(cons 42 (cons 69 (cons 613 nil)))

и написано с list:

(list 42 69 613)

В Лиспе списки реализуются поверх пар cons. Более конкретно, любая структура списка в Lisp является либо:

1. Пустой список (), который представляет собой специальный объект, обычно называемый nil.
2. Ячейка минусов, чья car является первым элементом списка и чей cdr представляет собой список, содержащий остальные элементы.

Это формирует основу простой структуры односвязного списка , содержимым которого можно манипулировать с помощью cons, car, и cdr. Обратите внимание, что nil это единственный список, который не является парой минусов. В качестве примера рассмотрим список, элементами которого являются 1, 2 и 3. Такой список можно создать в три этапа:

1. Минусы 3 на nil, пустой список
2. Минусы 2 на результат
3. Минусы 1 на результат

что эквивалентно одному выражению:

(cons 1 (cons 2 (cons 3 nil)))

или его сокращение:

(list 1 2 3)

Полученное значение представляет собой список:

(1 . (2 . (3 . nil)))

то есть

 *--*--*--nil
 |  |  |
 1  2  3

который обычно сокращается как:

(1 2 3)

Таким образом, cons может использоваться для добавления одного элемента в начало существующего связанного списка. Например, если x — это список, который мы определили выше, то (cons 5 x) выдаст список:

(5 1 2 3)

Еще одна полезная процедура создания списка — add , которая объединяет два существующих списка (т. е. объединяет два списка в один).

Деревья

Двоичные деревья , которые хранят данные только в своих листьях , также легко построить с помощью 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-ячейки, могут быть реализованы с помощью функций. Например, в схеме :

(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». Кодирование Чёрча — это обычный способ определения структур данных в чистом лямбда-исчислении , абстрактной теоретической модели вычислений, тесно связанной со Scheme.

Эта реализация, хотя и интересна с академической точки зрения, непрактична, поскольку она делает cons-ячейки неотличимыми от любой другой процедуры Scheme, а также вносит ненужную вычислительную неэффективность.

Однако тот же тип кодирования можно использовать для более сложных алгебраических типов данных с вариантами, где он может даже оказаться более эффективным, чем другие виды кодирования. Эта кодировка также имеет то преимущество, что ее можно реализовать на статически типизированном языке, не имеющем вариантов, например Java , использующем интерфейсы вместо лямбда-выражений.

См. также

• Лисп (язык программирования)
• АВТОМОБИЛЬ и CDR
• Конструктор (информатика)
• Алгебраический тип данных
• Хеширование

Внешние ссылки

• SDRAW , код Common Lisp для рисования структур ячеек cons. От Дэвида С. Турецкого.