Оглавление

В этой статье мы познакомимся с зипперами в языке Clojure. Это необычный способ работы с коллекциями. С помощью зиппера можно обойти и изменить произвольные данные, а также выполнить в них поиск. Зиппер — мощный инструмент для работы с данными. Однако он не так прост, как обычная итерация, и требует подготовки.

Объясним зиппер простыми словами. Это обертка над данными, которая предлагает универсальные действия над ними. Перечислим основные действия:

  • перемещение по глубине: вниз к потомкам или вверх к родителю;
  • перемещение по ширине: влево или вправо среди потомков;
  • обход всей структуры данных;
  • добавление, редактирование и удаление узлов.

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

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

Зипперы в Clojure используют мощь неизменяемых коллекций. Технически зиппер — это коллекция, которая хранит оригинал и положение указателя в нем. Все вместе это называется положением или локацией (location). Шаг в любую сторону вернет новую локацию подобно тому, как функции assoc или update производят новые данные на базе старых.

Из текущей локации можно получить узел (ноду) — часть данных, на которые ссылается указатель. На этом моменте путаются новички, поэтому уточним различие. Локация — это исходные данные и положение в них. Передвижение по локации порождает локацию. Из локации можно извлечь узел — данные, которые встретились на этом участке.

Приведем пример с вектором [1 2 3]. Чтобы переместиться на двойку, нужно выполнить команды zip/down и zip/right. С первым шагом мы провалимся в вектор и окажемся на единице. Шаг вправо сдвинет нас на двойку. Выразим это в коде: подключим пакет под псевдонимом zip и переместимся по вектору:

(require '[clojure.zip :as zip])

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right
    zip/node)
2

Цепочка из этих функций вернет двойку, как и ожидалось. Последнее действие zip/node выводит значение (узел) из текущей локации. Если убрать zip/node, получим локацию, которая соответствует двойке. Выглядит она так:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right)

[2 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3)}]

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

Итак, зиппер предлагает перемещение по данным. Несмотря на всю мощь, он не знает, как это делать в конкретном случае, поэтому его нужно научить. Кроме входных данных, зиппер требует ответы на два вопроса:

  • Как узнать, является ли текущий элемент веткой (branch)? Веткой называют элемент, из которого можно извлечь другие элементы.

  • Если это ветка, то как извлечь из нее потомков?

Вот все, что нужно знать зипперу для навигации. Заметим, что для редактирования зиппера нужен ответ на еще один вопрос — как присоединить потомков к ветке. Однако сейчас мы рассматриваем только навигацию, и третий вопрос подождет.

В техническом плане ответы это функции. Первая принимает узел и возвращает истину или ложь. Если была истина, зиппер вызовет вторую функцию. Она принимает тот же узел, но на этот раз должна вернуть последовательность дочерних узлов или nil, если их нет.

Чтобы получить зиппер, нужно сообщить ему исходные данные и две функции для ветки и потомков. До тех пор, пока мы только читаем зиппер, третья функция может быть nil. Зипперы живут в пакете clojure.zip. Подключите его в пространство, как делали это выше:

(ns my.project
  (:require [clojure.zip :as zip]))

В свободное время исследуйте исходный код этого модуля. Он занимает всего 280 строк!

Функция zip/zipper порождает зиппер из функций и исходных данных. Это центральная точка модуля, его строительный материал. Для частых случаев модуль предлагает уже готовые зипперы, которым нужно передать только данные. На роль примера подходит vector-zip для вложенных векторов. Приведем его код в сокращении:

(defn vector-zip
  [root]
  (zipper vector?
          seq
          ...
          root))

Третий параметр мы заменили на многоточие. Это функция, которая порождает ветку из дочерних узлов — вопрос, который пока что обходим стороной. Если передать в vector-zip вектор [1 2 3], произойдет следующее.

Зиппер обернет вектор и выставит указатель на него самого. Из начального положения можно проследовать только вниз, потому что у вектора нет родителя (вверх) и соседей (влево и вправо). При смещении вниз зиппер сначала проверит, что текущий узел — ветка. Сработает выражение (vector? [1 2 3]), что вернет истину. В этом случае зиппер выполнит (seq [1 2 3]), чтобы получить потомков. Ими станет последовательность (1 2 3). Как только потомки найдены, зиппер установит указатель на крайний левый потомок.

Покажем это на схеме. Начальная позиция, указатель на исходных данных:

                ┌───────┐
                │  nil  │
                └───────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │  nil  │◀───┃  [1 2 3]  ┃───▶│  nil  │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │   1   │
                └───────┘

Шаг вниз, указатель на единице:

                ┌───────┐
                │[1 2 3]│
                └───────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │  nil  │◀───┃     1     ┃───▶│   2   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Шаг вправо, указатель на двойке:

                ┌───────┐
                │[1 2 3]│
                └───────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃     2     ┃───▶│   3   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

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

(def loc2
  (-> [1 2 3]
      zip/vector-zip
      zip/down
      zip/right))

(-> loc2 zip/node)
2

(-> loc2 zip/right zip/node)
3

(-> loc2 zip/left zip/node)
1

При попытке сдвинуться вниз зиппер выполнит предикат (vector? 2). Результат будет ложью, что значит, что текущий элемент не ветка, а лист, и движение вниз запрещено.

При передвижении нужно учитывать следующее. Каждый шаг порождает новую локацию, не изменяя старую. Если вы сохранили в переменную некоторое положение, вызовы zip/right, zip/down и другие никак ее не изменят. Из этого следует, что зипперы сочетаются со стрелочным оператором ->. Следующая цепочка привет нас обратно в двойку:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right
    zip/right
    zip/left
    zip/node)
2

При ручном передвижении велики шансы выйти за пределы коллекции. Шаг вникуда вернет nil вместо локации:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/left)
nil

Это сигнал, что вы идете по неверному маршруту. Проблема в том, что из nil нельзя вернуться на прежнее место. Nil означает пустую локацию, и в ней нет ссылки на прежний шаг. Для пустой локации функции zip/up, zip/right и другие вернут nil, что означает, что вы будете топтаться на месте.

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/left
    zip/left
    zip/left
    zip/left)

Исключение составляет функция zip/down: при попытке спуститься из nil вы получите исключение NullPointerException. Это недочет, который забыли исправить в исходном коде.

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/left
    zip/down)

;; Execution error (NullPointerException)...

Рассмотрим случай с более сложным вектором. Один из его потомков — другой вектор: [1 [2 3] 4]. Чтобы переместить указатель на тройку, выполним шаги “вниз”, “вправо”, “вниз”, “вправо”. Сохраним локацию в переменную:

(def loc3
  (-> [1 [2 3] 4]
      zip/vector-zip
      zip/down
      zip/right
      zip/down
      zip/right))

(zip/node loc3)
3

Серия рисунков, которая показывает, что происходит на каждом шаге. Исходная позиция:

                ┌───────┐
                │  nil  │
                └───────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │  nil  │◀───┃[1 [2 3] 4]┃───▶│  nil  │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │   1   │
                └───────┘

Шаг вниз:

              ┌───────────┐
              │[1 [2 3] 4]│
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │  nil  │◀───┃     1     ┃───▶│ [2 3] │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Вправо:

              ┌───────────┐
              │[1 [2 3] 4]│
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃   [2 3]   ┃───▶│   4   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │   2   │
                └───────┘

Вниз:

              ┌───────────┐
              │   [2 3]   │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃     2     ┃───▶│   3   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Вправо (мы у цели):

              ┌───────────┐
              │   [2 3]   │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   2   │◀───┃     3     ┃───▶│  nil  │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Чтобы перейти на четверку из текущей позиции, сначала поднимемся вверх. Указатель сдвинется на вектор [2 3]. В этот момент мы находимся среди потомков исходного вектора и можем перемещаться по горизонтали. Сделаем шаг вправо и окажемся на цифре 4.

Текущая локация:

              ┌───────────┐
              │   [2 3]   │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   2   │◀───┃     3     ┃───▶│  nil  │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Шаг вверх:

              ┌───────────┐
              │[1 [2 3] 4]│
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃   [2 3]   ┃───▶│   4   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │   2   │
                └───────┘

Шаг вправо:

              ┌───────────┐
              │[1 [2 3] 4]│
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │ [2 3] │◀───┃     4     ┃───▶│  nil  │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │  nil  │
                └───────┘

Исходный вектор может быть любой вложенности. Ради интереса замените 3 на еще один вектор и спуститесь в него.

Что случится, если передать в vector-zip что-то отличное от вектора? Предположим, nil, строку или число. Перед тем, как двигаться, зиппер проверяет, подходит ли узел на роль ветки и можно ли извлечь из него потомков. Для vector-zip проверка выполняется с помощью функции vector?, которая вернет nil для всех отличных от вектора значений. В результате получим локацию, из которой нельзя шагнуть никуда: ни вниз, ни в стороны. Это тупиковый случай, и его нужно избегать.

(-> "test"
    zip/vector-zip
    zip/down)
nil

Модуль clojure.zip предлагает и другие встроенные зипперы. Особенно интересен xml-zip для навигации по XML-дереву. Мы обсудим его отдельно, когда читатель познакомится с другими свойствами зипперов.

(Продолжение следует)

Оглавление