如何获得已经在深度优先遍历中访问过的Clojure拉链的一部分？

Question

[当您通过Clojure zipper以深度优先的方式遍历任意嵌套的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仅返回相同层次级别的被访问部分。

Answer 1

听起来并非不可能，但是算法并不完全明显。我的第一个反对意见是问题似乎定义不清：您是否真的希望在访问事物时将“已访问集”设置为

shrink？您说访问[1 2]时将已访问的部分视为[0 [1 2]]，这意味着在查看向量[1 2]时，您将考虑其所有内容已被访问。在那种情况下，当您查看根时，整棵树已经被访问过了，当您进入它的根时，它的访问量就越来越少了！

因此，我建议熨平您想要的更精确的定义，并希望如果您对此严谨，算法会提出建议。

Answer 2

我得到的草图不完全正确，但是形状接近正确，并且可以说明我的建议：

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

Answer 3

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

根据您的确切用例，您可以根据需要调整输出格式。