Оглавление

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

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

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

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

Хорошая новость в том, что зипперы доступны в базовой поставке 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, если их нет. В коде эти функции называют branch? и children.

Чтобы получить зиппер, нужно сообщить ему входные данные и две функции, которые мы только что описали. До тех пор, пока мы только читаем зиппер, третья функция может быть 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 и другие никак её не изменят. Выше мы объявили переменную loc2, которая указывает на двойку. Можно оттолкнуться от неё, чтобы получить исходный вектор:

(-> loc2 zip/up zip/node)
;; [1 2 3]

При ручном перемещении велики шансы выйти за пределы коллекции. Шаг в никуда вернёт 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-дереву. Мы обсудим его отдельно, когда читатель познакомится с другими свойствами зипперов.

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

Оглавление