clojure - 如何获取已在深度优先遍历中访问过的 Clojure 拉链部分？

Question

当您以深度优先方式遍历任意嵌套的Clojure 拉链z/next时，您能否获取或重建拉链已经访问过的部分，并保留其结构？例如，让我们有一个矢量拉链[0 [1 2] 3]。如何实现一个函数visited来返回拉链的访问部分，例如[0 [1]]访问时1？

编辑：在有用的答案的提示下，我意识到loc只有当它的子树被完全遍历时，才可以考虑访问它。因此，只有非分支位置（即(complement z/branch?)）才算作已访问。

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

(def zipper (z/vector-zip [0 [1 2] 3]))

(defn visited
  [zipper]
  ; ...
  )

(-> zipper z/next visited)
; => [0]
(-> zipper z/next z/next visited)
; => [0]
(-> zipper z/next z/next z/next visited)
; => [0 [1]]
(-> zipper z/next z/next z/next z/next visited)
; => [0 [1 2]]
(-> zipper z/next z/next z/next z/next z/next visited)
; => [0 [1 2] 3]

z/lefts仅返回同一层级上的已访问部分。

编辑 2：amalloy 的答案似乎几乎可行。如果我们让它以 开头into，那么它对于示例拉链可以正常工作：

(def visited
  (letfn [(root? [node]
            (= (z/node node) (z/root node)))]
    (fn [node]
      (if-let [parent (z/up node)]
        (let [comb-fn (if (root? parent) into conj)]
          (comb-fn (visited parent)
                   (if (z/branch? node)
                     (vec (z/lefts node))
                     (conj (vec (z/lefts node)) (z/node node)))))
        [])))) ;; we're at the root

然而，随着更多的嵌套，它的局限性变得明显。例如：

(def zipper (z/vector-zip [0 [1 [2]]]))

(-> zipper z/next z/next z/next z/next z/next visited)
; => [0 [1] [2]]

我想知道是否z/edit可以更好地适应。

标签： clojurezipper

Answer 1

不容易。您希望将 value 作为输出[0 [1 2]]，但从未访问过该值。因此，您无法仅通过查看任何先前访问过的节点来获得它。相反，您必须根据访问者的历史找出一种方法来自己创建此结构。

这听起来并非不可能，但算法并不完全显而易见。我的第一个反对意见是这个问题似乎定义不清：你真的希望“已经访问过的集合”在你访问事物时缩小吗？你说在访问时[1 2]你认为已经访问过的部分是[0 [1 2]]，这意味着当你查看向量时，[1 2]你认为它的所有内容都已经被访问过。在这种情况下，当您查看根时，整棵树已经被访问过，当您深入其中时，它会变得越来越少！

因此，我建议对您想要的内容进行更准确的定义，并希望如果您对此足够严格，算法会自行提出建议。