Оглавление

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

До сих пор вторая функция, которую мы передавали в зиппер, возвращала потомков из ветки. Для вектора это была просто seq, для XML — более сложная комбинация (comp seq :content). Оба варианта отталкиваются от родительского узла, и если потомков нет, функция вернёт nil.

Но что если функция вернёт постоянный набор потомков:

(fn [_]
  (seq [1 2 3]))

Как поведёт себя такой зиппер? Напишем его:

(def zip-123
  (zip/zipper any?
              (constantly (seq [1 2 3]))
              nil
              1))

Из-за того, что у каждого элемента три потомка, зиппер станет бесконечным. Обойти его с помощью iter-zip не получится — zip/next будет всё глубже погружаться в зиппер, но не достигнет его конца.

Ради интереса сделаем несколько шагов по новому зипперу. Спустимся вниз и вправо. Мы окажемся на двойке в середине вектора [1 2 3]:

(def loc-2
  (-> zip-123
      zip/down
      zip/right))

(zip/node loc-2)
;; 2

Покажем наше положение не схеме. Шаги влево и право сдвинут нас на единицу и тройку:

              ┌───────────┐
              │     1     │
              └───────────┘
                    ▲
                    │
 ┌───────┐    ┏━━━━━━━━━━━┓    ┌───────┐
 │   1   │◀───┃     2     ┃───▶│   3   │
 └───────┘    ┗━━━━━━━━━━━┛    └───────┘
                    │
                    ▼
                ┌───────┐
                │[1 2 3]│
                └───────┘

С шагом вниз мы провалимся в очередной вектор [1 2 3] и так далее. Ради интереса спустимся вниз и вправо пять раз, и всё равно окажемся в двойке:

(def down-right (comp zip/right zip/down))

(-> loc-2
    down-right
    down-right
    down-right
    down-right
    down-right
    zip/node)
;; 2

Зиппер можно назвать виртуальным, потому что данных, по которым мы путешествуем, на самом деле не существует — они появляются в полёте.

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

Явно заданный вектор [1 2 3] не раскрывает их. Если потомки известны заранее, нужда в зиппере отпадает — коллекцию можно обойти более простым способом. Интересен случай, когда потомки зависят от каких-то внешних факторов, например, приходят из сторонних источников. В терминах функционального программирования зиппер становится “грязным”: поскольку мы не контролируем внешний источник, повторный обход может дать разный результат. Однако это не значит, что грязный зиппер не имеет права на жизнь. Рассматривайте его как абстракцию над источником, которая делает его удобней.

На роль примера отлично подходит файловая система. Ее элементы – файлы и директории – отвечают всем условиям зиппера. Директория – это узел, который содержит ссылки на другие элементы. Когда вы просматриваете файлы в любом менеджере, курсор ведет себя как локация. Он знает текущий файл, его соседей по директории и пути вверх и вглубь (если текущий файл – директория). Если правильно подобрать функции branch? и children, обычный файл становится зиппером.

Код оказывается на удивление коротким. Добавьте в пространство модуль clojure.zip и класс java.io.File:

(ns zipper-demo
  (:import java.io.File)
  (:require
   [clojure.zip :as zip]))

Функция file-zip принимает строковый путь и возвращает зиппер. Проверка branch? сводится к вызову метода .isDirectory файла. Очевидно, если это обычный файл, а не папка, двигаться ниже нельзя. Функция children опирается на метод .listFiles, который вернет массив файлов в директории. Обертка в seq необходима, чтобы привести пустой массив к nil.

(defn file-zip [^String path]
  (zip/zipper
   (fn [^File f] (.isDirectory f))
   (fn [^File f] (seq (.listFiles f)))
   nil
   (new File path)))

Получим зиппер проведем с ним эксперименты. Первая локация указывает на корневую папку:

(def fz
  (file-zip "/Users/ivan"))

(-> fz zip/node)
;; #object[java.io.File 0xe413375 "/Users/ivan"]

Вызов zip/next сдвигает указатель на вложенные папки и файлы. В случае автора это скрытая папка .eclipse:

(-> fz zip/next zip/node)
;; #object[java.io.File 0x23e1b67 "/Users/ivan/.eclipse"]

Через три сдвига получим файл secure_storage в ее недрах:

(-> fz zip/next zip/next zip/next zip/node)
;; #object[java.io.File 0x138b3172 "/Users/ivan/.eclipse/org.eclipse.equinox.security/secure_storage"]

Сохраним локацию в переменную и вызовем zip/path. Получим вектор папок, ведущих к файлу из локации:

(def file-loc
  (-> fz zip/next zip/next zip/next))

(zip/path file-loc)

[#object[java.io.File 0xe413375 "/Users/ivan"]
 #object[java.io.File 0x2067c8ff "/Users/ivan/.eclipse"]
 #object[java.io.File 0x69304325 "/Users/ivan/.eclipse/org.eclipse.equinox.security"]]

Файловый зиппер поддерживает iter-zip, поиск, переходы и прочие техники, что мы рассмотрели. Признаем, в случае с файлами это не самое оптимальное решение: за долгие годы для них созданы инструменты намного быстрее. Но пример подтверждает, что зиппером может выступить объект, который на первый взгляд не подходит на эту роль.

Наверное, каждый программист сталкивался с неуклюжим API, который возвращает сущности и ее потомков по одной. Например, древняя CRM по запросу GET /api/entity/<id> вернет JSON вида:

{
  "id": 3,
  "name": "Gizmo",
  "description": "Does something",
  "children": [6, 9, 11, 23]
}

Если у сущности нет потомков, в поле children пустой массив или оно отсутствует.

Чтобы обойти сущности, построим зиппер, замкнутый на API. Предположим, функция entity-by-id принимает HTTP-клиент с активным соединением и номер сущности и возвращает прочитанный JSON из тела ответа.

(defn entity-by-id [http-client entity-id]
  ...)

В этом случае зиппер выглядит как в примере ниже. Он принимает HTTP-клиент и номер корневой сущности. Функция branch? проверяет, что поле children не пустое. Функция потомков извлекает их в цикле for:

(defn entity-zip [http-client entity-id]
  (zip/zipper (fn [{:keys [children]}]
                (pos? (count children)))
              (fn [{:keys [children]}]
                (for [child children]
                  (entity-by-id http-client child)))
              nil
              (entity-by-id http-client entity-id)))

Вызывая zip/next, мы будем шагать по сущностям, извлекая их по сети по мере необходимости. Ради оптимизации можно заменить цикл for на частично параллельный pmap или применить библиотеки Aleph и Manifold для удобной многопоточности.

Когда сведения о потомках приходят по сети, важно оценить частоту запросов и нагрузку на источник данных. Если это CRM в банковской системе, ее замедление скажется на других частях компании. В этом случае данные полезно кэшировать в памяти или в key-value хранилищах типа Memcached или Redis. Зиппер, построенный на базе подобного хранилища, выглядит похоже за исключением функции entity-by-id. Изменится только его конструктор, но не принцип работы.

Еще один интересный пример – когда функции branch? и children замкнуты на некоторых данных. Это тоже обход, но по другим правилам.

Рассмотрим следующую задачу. Банк разменивает валюты, например доллары на евро, рубли на лиры и так далее. Для краткости обозначим их парами: (usd, eur), (rub, lir). Размен действует в одном направлении: чтобы поменять евро на доллары или лиры на рубли, у банка должны быть отдельные правила (eur, usd) и (lir, rub).

В банк обращается клиент, чтобы разменять валюту X на Y. Если в правилах есть пара (X, Y), проблемы не возникает. Но если пары нет, банк строит цепочку обменов. Например, клиент хочет поменять доллары на лиры, но в банке нет прямой пары (usd, lir). Однако есть пары (usd, eur) и (eur, lir). В этом случае клиенту предложат обмен usd → eur → lir.

Ваша задача — написать программу, которая принимает правила обмена, входную и выходную валюты. Вы должны найти цепочки обмена. Чем короче цепочка, тем лучше. Если возможны несколько цепочек одинаковой длины, вернуть их все, чтобы клиент мог выбирать. Учесть, что решений может не быть и адекватно реагировать на этот случай: не уйти в вечный цикл, не занимать все ресурсы компьютера.

Опишем входные данные в терминах Clojure. Каждое правило будет парой кейвордов — с какой валюты на какую происходит обмен. Вектор правил назовем rules. Кроме правил, мы принимаем параметры from и to с какой и на какую валюту менять.

;; rules
[[:usd :rub] [:rub :eur] [:eur :lir]]

:usd ;; from
:rub ;; to

На выходе ожидаем набор цепочек от from к to или nil. Для случая выше цепочка от доллара к евро выглядит так:

[:usd :rub :eur]

Всё вместе даёт функцию exchanges, тело которой нам предстоит заполнить:

(defn exchanges [rules from to]
  ...)

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

(deftest test-simple
  (is (= [[:usd :rub]]
         (exchanges [[:usd :rub]] :usd :rub))))

Обмен в обратную сторону невозможен, если нет отдельного правила:

(deftest test-reverse-err
  (is (nil? (exchanges [[:rub :usd]] :usd :rub))))

Случай, когда цепочки обмена не существует:

(deftest test-no-solution
  (is (nil? (exchanges [[:rub :usd] [:lir :eur]] :usd :eur))))

Наиболее важный сценарий: множественный обмен. От долларов к рублям ведут два пути с евро и лирами в середине:

(deftest test-two-ways
  (is (= [[:usd :eur :rub]
          [:usd :lir :rub]]
         (exchanges [[:usd :eur]
                     [:eur :rub]
                     [:usd :lir]
                     [:lir :rub]] :usd :rub))))

Ещё один тест проверяет, что вы вернём только самые короткие цепочки. Обмен с четырьмя валютами (в данном случае [:usd :yen :eur :rub]) не попадёт в результат:

(deftest test-short-ways-only
  (is (= [[:usd :eur :rub]
          [:usd :lir :rub]]
         (exchanges [[:usd :eur]
                     [:eur :rub]
                     [:usd :lir]
                     [:lir :rub]
                     [:usd :yen]
                     [:yen :eur]] :usd :rub))))

В терминах олимпиадного программирования можно сказать, что задача содержит отдельные рёбра графа. Требуется проверить, можно ли составить из рёбер маршрут от вершины А к B. Поскольку эта глава о зипперах, мы не будем использовать термины “граф” и “рёбра”. Мы не гарантируем, что решение будет оптимальным, и возможно, алгоритм на графах справится лучше. Однако надеемся, что пример ещё больше раскроет мощь зипперов.

Как вы помните, зипперы удобны там, где встречается иерархия. На первый взгляд у валют нет иерархии, но ее легко построить. Представим, что на вершине дерева стоит валюта from, которую мы хотим разменять. Пусть это будет доллар. Очевидно, что потомки этой валюты — все те, что размениваются на доллар. Для этого выберем второй элемент из каждой пары, где первый элемент равен from:

(def rules
  [[:usd :rub]
   [:usd :lir]
   [:rub :eur]
   [:rub :yen]
   [:eur :lir]
   [:lir :tug]])

(def from :usd)

(def usd-children
  (for [[v1 v2] rules
        :when (= v1 from)]
    v2))
;; (:rub :lir)

Таким образом, потомки доллара – рубль и лира. Изобразим мнимое дерево и обозначим уровни:

                  ┌───────┐
     1            │  usd  │
                  └───────┘
                      │
          ┌───────┐   │   ┌───────┐
     2    │  rub  │◀──┴──▶│  lir  │
          └───────┘       └───────┘

Для каждой валюты второго уровня найдём потомков по такому же правилу. Для удобства напишем функцию get-children:

(defn get-children [value]
  (for [[v1 v2] rules
        :when (= v1 value)]
    v2))

(get-children :rub)
;; (:eur :yen)

Новое дерево:

                      ┌───────┐
    1                 │  usd  │
                      └───────┘
                          │
              ┌───────┐   │   ┌───────┐
    2         │  rub  │◀──┴──▶│  lir  │
              └───────┘       └───────┘
                  │               │
       ┌───────┐  │  ┌───────┐    │  ┌───────┐
    3  │  eur  │◀─┴─▶│  yen  │    └─▶│  tug  │
       └───────┘     └───────┘       └───────┘

Заметим, что это виртуальное дерево, о котором мы говорили недавно. У нас нет этого дерева на руках – оно получается в процессе. Функция make-children замкнута на исходных парах обмена. Это пример того, как обходить данные, которые получаем в полёте из других данных.

Структура дерева валют известна, и его можно обойти. Вопрос, до каких пор его обходить? Очевидно, мы остановимся, как только встретим локацию, чей узел равен валюте to. Пусть это будут йены. Это значит, мы соединили from и to с помощью других валют. Обозначим решение на схеме:

                      ┌───────┐
    1                 │  usd  │
                      └───────┘
                          │
              ┌───────┐   │   ┌ ─ ─ ─ ┐
    2         │  rub  │◀──┘
              └───────┘       └ ─ ─ ─ ┘
                  │
       ┌ ─ ─ ─ ┐  │  ┌───────┐       ┌ ─ ─ ─ ┐
    3             └─▶│  yen  │
       └ ─ ─ ─ ┘     └───────┘       └ ─ ─ ─ ┘

Чтобы получить цепочку обмена, локацию to передают в функцию zip/path. Она вернёт вектор родителей локации, не включая ее саму. Путь к локации и её узел образуют цепочку обмена.

На базе этих рассуждений напишем код. Подготовим зиппер:

(def zip-val
  (zip/zipper keyword?      ;; это валюта?
              get-children  ;; на что её можно разменять?
              nil
              from))        ;; исходная валюта

Ищем в зиппере локацию с целевой валютой:

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

(def loc-to
  (->> zip-val
       iter-zip
       (find-first loc-to?)))

Если нашли, получим из неё цепочку обмена. Для этого к пути присоединим значение to:

(conj (zip/path loc-to) (zip/node loc-to))
;; [:usd :rub :yen]

Задача решена, но с недостатком: для любых данных мы получим только одну цепочку, даже если их несколько. Чтобы исправиться, ищем не только первую локацию с валютой to, а их все с помощью filter.

Расширим исходные данные:

(def rules
  [[:usd :rub]
   [:usd :lir]
   [:rub :eur]
   [:lir :yen]
   [:rub :yen]
   [:eur :lir]
   [:lir :tug]])

(def from :usd)
(def to :yen)

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

(def locs-to
  (->> zip-val
       iter-zip
       (filter loc-to?)))

Для каждой найденной локации постоим путь:

(for [loc locs-to]
  (conj (zip/path loc) (zip/node loc)))

([:usd :rub :eur :lir :yen]
 [:usd :rub :yen]
 [:usd :lir :yen])

Теперь мы нашли цепочки всех длин, что может быть избыточно. По условию задачи нам не нужен обмен из четырёх операций, если найден с двумя. Напишем функцию, которая вернёт самые короткие списки из результата выше. Она группирует обмены по длине, находит меньшую длину и выбирает из словаря.

(defn get-shortest-chains
  [chains]
  (when (seq chains)
    (let [count->chains (group-by count chains)
          min-count (apply min (keys count->chains))]
      (get count->chains min-count))))

Для последнего результата получим два вектора по три валюты в каждом. Этот случай покрывает последний тест test-short-ways-only, где длинные цепочки отбрасываются:

[[:usd :rub :yen] [:usd :lir :yen]]

Составьте функцию exchanges из фрагментов кода. Убедитесь, что тесты проходят. Добавьте в них больше случаев.

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

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

Оглавление