При этом довольно давно существует высоко эффективный инструмент для работы с деревьями – зипперы, однако широкого распространения он не получил и, мне кажется, я знаю почему.
Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.
Это образное объяснение, если поскрипеть мозгами, обычно, конечно же, понимается только отчасти. Далее зипперы откладываются в сторону, потому что «это непонятная какая-то функциональная заморочка, типа монад, потом разберусь».
У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.
Рассмотрим, как развивалась идея.
Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).
Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.
По сути, у нас получился некий компонент-курсор для работы с векторами, который мы можем сдвигать влево и вправо и считывать данные из текущей позиции. Естественным развитием идеи будет обогащение этого компонента дополнительными возможностями. Пусть он помимо сдвига и чтения текущего еще говорит нам, где мы находимся:
Мы можем пойти дальше и создать такой API этого компонента:
- ШагВлево
- ШагВправо
- ТекущееЗначение
- ПозицияСлева
- ПозицияСправа
- КрайнийСлева?
- КрайнийСправа?
- ЗаменитьТекущееЗначение
- ВставитьЗначениеСлева
- ВставитьЗначениеСправа
- УдалитьТекущееЗначение
Отметим, что наш компонент-курсор никоим образом не завязан на векторы и символы, то есть он может использоваться для любых коллекций с элементами любого типа. Очень хороший компонент.
А что с деревьями? Почему бы не придумать что-то аналогичное для деревьев? Легко!
В случае дерева естественным образом добавились новые возможности: теперь мы можем ходить не только влево и вправо, но еще вверх и вниз, а также определять находимся ли мы в корне или в листе дерева.
И, конечно же, сразу руки чешутся обогатить API:
- ШагВлево
- ШагВправо
- ШагВверх
- ШагВниз
- ТекущееЗначение
- КорневоеЗначение
- ДочерниеЗначения
- ПозицияСлева
- ПозицияСправа
- ПозицияСверху
- КрайнийСлева?
- КрайнийСправа?
- Корень?
- Лист?
- ЗаменитьТекущееЗначение
- ВставитьЗначениеСлева
- ВставитьЗначениеСправа
- УдалитьТекущееЗначение
Дамы и господа, разрешите представить… Zipper!
Очевидно, что приведенный API не полон, естественно нужно добавить два метода для depth first поиска: Предыдущий и Следующий, которые будут сдвигать окошечко вперед и назад согласно правилам поиска. Можно добавить метод ДобавитьДочернееЗначение, для удобства. В общем, мы плавно переходим к деталям реализации, чего делать не собирались.
Главное, что мы нащупали саму идею, которая теперь кажется очень банальной и естественной, и таковой является.
А где же пресловутая вывернутая на изнанку перчатка?
Да вот же она! Если мы заменим методы ПозицияСлева, ПозицияСправа, ПозицияСверху на ЗначенияСлева, ЗначенияСправа, ЗначенияСверху, то мы получим «взгляд на дерево изнутри»: имеется текущее значение и
- ЗначенияСлева
- ЗначенияСправа
- ЗначенияСверху
- ДочерниеЗначения
Чем не вывернутая перчатка?
Можно переходить к практике.
Но прежде, восполним одно упущение. Нужно упомянуть, что зипперы – это функциональный концепт, то есть они наиболее эффективны в окружении персистентных структур данных (грубо говоря, данные не изменяются, но только создаются новые), функций как объектов первого класса (грубо говоря, функции можно в параметрах передавать) и вот этого всего.
Если ваша платформа предоставляет эффективно реализованные персистентные структуры, то и зипперы автоматически получаются эффективными и low cost (ничего не стоящими) компонентами. Их можно смело создавать и пересоздавать по потребности, не сильно заботясь о накладных расходах.
Наша платформа – clojure(script) – персистентные структуры предоставляет. Мало того, она предоставляет и сами зипперы: пространство имен clojure.zip, рекомендую ознакомиться с исходным кодом – простая, чистенькая реализация.
Восполним второе упущение. В случае с курсором для вектора, мы отметили, что курсор не завязан ни на вектор, ни на символы, и может использоваться с любыми коллекциями.
А что на счет зипперов?
Все точно так же! Концептуально зипперы не привязаны ни к структуре, ни к данным, то есть могут использоваться на любых деревьях. Другими словами, зиппер позволяет абстрагировать алгоритм обработки дерева от его структуры.
Clojure.zip, к примеру, предоставляет нам функцию zipper, которая создает зиппер под наши потребности:
(zipper branch? children make-node root)
- branch? – функция, по переданному ей узлу определяет ветка он в принципе или нет (может ли иметь дочерние узлы);
- children – функция, по переданной ей ветке возвращает коллекцию дочерних узлов;
- make-node – функция, по переданным ей узлу и коллекции дочерних возвращает ветку дерева, то есть узел с переданными дочерними;
- root – корневой узел, то есть собственно наше дерево.
Используя эту функцию мы можем создать зиппер работающий с нашей конкретной структурой. Допустим, у нас есть такое небольшое деревце:
(def sample-tree
{:tag :div
:content [
{:tag :span :content ["С добрым утром"]}
{:tag :span :content ["страна!"]}
]})
Создадим зиппер:
(require '[clojure.zip :as z]) ; для начала затребуем нэймспэйс
(def sample-z
(z/zipper
(fn [node] (not (string? node))) ; если не строчка то ветка
(fn [node] (vec(:content node))) ; берем :content у узла и приводим к вектору (мало ли, может nil передадут)
(fn [node children] (assoc node :content (vec children))) ; пишем в :content узла переданную коллекцию детей
sample-tree)) ; наше деревце
Как нам получить полный текст дерева?
(loop [z sample-z result ""] ; цикл с переменными z и result
(if (z/end? z) ; если дошли до конца дерева
result ; отдаем результат
(recur (z/next z) (if (z/branch? z) result (str result (z/node z)))))) ;иначе продолжаем цикл с новыми значениями
Результат выполнения: “С добрым утромстрана!” Отметим, что обход дерева сделан итеративно, а не рекурсивно.
Нам бы вставить запятую с пробелом после обращения. Сказано – сделано!
(def new-z
(->
sample-z
z/next
(z/insert-right {:tag :span :content [", "]})))
new-z это измененный зиппер. Если нам нужно собственно измененное дерево:
(def new-tree
(z/root new-z))
Хотя базовый API реализован в виде функций пространства сlojure.zip, бывает полезно заглянуть в сам зиппер, а для этого нужно понимать, что он из себя представляет. В данной реализации это просто вектор из двух компонентов: текущий узел дерева и мапа описывающая его положение (та самая перчатка) с ключами:
- :l – узлы слева
- :r – узлы справа
- :pnodes – узлы сверху (путь до корня)
- :ppath – копия родительской «перчатки»
- :changed? – признак того, что дерево было изменено посредством данного зиппера
В нашем примере new-z будет выглядеть так:
[{:content ["С добрым утром"], :tag :span} ; текущий узел
{:changed? true,
:l [],
:pnodes [{:content [{:content ["С добрым утром"], :tag :span}
{:content ["страна!"], :tag :span}], :tag :div}],
:ppath nil,
:r ({:content [", "], :tag :span}
{:content ["страна!"], :tag :span})}]
Кстати, все примеры из статьи можно без проблем погонять на online REPL-е не заморачиваясь с развертыванием.
И немножечко терминологии: zipper – это концепт, идея. Конкретный инстанс (как new-z в нашем примере) принято называть локацией, что очень логично.
На этом все. Да поможет эта статья страждущему функциональному древосеку на его нелегком пути! Спасибо за внимание.
UPD: qnikst очень верно подметил, что статье не хватает некоторой ссылки на теорию, которая крайне полезна при ответе на практический вопрос "как нам организовать зиппер для конкретной структуры?". Разве не здорово было бы уметь математически точно подбирать зиппер под структуру?!
Для этого нужно уметь описывать структуру данных алгебраически, и полученное выражение дифференцировать. Второе все умеют со школы, а вот с первым может быть затык. Сам по себе этот вопрос мне кажется крайне интересным, а практическое изложение тянет на отдельную статью, которой пока нет. Поэтому отсылаю интересующихся к лучшему материалу, что я нашел по этой теме в сети на русском:
Алгебра данных и исчисление мутаций (перевод)
И еще одна ссылка для полноты картины, для более полного и более академичного описания понятия «алгебраический тип данных»: журнал «Практика функционального программирования»
Комментарии (24)
Gorthauer87
18.03.2016 22:48+4Я бы скорее сказал, что это расширение идеи итераторов, но если в плюсах они по сути в обычный курсор влево вправо превращаются, то тут всё немного интереснее.
misha_shar53
19.03.2016 07:44-1Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.
Инструменты для работы с деревом данных достаточно развиты и ничего нового зипперы не дают.
В MUMPS для работы с деревом данных используются 3 функции
1 Next — следующий или предыдущий узел на том же уровне.
2 Qery — следующий или предыдущий узел с данными на уровне ниже текущего.
3 Data — состояние вершины. Есть ли в ней данные и есть ли потомки у узла.
Хотя для работы с деревом хватило бы и одной функции Next.
Такого интерфейса вполне достаточно для работы с любым деревом и без дополнительных ограничений.
snoopnstalk
19.03.2016 11:13К сожалению я о MUMPS узнал только что из вашего комментария, поэтому приходится только догадываться как вы предполагаете реализовывать изменение дерева с помощью одной только Next.
Похоже, что речь идет об изменении в прямом классическом смысле этого слова, в смысле mutation. У этого подхода есть ряд проблем, и основная — он вносит в систему время, вносит его без надобности, чем увеличивает сложность системы в разы, если не на порядки. Причем сложность эта как правило не обусловлена задачей, так называемая accidental complexity.
Во времена дефицита оперативной памяти и крутящихся дисков малого объема этот подход был оправдан просто потому что никак иначе было нельзя, грубо говоря место приходилось экономить. Времена эти давно прошли. Поэтому то мы наблюдаем нарастающую активность в функциональным программировании.
Крайне рекомендую ознакомиться с первыми 30 минутами вот этого видео. В нем дядюшка Боб обрисовывает текущие тренды и рассказывает чего следует ждать в ближайшее десятилетие. Очень полезное видео.
Конечно, всегда останется некоторый спектр задач с ограничениями по ресурсам, в которых функциональный подход будет не применим. И в некоторых из них лучшим инструментом, возможно, будет MUMPS. В таком случае мы с вами скажем, что зипперы ничего нового не дают при решении задач из этого спектра.misha_shar53
19.03.2016 15:50Я вынес из статьи, что речь идет о доступе к иерархическим данным и поэтому об этом и написал. Изменение данных в MUMPS осуществляется командой Set. Как при этом вносится время мне не понятно. Команда одномоментно изменяет структуру данных. Если изменения выполняются в одном потоке то коллизий не возникает, если в разных заданиях то есть примитивы синхронизации. Но это по моему всегда так. По поводу экономии места на диске и в ОП то же не понял. Ведь речь шла об интерфейсе к деревянным данным независимо от способа хранения этих данных.
Извините дядюшку Боба понять не в состоянии, английским не владею.snoopnstalk
19.03.2016 19:01+1Речь шла о функциональном концепте работы с деревьями. Вы привели пример, если я все верно понял, нефункционального языка. Из того, что вы сочли персистентность данных излишним требованием, я делаю вывод, что Set мутирует свой параметр (некоторым образом изменяет данные в нем самом).
Ссылка на Боба, и рассуждения про память с дисками это способ подчеркнуть тот факт, что тенденция, то в сторону функционального программирования. И это не причуды или дело вкуса, а реальный процесс.
На счет времени.
Когда наша программа выдержана в функциональном стиле, мы грубо говоря имеем чистую обработку данных. Функция: на входе данные — параметр, на выходе другие данные — результат. Нет времени "до" и "после" обработки, есть просто вход и выход.
Когда наша программа не выдержана в функциональном стиле. В ней имеются участки наподобие такого:
Tree sampleTree = {"a" 1}; ... println(sampleTree); //момент времени До Set sampleTree.Set("a", 5); println(sampleTree); //момент времени После Set
в котором у нас возникает "до" и "после". С этим очень сложно работать. Тратятся колоссальные усилия чтобы синхронизировать нужные вызовы с нужными моментами во времени.misha_shar53
20.03.2016 07:23Пример на MUMPS
Set A=5
Write A
; до этого момента имеем старое значение и никакого времени нет
Set A=6
; здесь новое значение =6 момент определен командой Set причем тут время? Какие проблемы могут здесь возникать?guai
20.03.2016 14:00Допустим, у вас есть живая система, набитая разнородными объектами, и трэдами, которые их как-то ворочают время от времени, обновляют. И мы хотим в фоне по всей инфе сформировать отчет.
Можем остановить мир и всё сделать; можем мириться с тем, что отчет у нас кривоват, и пока мы дошли до конца структуры данных, она уже поменялась 10 раз.
В кложуре есть еще 1 вариант: мы схватились за хвост структуры данных и просто по ней пошли. Все структуры данных в кложуре персистентные, то есть по сути мы получили консистентный снэпшот всей структуры на момент старта, в итоге получим консистентный отчет на время старта.
Другие потоки в системе пока могут менять те же данные, но в своих копиях, они эту же структуру держат за другие хвостики-точки зрения. Соединение этих копий назад в одну структуру атомарные.
Ну и вся фишка кложуры в том, что эти копии не прям реально копии всей инфы, а компактно представлены чем-то типа диффов и таких вот хвостиков-точек зрения на инфу, компактно всё представлено. И только такие структуры данных в кложуре и есть, всё, что пишется на кложуре, такими свойствами обладает.
Вот отсутствие времени в этом и проявляется, я могу хоть неделю отчет строить, и пофигу, кто там что меняет, моя работа зависит только от входных данных. Я за данные схватился и держусь, и никто у меня их под рукой не поменяет незаметно. Для простого ненапряжного параллелизма это важно.misha_shar53
21.03.2016 05:39Выход конечно славный. Но я слабо представляю как это можно практически осуществить, кроме как остановив корректировку сделав копию в сторонку и работать с этой копией. Технически это возможно сделать. Но практически достаточно затратно и долго. Я в подобной ситуации работаю с кривоватыми данными. Заморозить всю систему и делать копию не выход. Хотя можно отложить корректировку до определенного момента времени, но тогда возникнут проблемы на рабочем месте у корректирующего данные.
guai
21.03.2016 12:34практически не сложно, берем кложур и пользуемся. на других языках такие структуры данных тоже можно заюзать, но тут, как только мы начнем их смешивать с обычными мутабельными коллекциями, так всё превратится в тыкву.
ну хотя как не сложно, если есть готовый продукт, то к нему привернуть это всё будет не просто, у него может быть архитектура совершенно неподходящая…
snoopnstalk
20.03.2016 15:34Давайте попробуем так. Попробуйте сформулировать ответ на вопрос "почему\для чего нужны транзакции?" Транзакции как способ изменения данных.
misha_shar53
21.03.2016 06:17Ну допустим в MUMPS транзакции есть. А нужны они для сохранения целостности данных. Но проблему формирования отчета из одного состояния данных. транзакции не решают.
mikhanoid
21.03.2016 07:45Дело не в дефиците оперативной памяти или крутящихся дисках. А скорее в неразвитости методов функционального программирования и отсутствии продвинутых трансляторов и сред исполнения. Потому как в своё время (вторая половина 1980-х) при ограничениях на оперативную память и скорость работы дисков существовал такой язык — SISAL, в котором SAL — это Single Assignment Language, и этот язык производительностью получаемого кода уделывал и Си, и чемпиона того времени — Фортран. То есть, вычисления с устойчивыми данными могут быть весьма эффективными.
Современный фокус внимания на таком подходе к вычислениям, скорее всего, связан не с эффективностью, а с необходимостью писать распределённые приложения, в которых изменчивость данных создаёт чрезмерно много конусов времени (ну, в терминологии векторных часов Лампорта), с которыми после некоторого предела уже невозможно надёжно работать. Поэтому, среди прочего, у нас всякие CRDT вместо баз данных и прочее, прочее.snoopnstalk
21.03.2016 16:06Возможно вы просто более глубоко понимаете проблему. Я обычно пытаюсь понять до уровня простых слов, а дальше бросаю, из за лени природной. В простых словах — не видно никаких других причин изменять, удалять данные кроме прямой необходимости делать это. Конечно необходимость эта была вызвана не неразвитостью методов, а прямыми техническими ограничениями, а чуть позднее естественной инертностью связанной с legacy, системой образования и тп. Прямые технические ограничения направляли умы на решение задач типа распределенных транзакций в большей степени, потому что это были задачи из той реальности, практические задачи. Как только реальность изменилась, начали возникать вопросы типа: а нужны ли нам транзакции вообще? можно ведь не изменять данные, а просто накапливать. Тут нет вопроса неразвитости метода. Нет метода — создадим. Отсутствует среда исполнения — напишем. Главное технических ограничений теперь нет.
anjensan
21.03.2016 14:01Ограничение на только <персистентных структур данных> сводит на нет ценность зипперов.
Ну так в Clojure все родные структуры персистентные. Так что ценность на 0 не сведена.
А насчет MUPS… Вы уже не раз на Хабре высказывались, что это ответ на главный вопрос жизни, вселенной и вообще. Спасибо за повторение.
qnikst
19.03.2016 12:24+1Целая статья про зипперы и ни одного слова про то, что это производная от алгебраического представления структуры данных?!
snoopnstalk
19.03.2016 12:33+1В целом, верное замечание. Статья правда практически ориентированная, с объяснением на пальцах, как бы алгебраические структуры данных не помешали восприятию. Но я подумаю, как их можно обыграть как минимум для расширения кругозора. Спасибо за идею.
EvilsInterrupt
19.03.2016 14:57+3производная от алгебраического представления структуры данных?!
Те кто умеет мыслить такими терминами, т.е. разбирается в алгебре им эта статья врядли чем-то поможет и чему-то научит. А вот таким как я, подобные "заумности" явно ни к чему. Оно понятно, что математика полезное дело. Не спорю. Очень полезное. Но во всем нужна золотая середина. Между "заумностью" и практичностью. Введя "заумности" такие как я не осилили бы и отложили бы прочтение на потом ;)qnikst
19.03.2016 15:50+1Вполне возможно делать это в 2 статьи или доп параграфом, т.к. часто возникают вопросы, а как правильно сделать зипперы для той или иной структуры данных и эти "заумности" дают весьма точный ответ. В принципе добавления общей информации и ссылки на статьи вполне достаточно, например, тем кто представляет что такое зипперы, но не теорию за этим стоящую.
Vlad911
19.03.2016 16:11+1Правильно ли понимаю, что zipper'ы можно использовать и для итерации по произвольному графу?
В случае с BSP, QuadTree, OcTree zipper'ы выглядят практично.snoopnstalk
19.03.2016 17:26+1Хороший вопрос. На счет произвольности, меня смущает цикличный вариант. Есть мнение, что и этот вариант можно реализовать через доп абстракцию, например представление графа в виде некоторого замыкания относительно его структуры, а уже на базе этого замыкания создавать зиппер. В любом случае это вопрос конкретной задачи, в каком виде нужно получать результаты и какие манипуляции проделывать с графами. Будет время обязательно попробую с циклами. Если вы этим занимаетесь, буду также рад прочитать о результатах ваших экспериментов.
mikhanoid
21.03.2016 07:50+1Да, можно с любой структурой данных, если в конкретном алгоритме проход по ней можете представить в виде дерева. То есть, сама структура данных может в виде дерева не существовать. И вообще не существовать. Потомки могут быть вычислимыми. Поэтому zipper-ы можно использовать для всяких переборных задач с back-tracking-ом. Ну, а то, что Вы перечислили так и вообще деревья в своём исходном определении. Поэтому, никаких проблем.
ivanych
Это же XPath.
snoopnstalk
Я бы сказал, что мы можем легко реализовать XPath на базе зипперов. Но если строго, то нет, это не XPath.