Застежка-молния (структура данных)

редактировать

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

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

Обычный человек объяснил бы дерево с застежкой-молнией обычной компьютерной файловой системой с операциями перехода к родительскому объекту (часто cd..) и возможностью перехода вниз (cd подкаталог). Застежка-молния - это указатель на текущий путь. Незаметно застежки-молнии эффективны при внесении (функциональных) изменений в структуру данных, когда новая, слегка измененная структура данных возвращается из операции редактирования (вместо того, чтобы вносить изменения в текущую структуру данных).

Содержание

1 Пример: двунаправленный обход списка
2 Контексты и дифференциация
3 Использование
4 Альтернативы и расширения
- 4.1 Прямая модификация
- 4.2 Универсальная застежка-молния
5 Ссылки
6 Дополнительная литература
7 Внешние ссылки

Пример: двунаправленный обход списка

Многие общие структуры данных в информатике могут быть выражены как структура, генерируемая несколькими примитивами или. Сюда входит структура конечных списков, которые могут быть сгенерированы двумя операциями:

Emptyсоздает пустой список,
Cons (x, L)создает список, добавляя или объединяя значение xперед списком L.

Список, такой как [1, 2, 3], поэтому является объявлением Cons (1, Cons (2, Cons (3, Empty)))). Можно описать местоположение в таком списке, как количество шагов от начала списка до целевого местоположения. Более формально, место в списке - это количество операций Cons, необходимых для восстановления всего списка из этого конкретного места. Например, в Минусы (1, Минусы (2, Минусы (X, 4, Пусто))))a Минусы (2, L)и Минусы (1, L) операцияпотребуется для восстановления списка относительно позиции X, иначе известной как Cons (X, Cons (4, Empty)). Эта запись вместе с местоположением называется заархивированным представлением списка или застежкой-молнией списка.

Для ясности: место в списке - это не только количество операций Минусы, но и вся другая информация об этих Минусах; в этом случае значения, которые необходимо повторно подключить. Здесь эти значения могут быть удобно представлены в отдельном списке в порядке приложения от целевого местоположения. В частности, из контекста «3» в списке [1, 2, 3, 4]запись (обычно называемая «путем») может быть представлена как [2, 1], где применяется Cons (2, L), за которым следует (Cons 1, L)для восстановления исходного списка, начиная с [X, 4].

Застежка-молния всегда представляет всю структуру данных. Однако эта информация дана с точки зрения конкретного места в этой структуре данных. Следовательно, застежка-молния со списком - это пара, состоящая из местоположения как контекста или начальной точки и записи или пути, который позволяет реконструировать из этого начального местоположения. В частности, застежка-молния списка [1, 2, 3, 4]в позиции "3" может быть представлена как ([2, 1], [3, 4]). Теперь, если "3" изменить на "10", то застежка-молния списка станет ([2, 1], [10, 4]). После этого список может быть эффективно реконструирован: [1, 2, 10, 4]или другие местоположения, к которым был осуществлен переход.

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

Контексты и дифференциация

Тип контекстов застежки-молнии может быть сконструирован с помощью преобразования исходного типа, который тесно связан с производным от исчисления до декатегоризации. Рекурсивные типы, из которых формируются застежки-молнии, можно рассматривать как наименьшую фиксированную точку конструктора унарного типа вида $∗ → ∗ {\ displaystyle * \ rightarrow *}$ $* \ rightarrow *$ . Например, с конструктором типа высшего порядка $lfp: (∗ → ∗) → ∗ {\ displaystyle lfp: (* \ rightarrow *) \ rightarrow *}$ ${\ displaystyle lfp: (* \ rightarrow *) \ rightarrow *}$ , который строит наименьшую фиксированную точку его аргумент немаркированное двоичное дерево может быть представлено как $lfp (T ↦ T 2 + 1) {\ displaystyle lfp (T \ mapsto T ^ {2} +1)}$ ${\ displaystyle lfp (T \ mapsto T ^ {2} +1)}$ и немаркированный список может принимать форму $lfp (T ↦ T + 1) {\ displaystyle lfp (T \ mapsto T + 1)}$ ${\ displaystyle lfp (T \ mapsto T + 1)}$ . Здесь обозначения возведения в степень, умножения и сложения соответствуют типам функций, типам продуктов и типам суммы соответственно, в то время как натуральные числа обозначают конечные типы ; Таким образом, конструкторы типов напоминают полиномиальные функции в $N → N {\ displaystyle \ mathbb {N} \ rightarrow \ mathbb {N}}$ ${\ displaystyle \ mathbb {N} \ rightarrow \ mathbb {N}}$ .

Таким образом, производная конструктора типа может быть образована с помощью этой синтаксической аналогии : для примера троичного дерева без метки производная от его конструктора типа $(T ↦ T 3 + 1) ′ {\ displaystyle (T \ mapsto T ^ {3} +1) '}$ $(T\mapsto T^{3}+1)'$ будет эквивалентно $T ↦ 3 × T 2 {\ displaystyle T \ mapsto 3 \ times T ^ {2}}$ ${\ displaystyle T \ mapsto 3 \ times T ^ {2}}$ , аналогично использованию суммы и power правила дифференциального исчисления. Тип контекстов застежки-молнии над исходным типом $lfp (f) {\ displaystyle lfp (f)}$ ${\ displaystyle lfp ( е)}$ эквивалентен производному конструктора типа, примененного к исходному типу, $f ′ (lfp (f)) {\ displaystyle f '(lfp (f))}$ $f'(lfp(f))$ .

Для иллюстрации рассмотрим рекурсивную структуру данных двоичного дерева с узлами, которые являются либо контрольными узлами из введите $1 {\ displaystyle 1}$ $1$ или содержат значение типа $A {\ displaystyle A}$ $A$ :

BT ree: = lfp (T ↦ A × T 2 + 1) { \ displaystyle BTree: = lfp (T \ mapsto A \ times T ^ {2} +1)}

{\ displaystyle BTree: = lfp (T \ mapsto A \ times T ^ {2} +1)}

Производная конструктора типа может быть вычислена как

(T ↦ A × T 2 + 1) ′ = T ↦ 2 × A × T {\ displaystyle (T \ mapsto A \ times T ^ {2} +1) '= T \ mapsto 2 \ times A \ times T}

(T\mapsto A\times T^{2}+1)'=T\mapsto 2\times A\times T

Таким образом, тип контекстов застежки-молнии является

(T ↦ 2 × A × T) (BT ree) = 2 × A × BT ree {\ displaystyle (T \ mapsto 2 \ times A \ times T) (BTree) = 2 \ times A \ times BTree }

{\ displaystyle (T \ mapsto 2 \ times A \ times T) (BTree) = 2 \ times A \ times BTree}

Таким образом, мы обнаруживаем, что контекст каждого дочернего узла, не являющегося дозорным, в метке ведомое двоичное дерево представляет собой тройку, состоящую из

a логического значения типа $2 {\ displaystyle 2}$ $2$ , выражающего, является ли текущий узел левым или правым дочерним элементом своего родительского узла;
значение типа $A {\ displaystyle A}$ $A$ , метка родительского элемента текущего узла; и
родственный элемент узла типа $BT ree {\ displaystyle BTree}$ ${\ displaystyle BTree }$ , поддерево, содержащееся в другой ветви родительского элемента текущего узла.

В общем, застежка-молния для дерева типа $lfp (f) {\ displaystyle lfp (f)}$ ${\ displaystyle lfp ( е)}$ состоит из двух частей: списка контекстов типа $f '(lfp (f)) {\ displaystyle f '(lfp (f))}$ $f'(lfp(f))$ текущего узла и каждого из его предков до корневого узла и поддерево типа $lfp (f) {\ displaystyle lfp (f) }$ ${\ displaystyle lfp ( е)}$ , который содержит текущий узел.

Использует

Застежка-молния часто используется там, где есть некоторая концепция фокуса или перемещения в некотором наборе данных, поскольку ее семантика отражает семантику перемещения, но функциональным неразрушающим способом.

Застежка-молния использовалась в

Xmonad для управления фокусом и размещением окон
Документы Хуэта покрывают a на основе застежек-молний и средства доказательства теорем
A файловая система (ZipperFS), написанная на Haskell, предлагающая "... транзакционную семантику; отмена любой операции с файлом и каталогом; моментальные снимки; статически гарантированный самый надежный, повторяемый режим чтения, изоляции для клиентов; повсеместное копирование- при записи для файлов и каталогов; встроенные средства обхода; и правильное поведение для циклических ссылок на каталоги. "
Clojure имеет обширную поддержку застежек-молний.

Альтернативы и расширения

Прямая модификация

В языке программирования, не являющемся чисто функциональным, может быть удобнее просто пройти по исходной структуре данных и изменить ее напрямую (возможно, после глубокого клонирования, чтобы не повлиять на другой код, который может содержать ссылку на него).

Универсальная застежка-молния

Универсальная застежка-молния - это метод достижения той же цели, что и обычная застежка-молния, путем фиксации состояния обхода в продолжении при посещении каждого узла. (Код Haskell, приведенный в справочнике, использует универсальное программирование для генерации функции обхода для любой структуры данных, но это необязательно - может использоваться любая подходящая функция обхода.)

Однако Generic Zipper включает в себя инверсию элемента управления, поэтому для некоторых его применений требуется конечный автомат (или эквивалент), чтобы отслеживать, что делать дальше.

Ссылки

Дополнительная литература

Huet, Gerard (сентябрь 1997 г.). «Функциональная жемчужина: молния» (PDF). Журнал функционального программирования. 7 (5): 549–554. doi : 10.1017 / s0956796897002864. CS1 maint: ref = harv (link )
Hinze, Ralf, et al. «Данные с указанием типа types ". 23 июля 2003 г.

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

В Wikibook Haskell есть страница по теме: Застежки-молнии