Молния (структура данных) - Википедия - Zipper (data structure)

А молния это техника представления совокупности структура данных так что это удобно для написания программ, которые произвольно пересекают структуру и обновляют ее содержимое, особенно в чисто функциональные языки программирования. Молния была описана Жерар Юэ в 1997 г.[1] Он включает и обобщает буфер промежутка техника, иногда используемая с массивами.

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

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

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

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

  • Пустой создает пустой список,
  • Минусы (x, L) создает список, добавляя или объединяя значение Икс перед списком L.

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

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

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

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

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

Тип контекстов застежки-молнии может быть сконструирован с помощью трансформация оригинального типа, который тесно связан с производная из исчисление через декатегоризация. Рекурсивные типы, из которых формируются молнии, можно рассматривать как наименьшая фиксированная точка конструктора унарного типа . Например, с конструктором типа высшего порядка который строит наименьшую фиксированную точку своего аргумента, непомеченное двоичное дерево может быть представлено как а немаркированный список может иметь вид . Здесь обозначения возведения в степень, умножения и сложения соответствуют типы функций, виды продукции, и типы сумм соответственно, в то время как натуральные числа обозначают конечные типы; в этом смысле конструкторы типов напоминают полиномиальные функции в .[2]

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

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

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

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

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

  • а логическое значение типа , выражая, является ли текущий узел левым или правым потомком своего родительского узла;
  • значение типа , метка родительского узла текущего узла; и
  • родственник узла типа , поддерево, содержащееся в другой ветви родительского элемента текущего узла.

В общем, молния под дерево вида состоит из двух частей: список контекстов типа текущего узла и каждого из его предков до корневого узла, а поддерево типа что текущий узел содержит.

Использует

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

Молния использовалась в

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

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

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

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

Обычная молния

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

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

Рекомендации

  1. ^ Huet 1997
  2. ^ Joyal, André (1981), «Une théorie combinatoire des séries formelles», Успехи в математике 42: 1–82.
  3. ^ Макбрайд, Конор (2001), «Производная регулярного типа - это его тип контекстов с одной дырой»
  4. ^ Хинце, Ральф; Jeuring, Йохан (2001). «Функциональная жемчужина: плетение паутины». Журнал функционального программирования. 11 (6): 681–689. Дои:10.1017 / S0956796801004129. ISSN  0956-7968.
  5. ^ Generic Zipper: контекст обхода
  6. ^ jafingerhut (22 октября 2010 г.). "clojure.zip/zipper". ClojureDocs. Получено 15 июн 2013.
  7. ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 1». Получено 29 августа 2011.
  8. ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 2». Получено 29 августа 2011.
  9. ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 3». Получено 29 августа 2011.

дальнейшее чтение

внешняя ссылка