Зипперы в Clojure (часть 4). Поиск в XML

Предположим, нам поставили задачу: выбрать из XML магазины, где продаются айфоны. Обратите внимание: мы впервые коснулись связи между узлами, и это важно. По отдельности выбрать данные легко. Магазины — это локации, у которых тег organization. Айфоны — локации, в которых узел с тегом product и атрибутом type="tablet". Но как найти связь между ними?

В прошлый раз мы разложили XML в последовательность с помощью xml-seq. Проблема в том, что функция порождает коллекцию узлов без какой-либо связи, что не даёт нам решить задачу. Покажем это на примере. Для начала получим цепочку узлов:

(def xml-nodes
  (->> "products-branch.xml"
     io/resource
     io/file
     xml/parse
     xml-seq))

Вообразим, что в одном из элементов находится нужный товар. Например, мы встретим айфон в третьем (втором от нуля) узле:

(-> xml-nodes (nth 2))
;; {:tag :product :attrs {:type "iphone"} :content ["iPhone 11 Pro"]}

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

(->> xml-nodes (mapv :tag) (remove nil?) (run! print))
;; :catalog :organization :product :product :organization ...

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

Здесь и приходит на помощь зиппер. Локация, которую он возвращает на каждом шаге, помнит положение в структуре. От локации можно пройти в нужное место с помощью функций zip/up, zip/right и других, что мы рассмотрели в первой части. Это тот случай, когда ручная навигация оправдана.

Вернемся к XML со структурой “каталог — организация — товары”. Освежим его в памяти:

<?xml version="1.0" encoding="UTF-8"?>
<catalog>
  <organization name="re-Store">
    <product type="iphone">iPhone 11 Pro</product>
    <product type="iphone">iPhone SE</product>
  </organization>
  <organization name="DNS">
    <product type="tablet">iPad 3</product>
    <product type="notebook">Macbook Pro</product>
  </organization>
</catalog>

Прежде всего найдём локации-айфоны. Напишем предикат на айфон:

(defn loc-iphone? [loc]
  (let [node (zip/node loc)]
    (and (-> node :tag (= :product))
         (-> node :attrs :type (= "iphone")))))

Получим локации с айфонами:

(def loc-iphones
  (->> "products.xml"
       ->xml-zipper
       iter-zip
       (filter loc-iphone?)))

(count loc-iphones)
2

Теперь, чтобы найти организацию по товару, поднимемся на уровень выше с помощью zip/up. Это верно, потому что организация – родитель товара:

(def loc-orgs
  (->> loc-iphones
       (map zip/up)
       (map (comp :attrs zip/node))))

({:name "re-Store"} {:name "re-Store"})

Для каждого айфона мы получим организацию, где его продают. Получились дубли, потому что оба айфона продаются в re-Store. Чтобы избавиться от повторов, оберните результат в set.

(set loc-orgs)
#{{:name "re-Store"}}

Это и есть ответ на вопрос: айфоны можно купить в магазине re-Store. Если добавить айфон в организацию DNS, она тоже появится в loc-orgs.

Решим ту же задачу для XML с филиалами. Мы не можем вызвать zip/up для товара, чтобы получить организацию, потому что в некоторых случаях получим филиал, и понадобится еще один шаг вверх. Чтобы не гадать, сколько раз подниматься, напишем функцию loc->org. Она вызывает zip/ах до тех пор, пока не выйдет на нужный тег:

(defn loc-org? [loc]
  (-> loc zip/node :tag (= :organization)))

(defn loc->org [loc]
  (->> loc
       (iterate zip/up)
       (find-first loc-org?)))

Функция find-first находит первый элемент коллекции, который подошёл предикату. Она ещё не раз пригодится нам.

(defn find-first [pred coll]
  (some (fn [x]
          (when (pred x)
            x))
        coll))

Чтобы сократить код, не будем объявлять переменные loc-iphones и другие. Выразим поиск одной формой:

(->> "products-branch.xml"
     ->xml-zipper
     iter-zip
     (filter loc-iphone?)
     (map loc->org)
     (map (comp :attrs zip/node))
     (set))

Новое решение отличается лишь тем, что мы заменили zip/up на функцию с более сложным восхождением. В остальном ничего не изменилось.

Обратите внимание, насколько удобен XML в плане поиска и навигации. Если бы мы хранили данные в JSON, их структура и обход сильно бы отличались. Сравните товары без филиалов:

[{"name": "re-Store",
  "products": [{"type": "iphone", "name": "iPhone 11 Pro"},
               {"type": "iphone", "name": "iPhone SE"}]},
 {"name": "DNS",
  "products": [{"type": "tablet", "name": "iPad 3"},
               {"type": "notebook", "name": "Macbook Pro"}]}]

и с ними:

[{"name": "re-Store",
  "products": [{"type": "iphone", "name": "iPhone 11 Pro"},
               {"type": "iphone", "name": "iPhone SE"}]},
 {"name": "DNS",
  "branches": [{"name": "Office 1",
                "products": [{"type": "tablet", "name": "iPad 3"},
                             {"type": "notebook", "name": "Macbook Pro"}]},
               {"name": "Office 2",
                "products": [{"type": "tablet", "name": "iPad 3"},
                             {"type": "notebook", "name": "Macbook Pro"}]}]}]

Очевидно, для работы с этими данными нужен разный код. В случае с XML его структура однородна: добавление филиала меняет лишь глубину товаров, но не правило обхода.

Усложним задачу: среди обычных товаров встречаются наборы из них (bundle). Товар из набора нельзя купить отдельно. Например, тряпочка для протирки экрана продаётся чаще всего с устройством. Нас просят найти магазин, где тряпочку можно купить отдельно.

Пример XML с наборами:

<?xml version="1.0" encoding="UTF-8"?>
<catalog>
  <organization name="re-Store">
    <product type="fiber">VIP Fiber Plus</product>
    <product type="iphone">iPhone 11 Pro</product>
  </organization>
  <organization name="DNS">
    <branch name="Office 2">
      <bundle>
        <product type="fiber">Premium iFiber</product>
        <product type="iphone">iPhone 11 Pro</product>
      </bundle>
    </branch>
  </organization>
</catalog>

Сначала найдём все тряпочки. В них окажутся как отдельные товары, так и из набора:

(defn loc-fiber? [loc]
  (some-> loc zip/node :attrs :type (= "fiber")))

(->> "products-bundle.xml"
     ->xml-zipper
     iter-zip
     (filter loc-fiber?)
     (map (comp first :content zip/node)))

("VIP Fiber Plus" "Premium iFiber")

Теперь решим задачу. Из найденных тряпочек отсекаем те, что входят в набор. С точки зрения зиппера это значит, что у родителя этой локации тег не равен :bundle. От оставшихся тряпочек переходим к магазинам.

Введём предикат loc-in-bundle? – входит ли локация в набор или нет:

(defn loc-in-bundle? [loc]
  (some-> loc zip/up zip/node :tag (= :bundle)))

Решение:

(->> "products-bundle.xml"
     ->xml-zipper
     iter-zip
     (filter loc-fiber?)
     (remove loc-in-bundle?)
     (map loc->org)
     (map (comp :attrs zip/node))
     (set))

#{{:name "re-Store"}}

Магазин DNS не попал в результат, потому что в нём тряпочка продаётся в наборе.

Новое усложнение: мы хотим купить айфон, но только в наборе с тряпочкой. В какой магазин направить покупателя?

Решение: сначала ищем все айфоны. Оставляем те, что входят в набор. Среди соседей айфона ищем тряпочку. Если нашли, переходим от айфона или тряпочки к магазину. Основные функции уже готовы: это предикаты на проверку набора, тип товара и другие мелочи. Но мы не рассмотрели, как получить соседей локации.

Функции zip/lefts и zip/rights вернут узлы по левую и правую стороны от текущей локации. Совместим их через concat, чтобы получить всех соседей:

(defn node-neighbors [loc]
  (concat (zip/lefts loc)
          (zip/rights loc)))

Уточним, что это будут именно узлы, а не локации. Покажем это на примере вектора:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right ;; узел 2
    node-neighbors)

;; (1 3)

Зиппер устроен так, что получить правые и левые узлы проще, чем передвигать локацию влево или вправо. Поэтому при поиске соседей выгодно работать с узлами (данными), а не локациями.

Добавим функции, чтобы проверить, если в соседях локации тряпочка:

(defn node-fiber? [node]
  (some-> node :attrs :type (= "fiber")))

(defn with-fiber? [loc]
  (let [nodes (node-neighbors loc)]
    (find-first node-fiber? nodes)))

Финальное выражение:

(->> "products-bundle.xml"
     ->xml-zipper
     iter-zip
     (filter loc-iphone?)
     (filter loc-in-bundle?)
     (filter with-fiber?)
     (map loc->org)
     (map (comp :name :attrs zip/node))
     (set))

;; #{"DNS"}

В результате получим магазин DNS, потому что именно в нём айфон продается в комплекте с тряпкой. Оба этих товара продаются и в re-Store, но по отдельности, что не подходит. Если заменить в наборе тряпочку на гарнитуру, мы не получим ни один магазин.

Можно добавить больше ограничений. Например, из найденных магазинов выбрать те, что расположены в радиусе 300 метров от покупателя. Для этого понадобится расположение магазинов на карте и функция попадания точки в окружность. Можно выбрать только открытые магазины или те, что предлагают доставку. Запишем эти признаки в атрибуты организаций и добавим функции отбора.

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

Конечно, по сравнению с настоящей базой у XML недостаток — в нём нет индексов, и поиск работает линейным перебором, а не как в бинарных деревьях. Кроме того, наш подход требует, чтобы все находились в памяти целиком. Он не сработает для очень больших документов с миллионами записей, но пока что не будем волноваться об этом.

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

Зипперы в Clojure (часть 4). Поиск в XML

Оглавление

Оглавление