Молния представляет собой метод , представляющие собой совокупную структуру данных , так что удобно для написания программ , которые пересекают структуру произвольно и обновлять его содержание, особенно в чисто функциональных языках программирования . Застежка-молния была описана Жераром Хюэ в 1997 году. [1] Она включает и обобщает технику буфера промежутков , иногда используемую с массивами.
Техника застежки-молнии является общей в том смысле, что ее можно адаптировать к спискам , деревьям и другим рекурсивно определяемым структурам данных. Такие модифицированные структуры данных обычно упоминаются как «дерево с застежкой-молнией» или «список с застежкой-молнией», чтобы подчеркнуть, что структура концептуально является деревом или списком, в то время как застежка-молния является деталью реализации.
Непрофессионал объяснил бы дерево с застежкой-молнией обычной компьютерной файловой системой с операциями перехода к родительскому объекту (часто cd ..
) и возможностью перехода вниз ( cd subdirectory
). Застежка-молния - это указатель на текущий путь. Незаметно застежки-молнии эффективны при внесении (функциональных) изменений в структуру данных, когда новая, слегка измененная структура данных возвращается из операции редактирования (вместо внесения изменений в текущую структуру данных).
Пример: двунаправленный обход списка
Многие общие структуры данных в информатике могут быть выражены как структура, созданная несколькими примитивными операциями конструктора или операциями наблюдателя . К ним относятся структуры конечных списков, которые можно сгенерировать двумя операциями:
Empty
создает пустой список,Cons(x, L)
создает список, добавляя или объединяя значениеx
перед спискомL
.
Список, такой как [1, 2, 3]
поэтому декларация Cons(1, Cons(2, Cons(3, Empty)))
. В таком списке можно описать местоположение как количество шагов от начала списка до целевого местоположения. Более формально место в списке - это количество Cons
операций, необходимых для восстановления всего списка из этого конкретного места. Например, в Cons(1, Cons(2, Cons( X, Cons(4, Empty))))
a Cons(2, L)
и Cons(1, L)
потребуется операция для восстановления списка относительно позиции X, иначе известной как Cons( X, Cons(4, Empty))
. Эта запись вместе с местоположением называется заархивированным представлением списка или застежкой-молнией списка.
Чтобы было ясно, место в списке - это не только количество Cons
операций, но и вся другая информация о них Cons
; в этом случае значения, которые необходимо переподключить. Здесь эти значения могут быть удобно представлены в отдельном списке в порядке приложения от целевого местоположения. В частности, из контекста «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]
или другие местоположения, в которые можно перейти.
При таком представлении списка легко определять относительно эффективные операции с неизменяемыми структурами данных, такими как списки и деревья, в произвольных местах. В частности, применение преобразования застежки-молнии к дереву позволяет легко вставлять или удалять значения в любом конкретном месте дерева.
Контексты и дифференциация
Тип контекстов застежки - молнии могут быть построены с помощью преобразования исходного типа , который тесно связан с производной от исчисления через decategorification . Рекурсивные типы, из которых формируются застежки-молнии, можно рассматривать как наименее фиксированную точку конструктора унарного типа типа. Например, с конструктором типа высшего порядка который строит наименьшую фиксированную точку своего аргумента, немаркированное двоичное дерево может быть представлено как а немаркированный список может иметь вид . Здесь обозначения экспоненциации, умножения и сложения соответствуют типам функций , виды продукции и типам сумм соответственно, в то время как натуральные числа маркировать конечные типы ; в этом смысле конструкторы типов напоминают полиномиальные функции в. [2]
Таким образом, производная от конструктора типа может быть сформирована с помощью этой синтаксической аналогии: например, для тернарного дерева без меток, производная от конструктора типа будет эквивалентно , Аналогично использованию сумм и энергетических правил в дифференциальном исчислении. Тип контекстов застежки-молнии поверх оригинального. эквивалентен производной конструктора типа, применяемой к исходному типу, . [3]
Для иллюстрации рассмотрим рекурсивную структуру данных двоичного дерева с узлами, которые являются либо контрольными узлами типа или содержать значение типа :
Частную производную конструктора типа можно вычислить как
Таким образом, тип контекстов застежки-молнии
Таким образом, мы обнаруживаем, что контекст каждого дочернего узла, не являющегося дозорным, в помеченном двоичном дереве представляет собой тройку, состоящую из
- логическое значение типа, выражая, является ли текущий узел левым или правым потомком своего родительского узла;
- значение типа , метка родительского узла текущего узла; а также
- брат типа узла , поддерево, содержащееся в другой ветви родительского элемента текущего узла.
В общем, молния для дерева типа состоит из двух частей: список контекстов типа текущего узла и каждого из его предков до корневого узла, а поддерево типа что текущий узел содержит.
Использует
Застежка-молния часто используется там, где есть некоторая концепция фокуса или перемещения в некотором наборе данных, поскольку ее семантика отражает перемещение, но функционально неразрушающим образом.
Застежка-молния использовалась в
- Xmonad , для управления фокусом и размещением окон
- Статьи Хюэ касаются структурного редактора [4], основанного на застежках-молнии и программе доказательства теорем.
- Файловая система (ZipperFS) , написанный на Haskell приношении»... транзакционная семантика, отмена любой операции файлов и каталогов, снимки, статический гарантируется сильным, повторяемые чтения, режим изоляции для клиентов, распространяющийся от копирования при записи для файлов и каталогов; встроенное средство обхода и правильное поведение для циклических ссылок на каталоги. " [5]
- Clojure имеет обширную поддержку застежек-молний. [6]
Альтернативы и расширения
Прямая модификация
На языке программирования, не являющемся чисто функциональным, может быть удобнее просто пройти по исходной структуре данных и изменить ее напрямую (возможно, после ее глубокого клонирования , чтобы не повлиять на другой код, который может содержать ссылку на нее).
Обычная молния
Универсальная застежка-молния [7] [8] [9] - это метод достижения той же цели, что и обычная застежка-молния, путем фиксации состояния обхода в продолжении при посещении каждого узла. (Код Haskell, приведенный в справочнике, использует универсальное программирование для генерации функции обхода для любой структуры данных, но это необязательно - может использоваться любая подходящая функция обхода.)
Однако Generic Zipper включает в себя инверсию управления , поэтому для некоторых ее применений требуется конечный автомат (или эквивалент), чтобы отслеживать, что делать дальше.
Рекомендации
- ^ Huet 1997
- ^ Joyal, Андре (1981), "Une Théorie combinatoire де SERIES formelles", Успехи математических наук 42: 1-82.
- ^ Макбрайд, Конор (2001), «Производная регулярного типа - это его тип контекстов с одной дырой»
- ^ Хинце, Ральф; Jeuring, Йохан (2001). «Функциональная жемчужина: плетение паутины». Журнал функционального программирования . 11 (6): 681–689. DOI : 10.1017 / S0956796801004129 . ISSN 0956-7968 .
- ^ Generic Zipper: контекст обхода
- ^ jafingerhut (22 октября 2010 г.). "clojure.zip/zipper" . ClojureDocs . Проверено 15 июня 2013 года .
- ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 1» . Проверено 29 августа 2011 года .
- ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 2» . Проверено 29 августа 2011 года .
- ^ Чун-чжи Шан, Олег Киселев (17 августа 2008 г.). «От ходьбы до застежки-молнии, часть 3» . Проверено 29 августа 2011 года .
дальнейшее чтение
- Хуэ, Жерар (сентябрь 1997 г.). «Функциональная жемчужина: молния» (PDF) . Журнал функционального программирования . 7 (5): 549–554. DOI : 10.1017 / s0956796897002864 .
- Хинце, Ральф и др. «Типы данных с индексированием» . 23 июля 2003 г.
Внешние ссылки
- Молния
- Тесей и молния
- "Roll Your Own Window Manager: отслеживание фокуса с помощью молнии"
- Определение
- «Аппликативный график потока управления на основе« молнии Хуэ »»
- Бесконечно малые типы