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

в 14:50, , рубрики: clojure, clojurescript, zippers, Алгоритмы, функциональное программирование, метки:

Известно, что дерево – довольно сложная структура. И если чтение успешно реализуется рекурсией (которая не лишена своих проблем), то с изменением дела обстоят совсем не хорошо.

При этом довольно давно существует высоко эффективный инструмент для работы с деревьями – зипперы, однако широкого распространения он не получил и, мне кажется, я знаю почему.

Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.

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

У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.

Рассмотрим, как развивалась идея.

Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).

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

Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.

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

По сути, у нас получился некий инструментальный компонент-курсор для работы с векторами, который мы можем сдвигать влево и вправо и считывать данные из текущей позиции. Естественным развитием идеи будет обогащение этого компонента дополнительными возможностями. Пусть он помимо сдвига и чтения текущего еще говорит нам, где мы находимся:

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

Мы можем пойти дальше и создать такой API этого компонента:

  • ШагВлево
  • ШагВправо
  • ТекущееЗначение
  • ПозицияСлева
  • ПозицияСправа
  • КрайнийСлева?
  • КрайнийСправа?
  • ЗаменитьТекущееЗначение
  • ВставитьЗначениеСлева
  • ВставитьЗначениеСправа
  • УдалитьТекущееЗначение

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

А что с деревьями? Почему бы не придумать что-то аналогичное для деревьев? Легко!

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

В случае дерева естественным образом добавились новые возможности: теперь мы можем ходить не только влево и вправо, но еще вверх и вниз, а также определять находимся ли мы в корне или в листе дерева.
И, конечно же, сразу руки чешутся обогатить 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

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js