Замечательные zippers, или как я научился не волноваться и полюбил древовидные структуры данных

[snoopnstalk]

Я бы сказал, что мы можем легко реализовать XPath на базе зипперов. Но если строго, то нет, это не XPath.

[Gorthauer87]

Я бы скорее сказал, что это расширение идеи итераторов, но если в плюсах они по сути в обычный курсор влево вправо превращаются, то тут всё немного интереснее.

[misha_shar53]

Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.
Инструменты для работы с деревом данных достаточно развиты и ничего нового зипперы не дают.
В MUMPS для работы с деревом данных используются 3 функции
1 Next — следующий или предыдущий узел на том же уровне.
2 Qery — следующий или предыдущий узел с данными на уровне ниже текущего.
3 Data — состояние вершины. Есть ли в ней данные и есть ли потомки у узла.
Хотя для работы с деревом хватило бы и одной функции Next.
Такого интерфейса вполне достаточно для работы с любым деревом и без дополнительных ограничений.

[snoopnstalk]

К сожалению я о MUMPS узнал только что из вашего комментария, поэтому приходится только догадываться как вы предполагаете реализовывать изменение дерева с помощью одной только Next.
Похоже, что речь идет об изменении в прямом классическом смысле этого слова, в смысле mutation. У этого подхода есть ряд проблем, и основная — он вносит в систему время, вносит его без надобности, чем увеличивает сложность системы в разы, если не на порядки. Причем сложность эта как правило не обусловлена задачей, так называемая accidental complexity.
Во времена дефицита оперативной памяти и крутящихся дисков малого объема этот подход был оправдан просто потому что никак иначе было нельзя, грубо говоря место приходилось экономить. Времена эти давно прошли. Поэтому то мы наблюдаем нарастающую активность в функциональным программировании.
Крайне рекомендую ознакомиться с первыми 30 минутами вот этого видео. В нем дядюшка Боб обрисовывает текущие тренды и рассказывает чего следует ждать в ближайшее десятилетие. Очень полезное видео.
Конечно, всегда останется некоторый спектр задач с ограничениями по ресурсам, в которых функциональный подход будет не применим. И в некоторых из них лучшим инструментом, возможно, будет MUMPS. В таком случае мы с вами скажем, что зипперы ничего нового не дают при решении задач из этого спектра.

[misha_shar53]

Я вынес из статьи, что речь идет о доступе к иерархическим данным и поэтому об этом и написал. Изменение данных в MUMPS осуществляется командой Set. Как при этом вносится время мне не понятно. Команда одномоментно изменяет структуру данных. Если изменения выполняются в одном потоке то коллизий не возникает, если в разных заданиях то есть примитивы синхронизации. Но это по моему всегда так. По поводу экономии места на диске и в ОП то же не понял. Ведь речь шла об интерфейсе к деревянным данным независимо от способа хранения этих данных.
Извините дядюшку Боба понять не в состоянии, английским не владею.

[snoopnstalk]

Речь шла о функциональном концепте работы с деревьями. Вы привели пример, если я все верно понял, нефункционального языка. Из того, что вы сочли персистентность данных излишним требованием, я делаю вывод, что Set мутирует свой параметр (некоторым образом изменяет данные в нем самом).
Ссылка на Боба, и рассуждения про память с дисками это способ подчеркнуть тот факт, что тенденция, то в сторону функционального программирования. И это не причуды или дело вкуса, а реальный процесс.
На счет времени.
Когда наша программа выдержана в функциональном стиле, мы грубо говоря имеем чистую обработку данных. Функция: на входе данные — параметр, на выходе другие данные — результат. Нет времени "до" и "после" обработки, есть просто вход и выход.
Когда наша программа не выдержана в функциональном стиле. В ней имеются участки наподобие такого:

Tree sampleTree = {"a" 1};
...
println(sampleTree); //момент времени До Set 
sampleTree.Set("a", 5);
println(sampleTree); //момент времени После Set 

в котором у нас возникает "до" и "после". С этим очень сложно работать. Тратятся колоссальные усилия чтобы синхронизировать нужные вызовы с нужными моментами во времени.

[misha_shar53]

Пример на MUMPS
Set A=5
Write A
; до этого момента имеем старое значение и никакого времени нет
Set A=6
; здесь новое значение =6 момент определен командой Set причем тут время? Какие проблемы могут здесь возникать?

[misha_shar53]

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

[snoopnstalk]

Давайте попробуем так. Попробуйте сформулировать ответ на вопрос "почему\для чего нужны транзакции?" Транзакции как способ изменения данных.

[misha_shar53]

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

[snoopnstalk]

Сделайте еще шаг в рассуждении: Когда и почему может нарушаться целостность данных?

[mikhanoid]

Дело не в дефиците оперативной памяти или крутящихся дисках. А скорее в неразвитости методов функционального программирования и отсутствии продвинутых трансляторов и сред исполнения. Потому как в своё время (вторая половина 1980-х) при ограничениях на оперативную память и скорость работы дисков существовал такой язык — SISAL, в котором SAL — это Single Assignment Language, и этот язык производительностью получаемого кода уделывал и Си, и чемпиона того времени — Фортран. То есть, вычисления с устойчивыми данными могут быть весьма эффективными.

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

[snoopnstalk]

Возможно вы просто более глубоко понимаете проблему. Я обычно пытаюсь понять до уровня простых слов, а дальше бросаю, из за лени природной. В простых словах — не видно никаких других причин изменять, удалять данные кроме прямой необходимости делать это. Конечно необходимость эта была вызвана не неразвитостью методов, а прямыми техническими ограничениями, а чуть позднее естественной инертностью связанной с legacy, системой образования и тп. Прямые технические ограничения направляли умы на решение задач типа распределенных транзакций в большей степени, потому что это были задачи из той реальности, практические задачи. Как только реальность изменилась, начали возникать вопросы типа: а нужны ли нам транзакции вообще? можно ведь не изменять данные, а просто накапливать. Тут нет вопроса неразвитости метода. Нет метода — создадим. Отсутствует среда исполнения — напишем. Главное технических ограничений теперь нет.

[anjensan]

Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.

Ну так в Clojure все родные структуры персистентные. Так что ценность на 0 не сведена.
А насчет MUPS… Вы уже не раз на Хабре высказывались, что это ответ на главный вопрос жизни, вселенной и вообще. Спасибо за повторение.

[qnikst]

Целая статья про зипперы и ни одного слова про то, что это производная от алгебраического представления структуры данных?!

[snoopnstalk]

В целом, верное замечание. Статья правда практически ориентированная, с объяснением на пальцах, как бы алгебраические структуры данных не помешали восприятию. Но я подумаю, как их можно обыграть как минимум для расширения кругозора. Спасибо за идею.

[EvilsInterrupt]

производная от алгебраического представления структуры данных?!

Те кто умеет мыслить такими терминами, т.е. разбирается в алгебре им эта статья врядли чем-то поможет и чему-то научит. А вот таким как я, подобные "заумности" явно ни к чему. Оно понятно, что математика полезное дело. Не спорю. Очень полезное. Но во всем нужна золотая середина. Между "заумностью" и практичностью. Введя "заумности" такие как я не осилили бы и отложили бы прочтение на потом ;)

[qnikst]

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

[snoopnstalk]

Готово, еще раз спасибо за ценное замечание.

[Vlad911]

Правильно ли понимаю, что zipper'ы можно использовать и для итерации по произвольному графу?
В случае с BSP, QuadTree, OcTree zipper'ы выглядят практично.

[snoopnstalk]

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

[mikhanoid]

Да, можно с любой структурой данных, если в конкретном алгоритме проход по ней можете представить в виде дерева. То есть, сама структура данных может в виде дерева не существовать. И вообще не существовать. Потомки могут быть вычислимыми. Поэтому zipper-ы можно использовать для всяких переборных задач с back-tracking-ом. Ну, а то, что Вы перечислили так и вообще деревья в своём исходном определении. Поэтому, никаких проблем.