如何获得深度优先遍历中已经访问过的 Clojure 拉链部分？
How to get the part of a Clojure zipper already visited in depth-first traversal?
当您通过 z/next 以深度优先的方式遍历任意嵌套的 Clojure zipper 时，您能否获取或重建拉链的已访问部分，同时保留其结构？例如，让我们有一个 [0 [1 2] 3] 的矢量拉链。如何实现函数visited到return拉链的访问部分，比如访问1时[0 [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 return仅访问同一层级的部分。
编辑 2： 似乎几乎可以工作。如果我们让它以 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能不能合身一些
不容易。您希望将值 [0 [1 2]] 作为输出，但从未访问过该值。所以，你不能仅仅通过查看任何以前访问过的节点来获得它。取而代之的是，您必须根据检查访问者的历史，自己想出一种创建此结构的方法。
这听起来并非不可能，但算法并不完全显而易见。我的第一个反对意见是这个问题似乎定义不明确：您真的希望 "already visited set" 在您访问事物时 收缩 吗？你说当访问 [1 2] 时你认为已经访问过的部分是 [0 [1 2]]，这意味着当你查看向量 [1 2] 时你认为它的所有内容都已经被访问过.在那种情况下，当您查看根时，整棵树都已被访问过，而当您深入其中时，它会变得越来越少！
因此，我建议对您想要的内容进行更准确的定义，希望如果您对此足够严谨，算法会自行提出建议。
不是使用 Zippers 的直接答案，但您可以使用 the Tupelo Forest library 轻松解决这个问题。这是一个例子：
(dotest-focus ; walk the tree and keep track of all the visited nodes
(hid-count-reset)
(with-forest (new-forest)
; an "hid" is like a pointer to the node
(let [root-hid (add-tree-hiccup [:a
[:b
[:c 1]]
[:d
[:e 2]]])
tgt-hid (find-hid root-hid [:** :c]) ; hid of the :c node we want to stop at
state-atom (atom {:visited-hids []
:found-tgt? false})
enter-fn (fn [path] ; path is from root
(let [curr-hid (xlast path)] ; curr node is last elem in path
(swap! state-atom
(fn [curr-state]
(cond-it-> curr-state
(falsey? (grab :found-tgt? it)) (update it :visited-hids append curr-hid)
(= curr-hid tgt-hid) (assoc it :found-tgt? true))))))]
(newline)
(println "Overall Tree Structure:")
(spy-pretty (hid->tree root-hid))
(newline)
(walk-tree root-hid {:enter enter-fn}) ; accum results => state atom
(newline)
(println "final state map")
(spyx @state-atom)
(newline)
(let [depth-first-tags (it-> (grab :visited-hids @state-atom)
(mapv hid->node it)
(mapv #(grab :tag %) it))]
(is= depth-first-tags [:a :b :c])
(println "depth-first tags thru target:")
(println depth-first-tags)
(newline)))))
输出：
Overall Tree Structure:
{:tag :a,
:tupelo.forest/kids
[{:tag :b,
:tupelo.forest/kids [{:tupelo.forest/kids [], :tag :c, :value 1}]}
{:tag :d,
:tupelo.forest/kids [{:tupelo.forest/kids [], :tag :e, :value 2}]}]}
final state map
(clojure.core/deref state) => {:visited-hids [1005 1002 1001], :found-tgt? true}
depth-first tags thru target:
[:a :b :c]
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.
根据您的确切用例，您可以根据需要修改输出格式。
您的评论 "z/lefts returns only the visited part on the same hierarchical level" 提出了自己的解决方案。调用z/lefts，然后用z/up上一层，递归继续。
我绘制的草图并不完全正确，但接近于正确的形状并说明了我的建议：
(defn visited [node]
(let [parent (z/up node)]
(if (nil? parent)
[] ;; we're at the root
(conj (visited parent)
(if (z/branch? node)
(vec (z/lefts node))
(conj (vec (z/lefts node)) (z/node node)))))))
如果我正确理解您的objective，我相信这会成功：
(defn visited [loc]
(loop [cur loc
start true]
;; Loop from the starting location up to the root
(if-let [par (z/up cur)]
(recur
;; Replace our parent with a node that only includes its visited children
(z/replace
par
(z/make-node
par
(z/node par)
(cond-> (z/lefts cur)
;; If we started at a branch, don't treat its children as visited
(not (and start (z/branch? cur))) (concat [(z/node cur)]))))
false)
(if (and start (not (z/end? cur)))
[]
(z/node cur)))))
作为测试，下面是一个在相对复杂的树的遍历中的每个步骤从 visited 打印 return 的示例：
(def root (z/vector-zip [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]))
(loop [loc root]
(when (not (z/end? loc))
(println "visit " (z/node loc))
(println "visited " (visited loc))
(recur (z/next loc))))
visit [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
visited []
visit [1 [2 3 4] 5]
visited []
visit 1
visited [[1]]
visit [2 3 4]
visited [[1]]
visit 2
visited [[1 [2]]]
visit 3
visited [[1 [2 3]]]
visit 4
visited [[1 [2 3 4]]]
visit 5
visited [[1 [2 3 4] 5]]
visit 6
visited [[1 [2 3 4] 5] 6]
visit [[[7 8] [9]] 10 11]
visited [[1 [2 3 4] 5] 6]
visit [[7 8] [9]]
visited [[1 [2 3 4] 5] 6 []]
visit [7 8]
visited [[1 [2 3 4] 5] 6 [[]]]
visit 7
visited [[1 [2 3 4] 5] 6 [[[7]]]]
visit 8
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit [9]
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit 9
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]]]]
visit 10
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10]]
visit 11
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
nil
当您通过 z/next 以深度优先的方式遍历任意嵌套的 Clojure zipper 时，您能否获取或重建拉链的已访问部分，同时保留其结构？例如，让我们有一个 [0 [1 2] 3] 的矢量拉链。如何实现函数visited到return拉链的访问部分，比如访问1时[0 [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 return仅访问同一层级的部分。
编辑 2：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能不能合身一些
不容易。您希望将值 [0 [1 2]] 作为输出，但从未访问过该值。所以，你不能仅仅通过查看任何以前访问过的节点来获得它。取而代之的是，您必须根据检查访问者的历史，自己想出一种创建此结构的方法。
这听起来并非不可能，但算法并不完全显而易见。我的第一个反对意见是这个问题似乎定义不明确：您真的希望 "already visited set" 在您访问事物时 收缩 吗？你说当访问 [1 2] 时你认为已经访问过的部分是 [0 [1 2]]，这意味着当你查看向量 [1 2] 时你认为它的所有内容都已经被访问过.在那种情况下，当您查看根时，整棵树都已被访问过，而当您深入其中时，它会变得越来越少！
因此，我建议对您想要的内容进行更准确的定义，希望如果您对此足够严谨，算法会自行提出建议。
不是使用 Zippers 的直接答案，但您可以使用 the Tupelo Forest library 轻松解决这个问题。这是一个例子：
(dotest-focus ; walk the tree and keep track of all the visited nodes
(hid-count-reset)
(with-forest (new-forest)
; an "hid" is like a pointer to the node
(let [root-hid (add-tree-hiccup [:a
[:b
[:c 1]]
[:d
[:e 2]]])
tgt-hid (find-hid root-hid [:** :c]) ; hid of the :c node we want to stop at
state-atom (atom {:visited-hids []
:found-tgt? false})
enter-fn (fn [path] ; path is from root
(let [curr-hid (xlast path)] ; curr node is last elem in path
(swap! state-atom
(fn [curr-state]
(cond-it-> curr-state
(falsey? (grab :found-tgt? it)) (update it :visited-hids append curr-hid)
(= curr-hid tgt-hid) (assoc it :found-tgt? true))))))]
(newline)
(println "Overall Tree Structure:")
(spy-pretty (hid->tree root-hid))
(newline)
(walk-tree root-hid {:enter enter-fn}) ; accum results => state atom
(newline)
(println "final state map")
(spyx @state-atom)
(newline)
(let [depth-first-tags (it-> (grab :visited-hids @state-atom)
(mapv hid->node it)
(mapv #(grab :tag %) it))]
(is= depth-first-tags [:a :b :c])
(println "depth-first tags thru target:")
(println depth-first-tags)
(newline)))))
输出：
Overall Tree Structure:
{:tag :a,
:tupelo.forest/kids
[{:tag :b,
:tupelo.forest/kids [{:tupelo.forest/kids [], :tag :c, :value 1}]}
{:tag :d,
:tupelo.forest/kids [{:tupelo.forest/kids [], :tag :e, :value 2}]}]}
final state map
(clojure.core/deref state) => {:visited-hids [1005 1002 1001], :found-tgt? true}
depth-first tags thru target:
[:a :b :c]
Ran 1 tests containing 1 assertions.
0 failures, 0 errors.
根据您的确切用例，您可以根据需要修改输出格式。
您的评论 "z/lefts returns only the visited part on the same hierarchical level" 提出了自己的解决方案。调用z/lefts，然后用z/up上一层，递归继续。
我绘制的草图并不完全正确，但接近于正确的形状并说明了我的建议：
(defn visited [node]
(let [parent (z/up node)]
(if (nil? parent)
[] ;; we're at the root
(conj (visited parent)
(if (z/branch? node)
(vec (z/lefts node))
(conj (vec (z/lefts node)) (z/node node)))))))
如果我正确理解您的objective，我相信这会成功：
(defn visited [loc]
(loop [cur loc
start true]
;; Loop from the starting location up to the root
(if-let [par (z/up cur)]
(recur
;; Replace our parent with a node that only includes its visited children
(z/replace
par
(z/make-node
par
(z/node par)
(cond-> (z/lefts cur)
;; If we started at a branch, don't treat its children as visited
(not (and start (z/branch? cur))) (concat [(z/node cur)]))))
false)
(if (and start (not (z/end? cur)))
[]
(z/node cur)))))
作为测试，下面是一个在相对复杂的树的遍历中的每个步骤从 visited 打印 return 的示例：
(def root (z/vector-zip [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]))
(loop [loc root]
(when (not (z/end? loc))
(println "visit " (z/node loc))
(println "visited " (visited loc))
(recur (z/next loc))))
visit [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
visited []
visit [1 [2 3 4] 5]
visited []
visit 1
visited [[1]]
visit [2 3 4]
visited [[1]]
visit 2
visited [[1 [2]]]
visit 3
visited [[1 [2 3]]]
visit 4
visited [[1 [2 3 4]]]
visit 5
visited [[1 [2 3 4] 5]]
visit 6
visited [[1 [2 3 4] 5] 6]
visit [[[7 8] [9]] 10 11]
visited [[1 [2 3 4] 5] 6]
visit [[7 8] [9]]
visited [[1 [2 3 4] 5] 6 []]
visit [7 8]
visited [[1 [2 3 4] 5] 6 [[]]]
visit 7
visited [[1 [2 3 4] 5] 6 [[[7]]]]
visit 8
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit [9]
visited [[1 [2 3 4] 5] 6 [[[7 8]]]]
visit 9
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]]]]
visit 10
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10]]
visit 11
visited [[1 [2 3 4] 5] 6 [[[7 8] [9]] 10 11]]
nil