Русская Википедия:Cons
В программировании cons (/ ˈkɒnz / или / ˈkɒns /) является фундаментальной функцией в большинстве диалектов языка программирования Лисп. cons создает объекты памяти, которые содержат два значения или два указателя на значения[1]. Название функции было образовано как сокращение от слова construct, то есть конструирование. Имелось ввиду, что cons конструирует в памяти новый объект из имеющихся двух. Эти объекты также называют cons-ячейками, cons-ами, неатомарными S-выражениями («NATS») или cons-парами. В английском языке, в жаргоне ЛИСП-программистов, слово cons используется также в качестве глагола. Выражение «to cons x onto y» равнозначно «сконструировать новый объект при помощи следующего кода: (cons x y)».
Среди пользователей функциональных языков программирования и в контексте работы со списками, «cons» также используется как жаргонное наименование аналогичных по назначению операторов аналогичного назначения, которые записываются совершенно по-другому. Хорошими примерами являются операторы :: в языках ML, Scala, F# и Elm или оператор : в языке Haskell, которые добавляют элемент в голову списка.
Использование
Хотя cons-ячейки могут использоваться для того, чтобы хранить упорядоченные пары данных, они чаще используются для построения более сложных составных структур данных, в частности списков и двоичных деревьев.
Упорядоченные пары
Например, выражение Лиспа (cons 1 2) конструирует ячейку, содержащую 1 в своей левой половине (так называемое поле car) и 2 в правой половине (поле cdr). В нотации Лиспа значение (cons 1 2) выглядит так:
(1. 2)
Обратите внимание на точку между 1 и 2; это указывает на то, что S-выражение является «точечной парой» (так называемая «cons-пара»), а не «списком».
Списки
(cons 42 (cons 69 (cons 613 nil)))
(list 42 69 613)
В Лиспе списки реализованы поверх cons-пар. Конкретнее, структура любого списка в Лиспе выглядит следующим образом:
- Пустой список, обозначаемый как (), является специальным объектом. Его также обычно называют nil.
- Список из одного элемента представляет собой cons-пару, в первой ячейке которой присутствует его единственный элемент, а вторая ссылается на nil.
- Список из двух и более элементов представляет собой cons-пару, первый элемент которой является первым элементом списка, а вторая ссылается на список, являющийся хвостом основного списка.
Показанное представление является простейшей формой однонаправленного списка, с содержимым которого легко манипулировать при помощи команд cons, car, cdr. Например, представим список с элементами 1, 2 и 3. Такой список может быть создан в три шага:
Cons (3 nil) Cons (2 результат предыдущей операции) Cons (1 результат предыдцщей операции)
или то же самое, одним выражением:
(cons 1 (cons 2 (cons 3 nil)))
та же последовательность операций cons представляется сокращённо:
(list 1 2 3)
в результате мы создаем список:
(1 . (2 . (3 . nil)))
со следующей структурой:
*--*--*--nil | | | 1 2 3
сокращённо он может быть записан следующим образом:
(1 2 3)
Исходя из вышенаписанного, cons можно использовать для добавления нового элемента в начало существующего связанного списка. Например, если x — это список, который мы определили выше, то (cons 5 x) создаст список:
(5 1 2 3)
Деревья
Бинарные деревья, которые хранят данные только в своих листьях, также легко реализуются при помощи 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-ячейки, могут быть реализованы с использованием функций. Пример на языке Scheme:
(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, Шаблон:Iw и Шаблон:Iw с использованием «cons-ячеек». Кодирование Чёрча — это обычный способ определения структур данных в чистом лямбда-исчислении.
Такая реализация, хотя и интересна с академической точки зрения, непрактична, поскольку она делает cons-ячейки неотличимыми от любой другой процедуры языка Scheme, а также вносит ненужную вычислительную неэффективность. Впрочем, такой же подход может использоваться для более сложных алгебраических типов данных с вариантами. В этом случае, он, действительно, может оказаться более эффективным, чем другие способы представления данных в памяти[2].
См. также
Ссылки
- SDRAW, Код на Common Lisp, предназначенный для отрисовки структур данных, составленных из cons-ячеек. Автор — David S. Touretzky.
Примечания
