Молния (структура данных)

Застежка -молния — это метод представления совокупной структуры данных , который удобен для написания программ, которые произвольно обходят структуру и обновляют ее содержимое, особенно в чисто функциональных языках программирования . Молния была описана Жераром Юэ в 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)))) а 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) восстановить исходный список, начиная с [3, 4].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Использование

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

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

Xmonad для управления фокусом и размещением окон.
В статьях Юэ упоминается структурный редактор. ^{[ 4 ]} на основе застежек-молний и средства доказательства теорем
Файловая система (ZipperFS), написанная на Haskell , предлагающая «... транзакционную семантику; отмену любых операций с файлами и каталогами; моментальные снимки; статически гарантированный самый сильный, повторяемый режим чтения и изоляции для клиентов; повсеместное копирование при записи для файлов и каталогов; встроенная возможность обхода и просто правильное поведение для циклических ссылок на каталоги». ^{[ 5 ]}
Clojure имеет обширную поддержку застежек-молний. ^{[ 6 ]}

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

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

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

Универсальная молния

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

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

Ссылки

^ Сделано в 1997 году.
^ Джоял, Андре (октябрь 1981 г.). «Комбинаторная теория формальных рядов» . Достижения в математике . 42 (1): 1–82. дои : 10.1016/0001-8708(81)90052-9 .
^ Макбрайд, Конор (2001), «Производная регулярного типа - это его тип контекстов с одной дыркой»
^ Хинце, Ральф; Журинг, Йохан (2001). «Функциональная жемчужина: плетение паутины» . Журнал функционального программирования . 11 (6): 681–689. дои : 10.1017/S0956796801004129 . ISSN 0956-7968 . S2CID 35791452 .
^ Generic Zipper: контекст обхода
^ джафингерхут (22 октября 2010 г.). «clojure.zip/zipper» . Документы Clojure . Проверено 15 июня 2013 г.
^ Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 1» . Проверено 29 августа 2011 г.
^ Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 2» . Проверено 29 августа 2011 г.
^ Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 3» . Проверено 29 августа 2011 г.

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

Юэ, Жерар (сентябрь 1997 г.). «Молния» (PDF) . Журнал функционального программирования . 7 (5): 549–554. дои : 10.1017/s0956796897002864 . S2CID 31179878 .
Хинце, Ральф; Журинг, Йохан; Лё, Андрес (май 2004 г.). «Типы данных с индексированием типов» . Наука компьютерного программирования . 51 (1–2): 117–151. дои : 10.1016/j.scico.2003.07.001 .

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

[1] Сделано в 1997 году.

[2] Джоял, Андре (октябрь 1981 г.). «Комбинаторная теория формальных рядов» . Достижения в математике . 42 (1): 1–82. дои : 10.1016/0001-8708(81)90052-9 .

[3] Макбрайд, Конор (2001), «Производная регулярного типа - это его тип контекстов с одной дыркой»

[4] Хинце, Ральф; Журинг, Йохан (2001). «Функциональная жемчужина: плетение паутины» . Журнал функционального программирования . 11 (6): 681–689. дои : 10.1017/S0956796801004129 . ISSN 0956-7968 . S2CID 35791452 .

[5] Generic Zipper: контекст обхода

[6] джафингерхут (22 октября 2010 г.). «clojure.zip/zipper» . Документы Clojure . Проверено 15 июня 2013 г.

[7] Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 1» . Проверено 29 августа 2011 г.

[8] Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 2» . Проверено 29 августа 2011 г.

[9] Чун-чи Шан, Олег Киселев (17 августа 2008 г.). «От прогулки до застегивания молнии, часть 3» . Проверено 29 августа 2011 г.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]