Clojure 拉链删除所有正确的兄弟姐妹

Question

我想为 zipper 编写一个函数，在保持相同位置的同时删除节点的所有右兄弟节点。

(defn remove-all-rights-1 [loc]
  (if (zip/right loc) 
    (recur (zip/remove (zip/right loc)))
    loc))

这里的问题是 remove returns 在 DFS 中本应位于当前节点之前的位置。

因此下面的例子...

(-> (clojure.zip/vector-zip [1 [[2] 3]])
    (zip/down)
    (zip/right)
    (zip/down)
    (remove-all-rights-1)
    (zip/replace :x)
    (zip/root))

...给出 [1 [[:x]]] 而不是 [1 [:x]] 因为 zip/remove 跳到了底部叶子而不是仅仅向左返回。

我应该如何在不改变树中的位置的情况下删除正确的兄弟姐妹？？提前致谢！

Answer 1

(letfn [(kill-right [loc]
            (let [lost   (zip/rights loc)
                  parent (-> loc zip/up zip/node)
                  node   (into (empty parent) (take (- (count parent) (count lost)) parent))]
                (-> loc
                    zip/up
                    (zip/replace node)
                    zip/down
                    zip/rightmost)))]
    (-> (clojure.zip/vector-zip [1 [[2] 3]])
        zip/down
        zip/right
        zip/down
        kill-right
        (zip/replace :x)
        zip/root))

Answer 2

泛化给出了以下解决方案：

(defn remove-all-rights
  "Removes all right siblings. Stays at original location."
  [loc]
  (let [parent-loc (zip/up loc)
        |lefts| (inc (count (zip/lefts loc)))]
    (->> (zip/make-node loc (zip/node parent-loc) (take |lefts| (zip/children parent-loc)))
         (zip/replace parent-loc)
         (zip/down)
         (zip/rightmost))))

主要思想是构造父节点的副本，其中子节点集合不包含正确的兄弟节点。

Answer 3

这可以通过 Tupelo Forest 库轻松完成：

(dotest
  (with-forest (new-forest)
    (let [edn-orig          [1 [[2] 3]]
          root-hid          (add-tree (edn->tree edn-orig))
          hid               (find-hid root-hid [::tf/list ::tf/list])
          subtree-edn-orig  (-> hid hid->tree tree->edn)
          >>                (kids-update hid butlast)
          subtree-edn-final (-> hid hid->tree tree->edn)
          edn-final         (-> root-hid hid->tree tree->edn)]

      (is= subtree-edn-orig      [[2] 3])
      (is= subtree-edn-final     [[2]])
      (is= edn-final          [1 [[2]]]  ))))

创建的树在第一级和第二级具有 :tag 值为 :tupelo.forest/list 的节点：

  (is= (hid->bush root-hid)
    [{:tag :tupelo.forest/list, :tupelo.forest/index nil}
     [#:tupelo.forest{:value 1, :index 0}]
     [{:tag :tupelo.forest/list, :tupelo.forest/index 1}
      [{:tag :tupelo.forest/list, :tupelo.forest/index 0}
       [#:tupelo.forest{:value 2, :index 0}]]]] )

一个HID是一个指向树节点的指针，所以root-hid指向树的根节点，hid指向子树[[2] 3]。我们去掉最右边的节点3后，hid指向子树[[2]].

对于子节点（kids），我们使用butlast函数删除最右边的数据，然后将数据从forest/tree格式转换回EDN。

见the README here, and the API docs here. There are also many live code examples here. Also see the Clojure Conj video。

Clojure 拉链删除所有正确的兄弟姐妹

Clojure zipper to remove all right siblings

functional-programming

clojure

zipper