Оглавление

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

Объясним зиппер простыми словами. Это обёртка над данными с набором действий. Вот некоторые из них:

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

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

Термин “зиппер” ввел французкий ученый Жерар Юэ (Gérard Huet) в 1996 году. Юэ занимался деревьями и искал универсальный способ работы с ними. В знаменитой работе “Functional Pearl: The Zipper” Юэ привел концепцию зиппера на языке OCaml. Документ привлек внимание простотой и ясностью: описание зиппера, включая код и комментарии, уместились на четырех страницах. Современные зипперы почти не отличаются от того изложения 1996 года.

Хотя Юэ отмечает, что зиппер можно создать на любом языке, лучше всего они прижились в функциональных: Haskell, OCaml, Clojure. Зипперы поощряют неизменяемые данные и чистые преобразования. Для упомянутых языков написаны библиотеки зипперов, и разработчики хотя бы поверхностно знакомы с ними. Наоборот, в императивной среде зипперы почти неизвестны.

Зипперы доступны в Clojure с первой версии. Их легко добавить в проект, не опасаясь проблем лицензии или новых зависимостей.

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

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

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

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

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

Функция zip/vector-zip строит зиппер из вектора. Вызовы zip/down и zip/right передвинут указатель на двойку, как и ожидалось. Последний шаг 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)}]

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

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

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

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

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

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

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

Зипперы находятся в модуле clojure.zip. В свободное время исследуйте его код: он занимает всего 280 строк!

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

Функция 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 нет сведений о позиции. Для nil функции zip/up, zip/right и другие тоже вернут nil. Если не учесть это в цикле, вы будете топтаться на месте.

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

nil

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

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

;; Execution error (NullPointerException)...

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

(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]   │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │  nil  │◀───┃     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  │
                └───────┘

Исходный вектор может быть любой вложенности. Ради интереса замените тройку на [5 [6 [7 [8] 9]]] и проследуйте до девятки.

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

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

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

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

Оглавление

← Книга для читалки и телефона

Зипперы в Clojure (часть 2). Автонавигация →