Известно, что дерево – довольно сложная структура. И если чтение успешно реализуется в том числе рекурсией (которая не лишена своих проблем), то с изменением дела обстоят совсем не хорошо.
При этом довольно давно существует высоко эффективный инструмент для работы с деревьями – зипперы, однако широкого распространения он не получил и, мне кажется, я знаю почему.
Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.
Это образное объяснение, если поскрипеть мозгами, обычно, конечно же, понимается только отчасти. Далее зипперы откладываются в сторону, потому что «это непонятная какая-то функциональная заморочка, типа монад, потом разберусь».
У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.
Рассмотрим, как развивалась идея.
Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).
Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.
По сути, у нас получился некий компонент-курсор для работы с векторами, который мы можем сдвигать влево и вправо и считывать данные из текущей позиции. Естественным развитием идеи будет обогащение этого компонента дополнительными возможностями. Пусть он помимо сдвига и чтения текущего еще говорит нам, где мы находимся:
Мы можем пойти дальше и создать такой API этого компонента:
Отметим, что наш компонент-курсор никоим образом не завязан на векторы и символы, то есть он может использоваться для любых коллекций с элементами любого типа. Очень хороший компонент.
А что с деревьями? Почему бы не придумать что-то аналогичное для деревьев? Легко!
В случае дерева естественным образом добавились новые возможности: теперь мы можем ходить не только влево и вправо, но еще вверх и вниз, а также определять находимся ли мы в корне или в листе дерева.
И, конечно же, сразу руки чешутся обогатить API:
Дамы и господа, разрешите представить… Zipper!
Очевидно, что приведенный API не полон, естественно нужно добавить два метода для depth first поиска: Предыдущий и Следующий, которые будут сдвигать окошечко вперед и назад согласно правилам поиска. Можно добавить метод ДобавитьДочернееЗначение, для удобства. В общем, мы плавно переходим к деталям реализации, чего делать не собирались.
Главное, что мы нащупали саму идею, которая теперь кажется очень банальной и естественной, и таковой является.
А где же пресловутая вывернутая на изнанку перчатка?
Да вот же она! Если мы заменим методы ПозицияСлева, ПозицияСправа, ПозицияСверху на ЗначенияСлева, ЗначенияСправа, ЗначенияСверху, то мы получим «взгляд на дерево изнутри»: имеется текущее значение и
Чем не вывернутая перчатка?
Можно переходить к практике.
Но прежде, восполним одно упущение. Нужно упомянуть, что зипперы – это функциональный концепт, то есть они наиболее эффективны в окружении персистентных структур данных (грубо говоря, данные не изменяются, но только создаются новые), функций как объектов первого класса (грубо говоря, функции можно в параметрах передавать) и вот этого всего.
Если ваша платформа предоставляет эффективно реализованные персистентные структуры, то и зипперы автоматически получаются эффективными и low cost (ничего не стоящими) компонентами. Их можно смело создавать и пересоздавать по потребности, не сильно заботясь о накладных расходах.
Наша платформа – clojure(script) – персистентные структуры предоставляет. Мало того, она предоставляет и сами зипперы: пространство имен clojure.zip, рекомендую ознакомиться с исходным кодом – простая, чистенькая реализация.
Восполним второе упущение. В случае с курсором для вектора, мы отметили, что курсор не завязан ни на вектор, ни на символы, и может использоваться с любыми коллекциями.
А что на счет зипперов?
Все точно так же! Концептуально зипперы не привязаны ни к структуре, ни к данным, то есть могут использоваться на любых деревьях. Другими словами, зиппер позволяет абстрагировать алгоритм обработки дерева от его структуры.
Clojure.zip, к примеру, предоставляет нам функцию zipper, которая создает зиппер под наши потребности:
(zipper branch? children make-node root)
Используя эту функцию мы можем создать зиппер работающий с нашей конкретной структурой. Допустим, у нас есть такое небольшое деревце:
Создадим зиппер:
Как нам получить полный текст дерева?
Результат выполнения: “С добрым утромстрана!” Отметим, что обход дерева сделан итеративно, а не рекурсивно.
Нам бы вставить запятую с пробелом после обращения. Сказано – сделано!
new-z это измененный зиппер. Если нам нужно собственно измененное дерево:
Хотя базовый API реализован в виде функций пространства сlojure.zip, бывает полезно заглянуть в сам зиппер, а для этого нужно понимать, что он из себя представляет. В данной реализации это просто вектор из двух компонентов: текущий узел дерева и мапа описывающая его положение (та самая перчатка) с ключами:
В нашем примере new-z будет выглядеть так:
Кстати, все примеры из статьи можно без проблем погонять на online REPL-е не заморачиваясь с развертыванием.
И немножечко терминологии: zipper – это концепт, идея. Конкретный инстанс (как new-z в нашем примере) принято называть локацией, что очень логично.
На этом все. Да поможет эта статья страждущему функциональному древосеку на его нелегком пути! Спасибо за внимание.
UPD: qnikst очень верно подметил, что статье не хватает некоторой ссылки на теорию, которая крайне полезна при ответе на практический вопрос "как нам организовать зиппер для конкретной структуры?". Разве не здорово было бы уметь математически точно подбирать зиппер под структуру?!
Для этого нужно уметь описывать структуру данных алгебраически, и полученное выражение дифференцировать. Второе все умеют со школы, а вот с первым может быть затык. Сам по себе этот вопрос мне кажется крайне интересным, а практическое изложение тянет на отдельную статью, которой пока нет. Поэтому отсылаю интересующихся к лучшему материалу, что я нашел по этой теме в сети на русском:
Алгебра данных и исчисление мутаций (перевод)
И еще одна ссылка для полноты картины, для более полного и более академичного описания понятия «алгебраический тип данных»: журнал «Практика функционального программирования»
При этом довольно давно существует высоко эффективный инструмент для работы с деревьями – зипперы, однако широкого распространения он не получил и, мне кажется, я знаю почему.
Классическое концептуальное объяснение зиппера, выглядит как-то так: это взгляд изнутри на древовидную структуру как бы вывернутую наизнанку, вроде вывернутой перчатки.
Это образное объяснение, если поскрипеть мозгами, обычно, конечно же, понимается только отчасти. Далее зипперы откладываются в сторону, потому что «это непонятная какая-то функциональная заморочка, типа монад, потом разберусь».
У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.
Рассмотрим, как развивалась идея.
Допустим, у нас есть некоторая последовательность неважно каких данных. Пусть это будет вектор (массив).
Вот вектор с элементами-символами, с которым нам нужно работать. Пускай нам нужно гулять по нему влево и вправо и считывать символы. Естественным образом возникает идея некоторого «окошечка» шириной в один элемент, которое мы можем смещать вправо и влево.
По сути, у нас получился некий компонент-курсор для работы с векторами, который мы можем сдвигать влево и вправо и считывать данные из текущей позиции. Естественным развитием идеи будет обогащение этого компонента дополнительными возможностями. Пусть он помимо сдвига и чтения текущего еще говорит нам, где мы находимся:
Мы можем пойти дальше и создать такой 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 очень верно подметил, что статье не хватает некоторой ссылки на теорию, которая крайне полезна при ответе на практический вопрос "как нам организовать зиппер для конкретной структуры?". Разве не здорово было бы уметь математически точно подбирать зиппер под структуру?!
Для этого нужно уметь описывать структуру данных алгебраически, и полученное выражение дифференцировать. Второе все умеют со школы, а вот с первым может быть затык. Сам по себе этот вопрос мне кажется крайне интересным, а практическое изложение тянет на отдельную статью, которой пока нет. Поэтому отсылаю интересующихся к лучшему материалу, что я нашел по этой теме в сети на русском:
Алгебра данных и исчисление мутаций (перевод)
И еще одна ссылка для полноты картины, для более полного и более академичного описания понятия «алгебраический тип данных»: журнал «Практика функционального программирования»