Известно, что дерево – довольно сложная структура. И если чтение успешно реализуется рекурсией (которая не лишена своих проблем), то с изменением дела обстоят совсем не хорошо.
При этом довольно давно существует высоко эффективный инструмент для работы с деревьями – зипперы, однако широкого распространения он не получил и, мне кажется, я знаю почему.
Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.
Это образное объяснение, если поскрипеть мозгами, обычно, конечно же, понимается только в какой-то мере, далее зипперы откладываются в сторону, потому что «это непонятная какая-то функциональная заморочка, типа монад, потом разберусь».
У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.
Рассмотрим, как развивалась идея.
Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).
Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.
По сути, у нас получился некий инструментальный компонент-курсор для работы с векторами, который мы можем сдвигать влево и вправо и считывать данные из текущей позиции. Естественным развитием идеи будет обогащение этого компонента дополнительными возможностями. Пусть он помимо сдвига и чтения текущего еще говорит нам, где мы находимся:
Мы можем пойти дальше и создать такой 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 ["страна!"]}
]})
Создадим зиппер:
(def sample-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 – копия родительской «перчатки»
И немножечко терминологии: zipper – это концепт, идея. Конкретный инстанс (как new-z в нашем примере) принято называть локацией, что очень логично.
На этом все. Да поможет эта статья страждущему функциональному древосеку на его нелегком пути! Спасибо за внимание.
Автор: snoopnstalk
