Оглавление

Мы разобрались с тем, как перемещаться по коллекции. Однако у читателя возникнет вопрос: как мы узнаем заранее, куда двигаться? Откуда приходит путь?

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

Clojure предлагает более простую работу с данными, структура которых известна. Например, если мы точно знаем, что на вход поступил вектор, второй элемент которого вектор, и нужно взять его второй элемент, воспользуемся get-in:

(def data [1 [2 3] 4])

(get-in data [1 1])
;; 3

То же самое касается других типов данных. Неважно, какую какую комбинацию образуют списки и словари: если структура известна заранее, до элемента легко добраться с помощью get-in или стрелочного оператора. В данном случае зипперы только усложнят код.

(def data {:users [{:name "Ivan"}]})

(-> data :users first :name)
;; "Ivan"

В чем же тогда преимущество зипперов? Свои сильные стороны они проявляют там, где get-in не работает. Речь о данных с неизвестной структурой. Представьте, что на вход поступил произвольный вектор, и нужно найти в нём строку. Она может быть как на поверхности вектора, так и вложена на три уровня. В этом случае get-in не поможет, потому что мы не знаем путь. Другой пример — XML-документ. Нужный тег может располагаться где угодно, и нужно как-то его найти. Таким образом, идеальный случай для зиппера — нечёткая структура данных, о которой у нас только предположения.

Функции zip/up, zip/down и другие образуют универсальную zip/next. Эта функция передвигает указатель так, что рано или поздно мы обойдем всю структуру. При обходе исключены повторы: мы побываем в каждом месте только раз. Пример с вектором:

(def vzip (zip/vector-zip [1 [2 3] 4]))

(-> vzip zip/node)
;; [1 [2 3] 4]

(-> vzip zip/next zip/node)
;; 1

(-> vzip zip/next zip/next zip/node)
;; [2 3]

(-> vzip zip/next zip/next zip/next zip/node)
;; 2

Очевидно, мы не знаем, сколько раз вызывать zip/next, поэтому пойдём на хитрость. Функция iterate принимает функцию f и значение x. Результатом станет последовательность, где первый элемент x, а каждый следующий — f(x) от предыдущего. Для зиппера мы получим исходную локацию, затем zip/next от неё, затем zip/next от прошлого шага и так далее.

Переменная loc-seq ниже – это цепочка локаций исходного зиппера. Чтобы получить узлы, мы берём шесть первых элементов (число взяли случайно) и вызываем для каждого zip/node.

(def loc-seq (iterate zip/next vzip))

(->> loc-seq
     (take 6)
     (map zip/node))

;; ([1 [2 3] 4]
;;   1
;;   [2 3]
;;   2
;;   3
;;   4)

Iterate порождает ленивую и бесконечную последовательность. Обе характеристики важны. Ленивость означает, что очередной сдвиг (вызов zip/next) не произойдёт до тех пор, пока вы не дойдёте до элемента в цепочке. Бесконечность означает, что zip/next вызывается неограниченное число раз. Понадобится признак, по которому мы остановим вызов zip/next, иначе поток локаций никогда не закончится.

Если исследовать loc-seq, станет ясно, что в какой-то момент zip/next уже не сдвигает указатель. Возьмём наугад сотый и тысячный элементы итерации. Их узел будет исходным вектором:

(-> loc-seq (nth 100) zip/node)
;; [1 [2 3] 4]

(-> loc-seq (nth 1000) zip/node)
;; [1 [2 3] 4]

Причина кроется в устройстве зиппера. Функция zip/next работает по принципу кольца. Когда она достигает исходной локации, цикл завершается. При этом локация получит признак завершения, и дальнейший вызов zip/next вернёт её же. Проверить признак можно функцией zip/end?:

(def loc-end
  (-> [1 2 3]
      zip/vector-zip
      zip/next
      zip/next
      zip/next
      zip/next))

loc-end
;; [[1 2 3] :end]

(zip/end? loc-end)
;; true

Чтобы получить конечную цепь локаций, будем сдвигать указатель до тех пор, пока локация не последняя. Всё вместе даёт функцию iter-zip:

(defn iter-zip [zipper]
  (->> zipper
       (iterate zip/next)
       (take-while (complement zip/end?))))

Функция вернёт все локации от начальной до конечной не включая ее. Напомним, что локация хранит узел (элемент данных), который можно извлечь с помощью zip/node. Код ниже показывает, как превратить локации в данные:

(->> [1 [2 3] 4]
     zip/vector-zip
     iter-zip
     (map zip/node))

;; ([1 [2 3] 4]
;;  1
;;  [2 3]
;;  2
;;  3
;;  4)

Теперь когда мы получили цепочку локаций, напишем поиск. Предположим, нужно проверить, есть ли в векторе кейворд :error. Сначала напишем предикат для локации – равен ли её узел этому значению:

(defn loc-error? [loc]
  (-> loc zip/node (= :error)))

Проверим, если ли среди локаций та, что подходит нашему предикату. Для этого вызовем some:

(def data [1 [2 3 [:test [:foo :error]]] 4])

(some loc-error?
      (-> data zip/vector-zip iter-zip))

;; true

Из-за ленивости мы не сканируем вектор целиком. Если нужный узел нашелся на середине, iter-zip прекращает итерацию, и дальнейшие вызовы zip/next не произойдут.

Полезно знать, что zip/next обходит дерево в глубину. При движении он стремится вниз и вправо, а наверх поднимается лишь когда шаги в эти стороны невозможны. Как мы увидим дальше, в некоторых случаях порядок обхода важен. Попадаются задачи, где мы должны двигаться вширь. По умолчанию в clojure.zip нет других вариантов обхода, но мы напишем собственный. Также мы рассмотрим задачу, где понадобится обход вширь.

Встроенный зиппер vector-zip служит для вложенных векторов. Но гораздо чаще встречаются вложенные словари. Напишем зиппер для обхода подобных данных:

(def map-data
  {:foo 1
   :bar 2
   :baz {:test "hello"
         :word {:nested true}}})

За основу возьмём знакомый нам vector-zip. Зипперы похожи, разница лишь в типе коллекции. Подумаем, как задать функции branch? и children. Сам по себе словарь — это ветка, чью потомки — элементы MapEntry. Тип MapEntry выражает пару ключа и значения. Если значение — словарь, получим из него цепочку вложенных MapEntry и так далее.

Для разминки напишем проверку на тип MapEntry:

(def entry?
  (partial instance? clojure.lang.MapEntry))

Зиппер map-zip выглядит так:

(defn map-zip [mapping]
  (zip/zipper
   (some-fn entry? map?)
   (fn [x]
     (cond
       (map? x)
       (seq x)
       (and (entry? x) (-> x val map?))
       (-> x val seq)))
   nil
   mapping))

Поясним основные моменты. Композиция (some-fn ...) вернёт истину, если хотя бы один из предикатов сработает положительно. Иными словами, на роль ветки мы рассматриваем только словарь или его узел (пару ключ-значение).

Во второй функции, которая ищет потомков, приходится делать перебор. Для словаря (проверка map?) получим потомков функцией seq – она вернёт цепочку элементов MapEntry. Если текущий элемент – MapEntry, проверим, является ли его значение вложенным словарём (функция var вернет второй элемент MapEntry). Если да, получим потомков той же функцией seq.

Обход зиппера вернет все пары ключей и значений. Если значение — вложенный словарь, мы провалимся в него при обходе. Пример:

(->> {:foo 42
      :bar {:baz 11
            :user/name "Ivan"}}
     map-zip
     iter-zip
     rest
     (map zip/node))

;; ([:foo 42]
;;  [:bar {:baz 11, :user/name "Ivan"}]
;;  [:baz 11]
;;  [:user/name "Ivan"])

Обратите внимание на функцию rest после iter-zip. Мы отбросили первую локацию, в которой находятся исходные данные. Поскольку они известны, нет смысла печатать их.

С помощью нашего map-zip легко проверить, есть ли в словаре ключ :error со значением :auth. По отдельности эти кейворды могут быть где угодно — и в ключах, и в значениях на любом уровне. Однако нас интересует их комбинация. Для этого напишем предикат:

(defn loc-err-auth? [loc]
  (-> loc zip/node (= [:error :auth])))

Убедимся, что в первом словаре нет пары, даже не смотря на то, что значения встречаются по отдельности:

(->> {:response {:error :expired
                 :auth :failed}}
     map-zip
     iter-zip
     (some loc-err-auth?))

;; nil

Но даже если пара вложена глубоко, мы найдём её:

(def data
  {:response {:info {:message "Auth error"
                     :error :auth
                     :code 1005}}})

(->> data
     map-zip
     iter-zip
     (some loc-err-auth?))

;; true

Предлагаем читателю несколько заданий для самостоятельной работы.

1) Зиппер map-zip не учитывает случай, когда ключ словаря – другой словарь, например:

{{:alg "MD5" :salt "***"} "deprecated"
 {:alg "SHA2" :salt "****"} "deprecated"
 {:alg "HMAC-SHA256" :key "xxx"} "ok"}

Такие коллекции хоть и редко, но встречаются в практике. Доработайте map-zip, чтобы он проверял не только значение MapEntry, но и ключ (вместо val используйте key).

2) Мы рассмотрели зипперы для векторов и словарей по отдельности. На практике мы работаем со смешанными данными, когда словари и векторы вложены друг в друга. Напишите универсальный зиппер, который учитывает обе коллекции при обходе.

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

Оглавление

← Зипперы в Clojure (часть 1). Азы навигации

Зипперы в Clojure (часть 3). XML-зипперы →