Зипперы в Clojure (часть 4). Поиск в XML
Оглавление
- Зипперы (часть 1). Азы навигации
- Зипперы (часть 2). Автонавигация
- Зипперы (часть 3). XML-зипперы
- Зипперы (часть 4). Поиск в XML
- Зипперы (часть 5). Редактирование
- Зипперы (часть 6). Виртуальные деревья. Обмен валют
- Зипперы (часть 7). Обход в ширину. Улучшенный обмен валют
- Зипперы (часть 8). Заключение
Предположим, нам поставили задачу: из 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 ...
Идея верная, но в целом слабая, потому что зависит от порядка обхода XML. Кроме того, решение задачи усложняется: при обходе нужно не просто выбрать нужные товары, но и переместиться назад в поисках магазина. Затем продолжить вперед и при этом пропустить найденный товар, чтобы не попасть в вечный цикл. Схема подразумевает состояние и хорошо смотрелась бы на императивных языках, но не в 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
. Она поднимается до тех пор, пока мы не
выйдем на нужный тег:
(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 недостаток — в нём нет индексов, и поиск работает линейным перебором, а не как в словарях. Кроме того, наш подход требует, чтобы все данные находились в памяти. Он не сработает для очень больших документов с миллионами записей, но пока что не будем волноваться об этом.
(Продолжение следует)
Оглавление
- Зипперы (часть 1). Азы навигации
- Зипперы (часть 2). Автонавигация
- Зипперы (часть 3). XML-зипперы
- Зипперы (часть 4). Поиск в XML
- Зипперы (часть 5). Редактирование
- Зипперы (часть 6). Виртуальные деревья. Обмен валют
- Зипперы (часть 7). Обход в ширину. Улучшенный обмен валют
- Зипперы (часть 8). Заключение
Нашли ошибку? Выделите мышкой и нажмите Ctrl/⌘+Enter