Clojure Zipper介绍

在本文中, 我们将讨论 Clojure 语言中的 zippers. 这是一种处理集合的不寻常方式. 使用 zipper, 你可以任意遍历数据结构, 修改其内容, 并在其中进行搜索.

Zipper 是一个强大的抽象, 其优势会随着时间的推移而显现. 然而, 它并不像常规工具那样直观, 需要一些练习才能掌握.

让我们用简单的术语来谈谈 zipper. 它是一个提供了多种数据操作的包装器. 让我们列出主要的几种:

• 垂直移动: 向下到子节点或向上到父节点;
• 水平移动: 在子节点之间向左或向右移动;
• 遍历整个数据结构;
• 添加, 编辑和删除节点.

这只是一个不完整的列表, 稍后将看到更多有趣的解决方案. 注意: 这些功能在处理任意数据时都可用, 无论是 vector 和 map 的组合, XML, 还是树.

这使得 zippers 成为一个强大的工具. 一旦弄清楚如何使用它们, 就会提升技能并打开新的大门.

zippers 内置在 Clojure基础库中无需要引入.

Clojure zippers 利用了不可变集合的强大功能. 从实现上讲, zipper 是一个 存储数据 和 指针位置 的集合. 它们一起被称为 location.

向任一方向移动一步都会返回一个新的 location, 就像 assoc 或 update 函数从旧数据生成新数据一样.

从当前 location, 可以得到一个 node, 也就是指针指向的那部分数据. 让我们澄清它们之间的区别, 以免初学者混淆.

Location 是源数据及其中的位置. 在 location 移动会生成一个新的 location. 从 location 中, 可以检索到一个 node —— 也就是这个区域中的数据.

下面是一个使用 vector [1 2 3] 的例子. 要移动到第二个元素 two, 需要将数据包装在一个 zipper 中并执行 zip/down 和 zip/right 命令.

第一步, 我们将进入 vector 并发现自己位于元素 1 上. 向右一步将我们移动到 2. 让我们用代码来表达: 引入带有别名 zip 的包并遍历该 vector.

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

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

2

链式调用这些函数将如预期般返回 2. 最后一个动作 – zip/node – 输出当前 location 的值 (一个 node).

如果我们移除 zip/node, 我们会得到一个对应于 2 的 location. 它看起来像这样:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right)
;; [2 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3)}]

[2 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3)}]

行至此处, 会有新的疑问: 当 2 可能在 vector 的其他位置时, 如何得道到 2 的路径? 如果超出了集合的范围会发生什么?

你将在下面找到这些问题的答案. 目前, 如果你有什么不清楚的地方, 不要惊慌: 我们会不止一次地澄清这里发生的一切.

所以, zipper 建议在数据中导航. 尽管它功能强大, 但它不知道如何为特定的集合执行此操作, 所以你需要教它. 除了数据, zipper 还需要回答两个问题:

• 当前元素是一个 branch 吗? 这是可以从中获取其他元素的元素的名称.
• 如果它是一个 branch, 如何从中获取 children?

这就是 zipper 导航所需要知道的全部. 注意, 要改变 zipper 本身, 你需要知道另一个问题的答案 —— 如何将 children 附加到一个 branch.

然而, 我们现在只关注导航, 所以第三个问题可以等等.

从技术上讲, 函数会给出第一个和第二个问题的答案. 第一个函数接收一个 node 并返回 true 或 false. 如果它返回 true, zipper 会调用第二个函数. 它接收相同的 node, 但应该返回一个子节点的序列, 如果不存在则返回 nil. 在代码中, 这些函数被称为 branch? 和 children.

要获得一个 zipper, 你需要告诉它输入数据和刚才描述的两个函数. 只要我们只读取 zipper, 第三个函数可以是 nil. zippers 位于 clojure.zip 包中. 将它包含到命名空间中:

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

有空的时候可以探索一下这个模块的源代码. 它只有 280 行长!

zip/zipper 函数从源数据和函数创建一个 zipper. 这是该模块的要点, 它的构建块. 对于常见情况, 该模块提供了一些预定义的 zippers, 它们只期望数据.

用于嵌套 vector 的 Vector-zip 就是一个很好的例子. 这是它的代码, 没有第三个参数:

(defn vector-zip
  [root]
  (zipper vector?
          seq
          ...
          root))

我们用三个点替换了它. 第三个参数是一个函数, 它在更改时将子节点附加到 branch (暂时忽略它). 如果你将 vector [1 2 3] 传递给 vector-zip, 会发生以下情况:

zipper 将包装该 vector 并暴露一个指向它的指针. 从起始位置, 你只能向下遍历, 因为在顶部 zipper 没有父节点 (up) 和邻居 (left 和 right).

当向下导航时, zipper 首先检查当前 node 是否是 branch. 这会触发表达式 (vector? [1 2 3]), 其计算结果为 true. 在这种情况下, zipper 将执行 (seq [1 2 3]) 来获取 children.

它们将是序列 (1 2 3). 一旦找到 children, zipper 会将指针设置到最左边的 child – 1.

让我们在图表中展示这一点. 起始位置, 指针在源 vector 上:

      nil
       ^
       |
nil <- [1 2 3] -> nil
       |
       v

向下移动, 指针在 1 上:

    [1 2 3]
       ^
       |
nil <- 1 -> 2
       |
       v
      nil

向右移动, 指针在 2 上:

  [1 2 3]
     ^
     |
1 <- 2 -> 3
     |
     v
    nil

所以, 我们在 2 上, 可以水平移动. 向右一步将我们移动到 3, 向左 – 到 1. 在代码中, 它看起来像这样:

(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

当尝试向下移动时, zipper 将执行 (vector? 2) 谓词. 结果将是 false, 这意味着当前元素不是一个 branch, 不允许向下移动.

遍历时请记住以下内容. 每一步都会创建一个新的 location 而不改变旧的. 如果将任何特定的 location 保存在一个变量中, 后续对 zip/right, zip/down 等的调用不会以任何方式改变它.

上面, 我们声明了 loc2 变量, 它指向 2. 你可以用它来获取源 vector.

(-> loc2 zip/up zip/node)
;; [1 2 3]

如果手动移动, 很有可能会超出集合的范围. 移动到无处将返回 nil 而不是一个 location:

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

nil

这是一个信号, 表明走错了路. 坏消息是, 不能从 nil 返回. nil 表示一个空的 location, 并且其中没有对前一步的引用.

zip/up, zip/right 和其他函数对空 location 也返回 nil. 如果在一个循环中迭代并且不考虑这一点, 最终只会原地打转.

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

zip/down 函数是一个例外: 如果你尝试从 nil 下降, 你会得到一个 NullPointerException 错误. 这是一个轻微的缺陷, 可能会在某一天被修复.

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

让我们看一个更复杂的 vector. 它的一个 child 是另一个 vector - [1 [2 3] 4]. 要将指针移动到 3, 执行 down, right, down, 和 right 的步骤. 将一个 location 存储在一个变量中:

(def loc3
  (-> [1 [2 3] 4]
      zip/vector-zip
      zip/down
      zip/right
      zip/down
      zip/right))

(zip/node loc3)
3

3

下面的图片显示了每一步发生的事情. 起始位置:

      nil
       ^
       |
nil <- [1 [2 3] 4] -> nil
       |
       v
       1

向下移动:

  [1 [2 3] 4]
       ^
       |
nil <- 1 -> [2 3]
       |
       v
      nil

向右:

[1 [2 3] 4]
     ^
     |
1 <- [2 3] -> 4
     |
     v
     2

向下:

     [2 3]
       ^
       |
nil <- 2 -> 3
       |
       v
      nil

向右. 到达了我们的目标:

   [2 3]
     ^
     |
2 <- 3 -> nil
     |
     v
    nil

要从当前位置移动到 4, 你首先需要向上走. 指针将移动到 vector [2 3]. 现在我们在原始 vector 的 children 中, 可以水平移动. 让我们向右走一步, 找到数字 4.

以下是图形化显示的相同操作. 当前 location (即 3):

   [2 3]
     ^
     |
2 <- 3 -> nil
     |
     v
    nil

向上:

[1 [2 3] 4]
     ^
     |
1 <- [2 3] -> 4
     |
     v
     2

向右:

  [1 [2 3] 4]
       ^
       |
[2 3] <- 4 -> nil
       |
       v
      nil

原始 vector 可以是任意嵌套的. 作为一个练习, 将 3 替换为另一个 vector 并进入它.

如果你向 vector-zip 传递一个 vector 以外的东西会发生什么? 例如, 它可能是一个字符串, nil, 或一个数字. 在遍历之前, zipper 会检查该 node 是否是一个 branch 以及它是否有子节点. 对于 vector-zip, 它使用 vector? 函数检查数据, 该函数对所有非 vector 值返回 nil. 结果, 我们得到一个无法移动到任何地方的 location: 既不能向下也不能横向. 必须避免这种死胡同.

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

clojure.zip 模块还提供了其他内置的 zippers. xml-zip 对于导航 XML 树特别有趣. 当你了解其他 zipper 功能时, 我们将单独讨论它.

弄清楚了如何通过集合进行导航之后, 要搞清楚路径是如何走的, 如何提前知道该往哪个方向走?

本节的主要信息是: 手动数据导航没有意义. 如果你事先知道路径, 你就不需要 zipper.

对于结构事先已知的数据, Clojure 提供了更简单的工作方式. 例如, 如果我们确定输入数据结构是一个 vector, 并且它的第二个元素是另一个 vector, 我们将使用 get-in:

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

(get-in data [1 1])

3

其他数据类型也是如此. 列表和 map 的组合方式无关紧要. 如果结构是已知的, 你需要的数据可以很容易地用 get-in 或线程宏来达到. 在这种情况下, zippers 只会使代码复杂化.

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

(-> data :users first :name)

Ivan

zippers 的优势是什么? 它们的优势在 get-in 无法工作的场景中体现出来. 这涉及到具有未知结构的数据. 假设输入是一个任意的 vector, 你需要在其中找到一个字符串.

例如, 它可能在第一个嵌套级别, 或者在第三个, 等等. 另一个例子是 XML 文档. 所需的标签可以位于其中的任何位置, 但你需要以某种方式找到它. 简而言之, zipper 的理想情况是一个我们只能猜测其结构的模糊数据结构.

zip/up, zip/down 等函数共同构成了通用函数 zip/next. 它移动指针, 以便我们迟早会遍历整个结构. 遍历时, 重复会被排除: 我们每个地方只访问一次. 这是一个使用 vector 的例子:

(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).

对于一个 zipper, 我们得到初始 location, 然后从中得到 zip/next, 再从前一次移动中得到 zip/next, 依此类推.

下面, loc-seq 变量是源 zipper 的 location 链. 为了得到 nodes, 我们取前六个元素 (我们随机取的数量) 并为每个元素调用 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, 否则 location 流将永不结束.

此外, 在某个时刻, zip/next 停止移动指针. 以迭代的第一百个和第一千个元素为例. 它们的 node 将是初始 vector:

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

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

原因在于 zipper 遍历的工作方式. zip/next 函数的行为像一个环. 当它到达初始 location 时, 循环结束.

在这种情况下, 该 location 将获得一个完成标志, 下一次调用 zip/next 将返回相同的 location. 你可以使用 zip/end? 函数检查标志是否存在:

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

[loc-end (zip/end? loc-end)]

[[[1 2 3] :end] true]

为了创建有限的 location 链, 我们将一直移动指针, 直到得到最后一个 location. 总之, 这给出了以下函数:

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

#'user/iter-zip

此函数返回数据结构中的所有 locations. 回想一下, 一个 location 存储一个 node (一个数据元素), 我们可以使用 zip/node 获取它. 下面的例子展示了如何将 locations 转换为数据:

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

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

有了一个 location 链之后写一个搜索. 假设想检查 vector 是否包含 :error 关键字. 首先, 让我们为 location 写一个谓词, 以了解其 node 是否等于此值.

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

#'user/loc-error?

好了, 让我们检查一下 location 链中是否有一个与我们的谓词匹配的. 为此, 调用 some:

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

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

true

注意: 由于惰性, 没有扫描整个树. 如果所需的 node 出现在中间, iter-zip 会结束迭代并停止进行调用, 后续的 zip/next 调用也不会发生.

zip/next 以深度优先的顺序遍历树是很有用的. 在移动时, 它倾向于向下或向右, 但只有在这些方向的步骤返回 nil 时才向上.

有时遍历顺序很重要. 有些任务我们必须以广度优先的方式遍历. clojure.zip 中没有其他默认的遍历选项, 但可以轻松地编写自己的. 稍后会看一个需要广度遍历的任务.

内置的 vector-zip zipper 用于嵌套的 vectors. 但嵌套的 maps 更为常见. 让我们写一个 zipper 来遍历这类数据:

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

以熟悉的 vector-zip 为基础. 这些 zippers 是相似的, 唯一的区别是它们处理的集合类型. 让我们思考如何定义回答问题的函数.

map 是一个 branch, 其 children 是 MapEntry 元素. 这种类型表示一个键值对. 如果值是一个 map, 我们会从中得到一个嵌套的 MapEntry 链, 依此类推.

先写一个检查 MapEntry 类型的谓词:

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

#'user/entry?

map-zip zipper 看起来像这样:

(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))

#'user/map-zip

(some-fn ...) 组合在其中一个谓词参数为真时返回 true. 换句话说, 我们只把 map 或其 entry (键值对) 视为一个 branch.

在第二个寻找 children 的函数中, 我们必须检查一些条件. 如果当前值是一个 map, 我们使用 seq 函数返回一个 map entries 的序列.

如果我们已经在 MapEntry 中, 那么检查值是否是一个嵌套的 map. 如果是, 我们应该用相同的 seq 函数获取它的 children.

遍历树时, 我们会得到所有的键值对. 如果值是一个嵌套的字典, 我们在遍历时会进入它. 这是一个例子:

(->> {: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"])

注意 iter-zip 之后的 rest 函数. 我们跳过了包含原始数据的第一个 location. 因为它们已经是已知的, 打印它们没有意义.

使用我们的 map-zip, 我们可以检查 map 是否包含键 :error 和值 :auth. 这些关键字中的每一个都可以在任何地方, 无论是在键中还是在任何级别的值中.

然而, 我们感兴趣的是它们的组合. 为此, 让我们写一个谓词:

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

#'user/loc-err-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 zipper 忽略了 map key 是另一个 map 的情况. 例如:

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

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

   这种集合虽然很少见, 但有时也会使用. 修改 map-zip 使其不仅检查 MapEntry 的值, 还检查键.

2. 在实践中, 我们使用 vector 和 map 的组合. 编写一个通用的 zipper, 在遍历时同时考虑 map 和 vector.

zippers 的威力在处理 XML 时得以充分展现. 与其他格式不同, 它是递归指定的. 例如, JSON, YAML 和其他格式提供了具有不同语法和结构的数据类型 (数字, 字符串, 集合).

在 XML 中, 无论我们在哪里, 当前节点总是由三个部分组成: 标签, 属性和内容. 内容是一组字符串或其他节点. 这是一个递归的伪代码表示法:

XML = [Tag, Attrs, [String|XML]]

为确保 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>

在 XML 的顶层是 catalog 节点. 它只是一个分组标签; 我们需要它, 因为顶层不能有多个标签. catalog 的 children 是 organizations. organization 的 name 属性包含其名称.

Products 在 organization 下面. 一个 product 是一个带有 product 标签和产品类型描述的节点. 它没有 children, 而是有文本内容 —— 它的描述. 不可能再向下进入 product.

Clojure 提供了一个 XML 解析器, 它返回一个类似于上面 [Tag, Attrs, Content] 模式的结构. 每个节点都变成一个带有键 :tag, :attrs 和 :content 的 map.

:content 键存储一个 vector, 其中元素要么是字符串, 要么是嵌套的 map.

我们将带有 products 的 XML 数据放在 resources/products.xml 文件中. 让我们写一个函数将文件解析成一个 XML zipper. 添加模块导入:

(require '[clojure.java.io :as io])
(require '[clojure.xml :as xml])

nil

两者都随 Clojure 一起提供, 因此不需要依赖. 为了得到 zipper, 我们将 path 参数通过一系列函数传递:

(defn ->xml-zipper [path]
  (-> path
      io/file
      xml/parse
      zip/xml-zip))

(->xml-zipper "/tmp/product.xml")

[{:tag :catalog,
  :attrs nil,
  :content
  [{:tag :organization,
    :attrs {:name "re-Store"},
    :content
    [{:tag :product,
      :attrs {:type "iphone"},
      :content ["iPhone 11 Pro"]}
     {:tag :product, :attrs {:type "iphone"}, :content ["iPhone SE"]}]}
   {:tag :organization,
    :attrs {:name "DNS"},
    :content
    [{:tag :product, :attrs {:type "tablet"}, :content ["iPad 3"]}
     {:tag :product,
      :attrs {:type "notebook"},
      :content ["Macbook Pro"]}]}]}
 nil]

xml/parse 函数应该返回一个由带有键 :tag, :attrs 和 :content 的 map 组成的嵌套结构. 请注意, 文本内容, 如产品名称, 也是一个带有一个字符串的 vector. 这实现了每个节点的同构性.

这是我们调用 xml/parse 后应该得到的结果:

{:tag :catalog
 :attrs nil
 :content
 [{:tag :organization
   :attrs {:name "re-Store"}
   :content
   [{:tag :product
     :attrs {:type "iphone"}
     :content ["iPhone 11 Pro"]}
    {:tag :product :attrs {:type "iphone"} :content ["iPhone SE"]}]}
  {:tag :organization
   :attrs {:name "DNS"}
   :content
   [{:tag :product :attrs {:type "tablet"} :content ["iPad 3"]}
    {:tag :product
     :attrs {:type "notebook"}
     :content ["Macbook Pro"]}]}]}

调用 (->xml-zipper "products.xml") 从上面的数据创建 XML zipper 的初始 location. 首先, 让我们看一下 xml-zip 的定义来理解它是如何工作的. 这里我们展示代码摘录:

(defn xml-zip
  [root]
  (zipper (complement string?)
          (comp seq :content)
          ...
          root))

正如你可能猜到的, 节点的 children 是它的 :content, 额外用 seq 包装. 字符串不能有 children, 所以 (complement string?) 的意思是 - 只在非字符串节点中搜索 children.

看看我们如何从给定的 XML 中找到所有 products. 首先, 让我们对它的 zipper 进行一次惰性迭代. 回想一下, 在每一步我们得到的不是一个带有 :tag 和其他字段的 map, 而是一个带有指向它的指针的 zip location.

剩下的只是过滤掉那些节点包含 product 标签的 locations. 为此, 让我们写一个谓词:

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

#'user/loc-product?

(def loc->product (comp first :content zip/node))

#'user/loc->product

再写一个转换选择:

(->> "/tmp/product.xml"
     ->xml-zipper
     iter-zip
     (filter loc-product?)
     (map loc->product))

("iPhone 11 Pro" "iPhone SE" "iPad 3" "Macbook Pro")

乍一看, 这里没有什么特别的. XML 结构是预先知道的, 所以我们可以在没有 zipper 的情况下做到. 让我们选择 catalog 的 children 并得到 organizations, 然后我们将得到 organizations 的 children (即, goods). 这是这个简单的代码:

(def xml-data
  (-> "/tmp/product.xml"
       io/file
      xml/parse))

(def orgs
  (:content xml-data))

(def products
  (mapcat :content orgs))

@(def product-names
  (mapcat :content products))

("iPhone 11 Pro" "iPhone SE" "iPad 3" "Macbook Pro")

为了使代码更简洁, 你可以移除中间变量并将其缩小为一种形式:

(->> "/tmp/product.xml"
     io/file
     xml/parse
     :content
     (mapcat :content)
     (mapcat :content))

("iPhone 11 Pro" "iPhone SE" "iPad 3" "Macbook Pro")

在实践中, XML 的结构总是在变化. 假设一个超大型经销商按分支分解产品. 在这种情况下, XML 看起来像这样 (一个片段):

<organization name="DNS">
  <branch name="Office 1">
    <product type="tablet">iPad 3</product>
    <product type="notebook">Macbook Pro</product>
  </branch>
  <branch name="Office 2">
    <product type="tablet">iPad 4</product>
    <product type="phone">Samsung A6+</product>
  </branch>
</organization>

上面那段只按层级选择数据的代码将不再工作. 如果我们对新的 XML 运行它, 我们会得到一个 branch 节点和 products 一起:

("iPhone 11 Pro"
 "iPhone SE"
 {:tag :branch, :attrs {:name "Office 1"}, ...})

如果我们使用 zipper, 它将只返回 products, 包括那些来自 branch 的:

(->> "/tmp/products-branch.xml"
     ->xml-zipper
     iter-zip
     (filter loc-product?)
     (map loc->product))

("iPad 3" "Macbook Pro" "iPad 4" "Samsung A6+")

显然, 使用能同时处理两种 XML 的代码是有益的, 而不是为大型经销商维护一个单独的版本. 在后一种情况下, 你必须存储标志, 哪个供应商是普通的, 哪个是大型的, 并及时更新它.

然而, 这个例子并没有涵盖 zippers 的全部能力. 核心 Clojure 模块中的 xml-seq 函数也提供了 XML 遍历. 该函数以相同的形式 (一个带有 :tag, :attr 和 :content 的 map) 返回一个 XML 节点的惰性序列.

Xml-seq 是更抽象的 tree-seq 函数的一个特例. 后者类似于 zipper, 因为它接受类似的函数来确定一个节点是否可以是一个 branch 以及如何获取它的 children. 正如你从代码中看到的, xml-seq 和 xml-zip 的定义是相似的:

(defn xml-seq
  [root]
  (tree-seq
   (complement string?)
   (comp seq :content)
   root))

#'user/xml-seq

zipper 和 tree-seq 之间的区别在于, 迭代时, zipper 返回一个 location – 一个更抽象和信息更丰富的元素. 相反, tree-seq 在迭代期间产生未包装的元素.

对于普通的搜索, tree-seq 甚至更可取, 因为它不会产生不必要的抽象. 考虑到分支的商品选择看起来像这样:

(defn node-product? [node]
  (some-> node :tag (= :product)))

(->> "/tmp/products-branch.xml"
     io/file
     xml/parse
     xml-seq
     (filter node-product?)
     (mapcat :content))

("iPad 3" "Macbook Pro" "iPad 4" "Samsung A6+")

回到 zippers, 让我们选择一个 tree-seq 失去其优势的问题. 手动搜索就是这样一个任务.

假设我们需要从一个带有 products 的 XML 中选择销售 iPhones 的商店. 注意: 这是我们第一次接触到节点之间的关系.

这很重要! 单独选择数据很容易. 商店是具有 organization 标签的 locations. iPhones 是具有 product 标签和 type="iphone" 属性的节点的 locations. 但是如何找到它们之间的关系呢?

上一次, 我们使用 xml-seq 将 XML 分解成一个序列. 问题是该函数返回一个没有关系的节点集合, 这阻碍了我们解决我们的任务. 让我们用一个例子来展示这一点: 首先, 让我们得到一个节点链:

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

#'user/xml-nodes

假设我们想要的产品在其中一个元素中. 例如, 我们将在第三个 (从零开始的第二个) 节点中找到一个 iPhone:

(-> xml-nodes (nth 2))

{:tag :product, :attrs {:type "tablet"}, :content ["iPad 3"]}

然而, 很难找出它来自哪家商店. 你可以猜测商店在产品的左边, 因为在遍历树时, 它在产品之前. 如果你打印节点标签, 这就变得很清楚:

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

这是一个或多或少正确的假设, 但你不应该过于依赖它, 因为结果取决于 XML 遍历的顺序. 此外, 解决问题变得更加复杂.

遍历时, 你不仅需要选择所需的产品, 还要向后移动以寻找商店. 然后你将不得不再次向前移动, 跳过已找到的产品, 否则会陷入一个无限循环. 这种方法是状态化的, 在命令式语言中工作得很好, 但在 Clojure 中不行.

这就是 zipper 发挥作用的地方. 它在每一步返回的 location 会记住它在结构中的位置. 这意味着我们可以使用我们在第一部分讨论过的函数 zip/up, zip/right 等从该 location 导航到所需的地方. 在这种情况下, 使用手动导航是合理的.

让我们回到具有简单 catalog-organization-products 结构的 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>

首先, 让我们找到 iPhones-locations 并为 iPhone 编写谓词:

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

#'user/loc-iphone?

获取带有 iPhones 的 locations:

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

(count loc-iphones)

2

现在, 要通过 product 找到一个 organization, 只需使用 zip/up 向上移动一级. 这是正确的, 因为 organization 是 product 的父级:

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

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

对于每个 iPhone, 我们应该得到销售它的 organization. 我们得到重复项, 因为两款 iPhone 都在 re:Store 商店销售. 为了使结果唯一, 将其包装在 set 中.

(set loc-orgs)

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

这就是问题的答案: iPhones 可以在 re:Store 购买. 如果向 DNS organization 添加一个 iPhone, 后者也会出现在 loc-orgs 中.

让我们为带有 branches 的 XML 解决同样的问题. 现在我们不能在 product 上调用 zip/up 来得到 organization, 因为在某些情况下我们会得到一个 branch, 这将需要再向上一步.

为了不猜测要向上走多少步, 让我们写一个函数 loc->org. 它会一直向上走, 直到我们找到所需的标签:

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

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

#'user/loc->org

find-first 实用函数找到与谓词匹配的第一个集合元素. 我们将不止一次地使用这个函数.

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

#'user/find-first

为了缩短代码, 我们不会声明变量 loc-iphones 等. 让我们用一种形式来表达搜索:

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

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

在新的解决方案中, 我们用一个更复杂的攀升算法的函数替换了 zip/up. 否则, 一切都没有改变.

注意 XML 对于搜索和导航是多么方便. 如果我们用 JSON 存储数据, 它是列表和字典的组合, 带有和不带 branches 的版本是不同的.

这里是没有 branch 商店的产品:

[{"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 4"},
                             {"type": "notebook", "name": "Samsung A6+"}]}]}]

不言而喻, 遍历这些结构需要不同的代码. 在 XML 的情况下, 其结构是同构的: 添加一个 branch 只改变了商品嵌套的深度, 但遍历规则保持不变.

让我们把问题要求复杂化: 在单个产品中存在产品捆绑包. 捆绑产品不能单独购买. 例如, 屏幕清洁湿巾通常与设备一起出售. 他们要求我们找到一个单独出售湿巾的商店.

这是一个例子:

<?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")))

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

("VIP Fiber Plus" "Premium iFiber")

让我们开始解决问题. 首先, 我们像上面一样找到所有的湿巾. 然后我们切掉那些包含在捆绑包中的. 在 zipper 的术语中, 这意味着这个 location 的父级没有 :bundle 标签. 之后, 我们从剩余的湿巾移动到商店.

loc-in-bundle? 谓词检查一个 location 是否包含在捆绑包中:

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

#'user/loc-in-bundle?

最终的解决方案:

(->> "/tmp/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 商店没有包含在结果中, 因为它只在捆绑包中销售湿巾.

新的复杂情况: 我们想买一个 iPhone, 但 只在与湿巾捆绑的包中. 你应该引导买家去哪家商店?

解决方案: 首先, 寻找所有的 iPhones. 只选择那些存在于捆绑包中的. 接下来, 我们在 iPhone 的邻居中寻找湿巾. 如果找到了, 从 iPhone 或湿巾向上走到商店.

这个搜索所需的大部分函数已经准备好了: 这些是检查捆绑包, 产品类型和其他小东西的谓词. 但我们还没有考虑如何获取 location 的邻居.

函数 zip/lefts 和 zip/rights 返回当前 location 左边和右边的 nodes. 如果我们 concat 它们, 我们会得到所有的邻居 (也称为 peers):

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

#'user/node-neighbors

注意: 这些是 nodes, 不是 locations. 让我们用一个 vector 快速检查一下:

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

(1 3)

zipper 的设计方式使得获取左右节点比将 location 向左或向右移动更容易. 因此, 在寻找邻居时, 最好使用 nodes (值) 而不是 locations.

让我们添加函数来检查是否有与该 location 相邻的湿巾:

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

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

#'user/with-fiber?

这是最终的表达式:

(->> "/tmp/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 商店, 因为它销售包括 iPhone 和湿巾在内的捆绑包. 这两种产品在 re:Store 都有售, 但是是分开的.

这不适合我们. 如果我们用耳机替换捆绑包中的湿巾, 我们将得不到商店.

最后, 我们可以添加新的约束. 例如, 从找到的商店中, 选择那些位于距离顾客 300 米半径范围内的.

为此, 我们需要地图上的商店位置和一个检查一个点是否在一个圆内的函数. 你只能选择营业的商店或那些提供送货服务的商店. 让我们把这些特性写入 organizations 的属性并添加选择函数.

我们的 XML zipper 已经变得像一个数据库了. 它为复杂查询提供答案, 同时, 代码的增长速度比语义负载慢.

由于其规则的结构, XML 是高度可遍历的, 而 zippers 进一步增强了这一属性. 请注意节点之间方便的转换和关系. 想象一下将数据拆分成表格并用许多 JOIN 构建 SQL 查询所付出的努力.

当然, 与真正的数据库相比, XML 有一个缺点: 它没有索引, 只有线性搜索在其中工作, 而不是二叉树搜索. 此外, 在我们的方法中, 所有数据都在内存中. 对于拥有数百万条记录的非常大的文档, 它不会工作得很好, 但我们暂时不关心这个问题.

到目前为止, 我们忽略了 zipper 的另一个可能性. 在遍历过程中, 你不仅可以解析, 还可以改变 locations. 从广义上讲, 所有我们从 web 开发中熟悉的 CRUD (Create, Read, Update, Delete) 操作都可供我们使用. 下面我们将讨论它们在 zippers 中是如何工作的.

你还记得, zipper 接受第三个函数 — make-node. 到目前为止, 我们一直传递 nil 给它. 我们没有使用它, 因为我们只读取数据. 当我们要求返回对 locations 所做的更改的数据时, zipper 将调用该函数. 该函数接受两个参数: 一个 branch 和 children. 它的任务是以树中习惯的方式将它们关联起来.

对于像 vector 这样的简单集合, 函数很简单. 它只是将 children 包装在 vec 中以从序列中获取一个 vector. 在 vector-zip 中, 函数稍微复杂一些, 因为它考虑了元数据. 这是这个 zipper 的全部代码.

(defn vector-zip
  [root]
  (zipper vector?
          seq
          (fn [node children]
            (with-meta (vec children) (meta node)))
          root))

你看到新的 vector (形式 (vec children)) 复制了旧 vector (变量 node) 的元数据. 如果你用 assoc 或 conj 补充原始 vector, 元数据会被保留. 在 vector-zip 的情况下, 我们正在构建一个新的 vector, 所以我们用 with-meta 包装它. 如果我们移除 with-meta, 输出将是一个没有元数据的 vector, 这可能会影响程序逻辑.

XML zipper 的构建略有不同: children 在 :content 字段中. (译者注: 原文代码不完整, 此处补全)

(fn [node children]
  (assoc node :content (and children (apply vector children))))

对于我们一开始开发的 zipper map-zip, 构建函数看起来会像 assoc 或 into 与 MapEntry 对的集合.

如果 zipper 找到了修改过的节点, 它会隐式调用这个函数. 函数 zip/edit, zip/replace 和其他函数用于修改. 在看它们之前, 让我们确切地讨论一下修改是如何在 zippers 内部发生的.

这些更改是特定的, 因为它们影响 locations, 而不是源数据. 在你处理了一个 location 之后, 它会被标记上 :changed? 标志. 这是一个使用 zip/root 函数重新构建数据的信号, 我们稍后会讨论.

让我们看一个使用 vector [1 2 3] 的例子. 移动到 2 并使用 zip/edit 函数将其加倍. 它接受一个 location, 一个函数和剩余的参数. 你从关于 atoms (swap!) 和 collections (update) 的主题中熟悉这种方法. 与它们类似, location 将收到一个新值, 这个值是函数根据前一个值计算出来的.

这是更改前的 location:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right)
[2 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3)}]

现在, 这是更改后的 location: 注意 :changed? 键:

(def loc-2
  (-> [1 2 3]
      zip/vector-zip
      zip/down
      zip/right
      (zip/edit * 2)))
[4 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3), :changed? true}]

接下来, 我们希望得到修改后的 vector [1 4 3]. 让我们手动来做:

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

zip/root 函数接受带有更改的 location 并做同样的事情. 它的算法看起来像这样:

• 上升到根 location;
• 返回一个 node.

为了在一次传递中得到结果, 在线程宏的末尾添加 zip/root:

(-> [1 2 3]
    zip/vector-zip
    zip/down
    zip/right
    (zip/edit * 2)
    zip/root)
;; [1 4 3]

我们手动或在 zip/root 中隐式调用的 zip/up 函数完成了大部分工作. 向上移动时, 它会检查 location 是否已更改, 如果是, 就用 make-node 重建它. 这是其代码的片段: (译者注: 原文代码不完整, 仅为示意)

(defn up
  [loc]
  (let [[node { ... changed? :changed? :as path}] loc]
    (when pnodes
      (let [pnode (peek pnodes)]
        (with-meta (if changed?
                     [(make-node loc pnode (concat l ...))
                      (and ppath (assoc ...))]
                     [pnode ppath])
                   (meta loc))))))

我们希望理论和例子足以开始试验 zippers. 我们提请你注意一个不寻常的例子.

到目前为止, 我们传递给 zipper 的第二个函数从一个 branch 返回 children. 对于 vector, 我们使用 seq, 对于 XML, 我们使用更复杂的组合 (comp seq :content). 这两种选择都取决于父节点, 如果没有 children, 函数返回 nil.

但是如果函数返回一个固定的 children 集合会发生什么:

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

这样的 zipper 会如何表现? 让我们写一下:

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

由于每个元素都有三个 children, zipper 将变得无限. 使用 iter-zip 遍历它行不通. Zip/next 会越来越深地陷入 zipper, 但永远不会到达终点.

为了好玩, 让我们在新 zipper 上走几步. 让我们向下然后向右. 我们会发现自己在 vector [1 2 3] 中间的 2 上:

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

(zip/node loc-2)
;; 2

让我们在图上看看我们的位置. 向左一步将我们移动到 1, 向右一步 —— 到 3:

      1
      ^
      |
1 <-  2 -> 3
      |
      v
  [1 2 3]

向下走, 我们会进入下一个 vector [1 2 3], 依此类推. 让我们再向下和向右五次, 仍然会停在 2:

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

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

这个 zipper 可以被称为虚拟的, 因为我们遍历的数据并不真正存在 —— 它们是动态出现的.

这个 zipper 的用途还有待观察. 然而, 它证实了一个重要的论点, 即你可以在遍历树的过程中获得子节点. 这不违反 zipper 规则, 并提供了新的机会.

然而, 显式指定的 vector [1 2 3] 并没有暴露它们. 如果 children 是预先知道的, 就不需要 zipper, 因为可以用更简单的方式遍历集合. 一个合适的案例是当 children 依赖于一些外部因素时. 例如, branch? 和 children 函数都依赖于其他集合和数据. 这也是一种遍历, 但根据不同的规则.

让我们看下面的问题. 一家银行兑换货币, 例如, 美元换欧元, 卢布换里拉, 等等. 为简洁起见, 让我们用对来表示它们: (usd, eur) 和 (rub, lir). 兑换是单向的. 要将欧元兑换成美元或里拉兑换成卢布, 银行必须有单独的规则 (eur, usd) 和 (lir, rub).

客户联系银行将货币 X 兑换成 Y. 如果在兑换规则中有一对 (X, Y), 就没问题. 但如果没有这样的对, 银行必须构建一个兑换链. 例如, 客户想将美元兑换成里拉, 但银行没有直接的对 (usd, lir). 然而, 有对 (usd, eur) 和 (eur, lir).

在这种情况下, 客户将被提供兑换 usd -> eur -> lir.

编写一个接受兑换规则以及输入和输出货币的程序. 你必须找到兑换链. 链越短越好. 如果可能有多条相同长度的链, 返回所有这些链, 以便客户可以选择. 考虑没有解决方案的情况, 并提供一个适当的响应, 以免陷入永恒循环, 不占用所有计算机资源.

让我们用 Clojure 的术语来描述输入数据. 每个规则都是一个包含两个关键字的 vector – 哪种货币兑换成哪种. 规则的 vector 将被称为 rules. 除了规则, 我们还接受参数 from 和 to – 这些参数指示要从哪种货币兑换到哪种货币.

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

:usd ;; from
:lir ;; to

输出应该是一组从 from 到 to 的链, 或者 nil. 对于上面的情况, 从美元到里拉的链看起来像这样:

[:usd :rub :eur :lir]

所有这些加在一起就得到了函数 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 :lir))))

最重要的场景是多重兑换. 你可以通过两种方式从美元换到卢布 – 中间使用欧元或里拉:

(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]
                     [:eur :rub]] :usd :rub))))

在竞争性编程方面, 我们可以说这个问题提供了图的单独边. 需要检查是否可能从顶点 A 到 B 构建一条连续的路径. 但由于我们正在用 zippers 解决问题, 我们不会使用术语“图”和“边”. 我们不保证解决方案将是最优的 —— 也许图算法会做得更好. 然而, 我们希望这个例子能进一步揭示 zippers 的威力.

你还记得, zippers 用于遍历树, 这包含在问题陈述中. 假设我们要兑换的 from 货币在树的根节点. 让它成为美元. 显然, 这种货币的 children 是所有可以兑换成美元的货币. 为此, 从每对中选择第二个元素, 其中第一个元素是 :usd:

(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)

在我们的例子中, 美元的 children 是卢布和里拉. 让我们画一棵想象中的树并标记层级:

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 货币的 location 时立即停止. 让它成为日元. 也就是说, 我们已经使用其他货币连接了 from 和 to.

让我们在图上展示解决方案:

usd
 |
rub
 |
yen

为了得到兑换链, 我们将 to location 传递给 zip/path 函数. 它应该返回该 location 所有父节点的 vector, 不包括其自身. 所以, 到该 location 的路径及其节点构成了一个兑换链.

我们将基于这个推理编写代码. 让我们准备一个 zipper:

(def zip-val
  (zip/zipper keyword?         ;; is it currency?
              get-children     ;; what can it be exchanged for?
              nil
              from))           ;; original currency

在 zipper 中寻找带有目标货币的 location:

(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 货币的 location, 而是使用 filter 搜索所有.

让我们扩展初始数据:

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

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

并找到链. 为此, 用 filter 替换 find-first, 它应该返回所有匹配谓词的元素.

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

对于找到的每个 location, 让我们构建一个路径:

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

现在我们找到了任意长度的链, 这可能是多余的. 根据问题陈述, 如果我们用两次操作找到一个兑换, 我们就拒绝一个四次操作的兑换. 让我们写一个函数, 从上面的结果中返回最短的列表. 它按长度对兑换进行分组, 找到最短的一个, 并从一个 map 中选择它.

(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))))

对于最后一个结果, 我们得到两个每个包含三种货币的 vectors. 最后一个测试 test-short-ways-only, 其中长链被丢弃, 涵盖了这种情况:

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

从代码片段构建 exchanges 函数. 确保所有测试都通过. 向它们添加更多案例.

问题似乎已经解决了, 但你可以改进解决方案. 事实上, 对于某些输入数据, 树可能会变得无限. 程序要么会进入一个无限循环, 要么在有限的步数内找不到解决方案. 试着猜测可能导致这个问题的原因以及如何解决它. 在下一节中, 你会找到这些问题的答案.

之前, 我们使用货币树来寻找兑换链. 我们解决了问题, 但提到在特殊情况下树可能会变得无限. 这怎么可能? 让我们记住 zip/next 是如何遍历树的.

该算法被称为深度优先. 通过这种遍历, 代码首先向下走, 然后才向侧面走 (在我们的例子中, 是向右). 如果你使用 zipper 将数据分解成部分, 这很容易看到:

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

在 4 之前的数字 3 意味着 zipper 首先深入 (在 vector [3] 内部), 然后才向右.

更有趣的是一个简单的虚拟树的情况, 其中每个节点都有 children [1 2 3]. 当遍历这样的树时, zipper 会倾向于向下, 每次都下降到下一个 vector [1 2 3] 中并在 1 处停止. 让我们在图表中展示这一点:

[1 2 3]
   |
[1 2 3]
   |
[1 2 3]
   |
  ...

由于我们的 zipper 中没有条件来停止子节点的产生, 它们的嵌套是无限的. iter-zip 函数返回一个无限的 location 链, 每个都包含 1. 我们从中取多少个“1”都无关紧要 —— 一百个或一千个 —— 我们得到相同数量的“1”.

(->> zip-123
     iter-zip
     (take 10)
     (map zip/node))
;; (1 1 1 1 1 1 1 1 1 1)

现在让我们回到货币兑换. 假设一家银行将卢布兑换成美元, 美元兑换成欧元, 欧元兑换成卢布. 让我们用代码来表达:

(def rules
  [[:rub :usd]
   [:usd :eur]
   [:eur :rub]])

如你所见, 我们有一个恶性循环:

rub -> usd -> eur
 ^            |
 |------------+

之前的解决方案忽略了规则的周期性, 这是它的缺点. 假设一个客户想将卢布兑换成里拉. 让我们从卢布开始构建一棵树. 这是链的开始:

rub
 |
usd
 |
eur
 |
rub

所以我们又回到了卢布. 对于它, 我们又得到了美元, 对于美元是欧元, 然后是卢布. 如果我们继续迭代, 我们会无休止地陷入这个链条.

逻辑告诉我们, 如果下一个货币等于初始货币, 你需要停止深入. 简单地说, 一个不在根节点的 :rub 元素不能有 children. 然而, 在 branch? 和 make-children 函数中, 我们不知道元素在树中的位置. 它们得到的是值, 而不是 locations. 我们可以用一个状态来解决这个问题, 比如一个 atom, 它会保存我们遍历过的货币列表.

另一个选择是检查我们引用 from 货币来寻找 children 的次数. 如果这是第一次调用, 那么我们在树的顶部 (即, 在根节点) 让我们找到 children 并改变 children 函数所闭包的 atom. 如果不是第一次 (atom 已改变), 我们遇到了一个循环的情况, 并且没有 children.

这两种选择都有存在的权利, 但现在, 我们想在没有状态和可变手段的情况下进行.

如果你再次检查这棵树, 就会清楚地发现问题在于遍历顺序. 由于我们努力深入, 很有可能会掉进一个我们出不去的虫洞. 如果我们成功地进入了带有解决方案的分支 (左侧), 而无限分支 (右侧) 保持未触动, 我们可能会很幸运:

   rub
  /   \
yen   usd
        |
       eur
        |
       rub

然而, 在解决问题时你不能依赖运气.

现在, 让 zipper 不是深入地遍历 location, 而是广度地向右遍历. 按照这个顺序, 我们不会受到无限分支的威胁. 如果树中出现无限分支, 我们不会试图详尽地遍历它. 相反, 我们会沿着树的层级向下, 并读取每个层级的所有元素. 即使其中一个源于一个无尽的分支, 这也不会阻止你探索其余的元素. 下图显示了水平遍历有助于你得到解决方案. 在这种情况下, 垂直遍历会走向无穷, 因为两个分支都是周期性的.

     rub
    /   \
  yen   usd
  / \   / \
... ... ... ...

问题在于 clojure.zip 模块只提供 zip/next 的深度优先遍历顺序. 没有其他算法. 我们将编写自己的函数来“分层”遍历 zipper, 如图所示:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

我们会得到以下层:

[1]
[2 3]
[4 5 6 7]

在这种情况下, 每个元素都不是一个原始类型, 而是一个 location. 这意味着元素记住了它在树中的位置, 你可以从它移动到其他元素, 获取它的路径, 等等.

首先, 我们需要一个函数, 它将返回原始 location 的子 locations. 它的逻辑很简单: 如果可以从该 location 向下走, 我们就向右移动, 直到到达空.

(defn loc-children [loc]
  (when-let [loc-child (zip/down loc)]
    (->> loc-child
         (iterate zip/right)
         (take-while some?))))

请注意, 这个函数与 zip/children 不同. 后者返回值, 而不是 locations, 而我们正好需要 locations. 比较表达式:

(-> [1 2 3]
    zip/vector-zip
    zip/children)
;; (1 2 3)

和

(-> [1 2 3]
    zip/vector-zip
    loc-children)
;; ([1 {:l [], :pnodes [[1 2 3]], :ppath nil, :r (2 3)}]
;;  [2 {:l [1], :pnodes [[1 2 3]], :ppath nil, :r (3)}]
;;  [3 {:l [1 2], :pnodes [[1 2 3]], :ppath nil, :r nil}])

在第二种情况下, 我们得到了 locations, 而 zip/children 只是访问了传递给 zipper 的 find children 函数.

假设, 对于某个 location, loc-children 返回了其 children 的列表. 要向下一层, 你需要找到它们的 children 并组合结果. 最简单的方法是使用以下表达式:

(mapcat loc-children locs)

其中 locs 是当前层的 locations 列表. 如果我们将 mapcat 的结果传递给 locs 参数, 我们会走得更远. 我们会这样做, 直到得到一个空序列. 所有这些加在一起就得到了 loc-layers 函数:

(defn loc-layers [loc]
  (->> [loc]
       (iterate (fn [locs]
                  (mapcat loc-children locs)))
       (take-while seq)))

它接受根 location, 从那里开始迭代层. 我们将第一层显式设置为一个 location 的 vector. 然后是它的 children, 然后是 children 的 children, 依此类推. 我们只在得到一个空层时停止. 快速检查:

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

(let [layers (-> data
                 zip/vector-zip
                 loc-layers)]
  (for [layer layers]
    (->> layer
         (map zip/node)
         println)))
;; ([[[[1]]] 2 [[[3]]] 3])
;; ([[[1]]] [[[3]]])
;; ([[1]] [[3]])
;; ([1] [3])
;; (1 3)

为了得到一个元素从左到右的链, 我们用 concat 连接各层. 解决这个问题不需要这个函数, 但它可能有用:

(defn loc-seq-layers [loc]
  (apply concat (loc-layers loc)))

让我们回到货币兑换. 让我们选择兑换规则, 使它们包含周期性依赖. zipper 保持不变: 它使用本地的 get-children 函数构建兑换树, 该函数闭包在规则上.

(def rules2
  [[:rub :usd]
   [:usd :eur]
   [:eur :rub]

   [:rub :lir]
   [:lir :eur]

   [:eur :din]
   [:din :tug]])

使用这个 zipper 的工作风格将会改变. 现在我们不是用 zip/next 而是用我们的 loc-layers 来迭代它. 在每一步, 我们应该得到兑换层. 我们必须找到节点等于最终货币的 locations, 在下一层中. 一旦我们至少找到了一个, 问题就解决了. 剩下的只是计算到它们的路径.

(defn exchange2 [rules from to]
  (letfn [(get-children [value]
            (seq (for [[v1 v2] rules
                       :when (= v1 value)]
                   v2)))
          (loc-to? [loc]
            (-> loc zip/node (= to)))
          (find-locs-to [layer]
            (seq (filter loc-to? layer)))
          (->exchange [loc]
            (conj (zip/path loc) (zip/node loc)))]
    (let [zipper (zip/zipper keyword?
                             get-children
                             nil
                             from)]
      (->> zipper
           loc-layers
           (some find-locs-to)
           (map ->exchange)))))

你可能已经注意到, 现在没有必要比较链的长度: 如果 locations 属于同一层, 到达它们的步数是相同的. 根据问题陈述, 我们对最短的兑换选项感兴趣. 例如, 如果在第三层找到一个链, 而在第四层有三个链, 那么后者对我们来说不感兴趣 —— 我们在第三层完成遍历.

以下是关于 rules2 中指定的规则的兑换示例:

(exchange2 rules2 :rub :eur)
;; ([:rub :usd :eur] [:rub :lir :eur])

(exchange2 rules2 :rub :tug)
;; ([:rub :usd :eur :din :tug] [:rub :lir :eur :din :tug])

(exchange2 rules2 :lir :din)
;; ([:lir :eur :din])

解决方案仍然不完美. 如果我们指定一对没有链的货币, 我们会得到一个无限循环. 为了阻止它, 将层数限制在一个合理的数字, 比如五. 从金融的角度来看, 没有任何限制的货币兑换很可能是有害的, 因此是无意义的. 从技术上讲, 我们需要在 loc-layers 之后立即添加 (take N) 的形式:

(->> zipper
     loc-layers
     (take 5)
     (some find-locs-to)
     (map ->exchange))

现在, 我们得到一个无效对的空结果:

(exchange2 rules2 :tug :yen)
()

这个任务可以进一步改进. 例如, 你可以为每个链计算成本和交易费. 为此, 将汇率和费用添加到 [:from :to] vector 中. 根据我们代表的是客户还是银行, 我们会寻找最优或最昂贵的兑换. 请为这个问题想出你自己的变体. 在这一点上, 我们将结束货币的话题, 然后继续.

在本章中, 我们讨论了遍历顺序如何影响问题的解决方案. 广度优先和深度优先遍历排序适用于不同的情况. 这对于无限树很重要, 当算法在遍历时可能会循环. clojure.zip 包中没有广度遍历, 但你可以很容易地写一个函数将 zipper 分成几层. 你可能会发现 loc-layers 在涉及图和顶点的其他情况下很有用.

最后, 让我们看看你可能会觉得有用的其他 zipper 功能.