Clojure拉链路径函数不完整？

Question

编辑 #2: 我错过了zipper的基本概念，即它们代表数据结构中从特定节点视角的一种透视图。因此，一个zipper始终是当前节点和从该节点视角看到的树的其余部分的一对。我最初尝试从zipper生成一个全新的结构，而实际上我所需要的只是zipper本身。希望这篇文章能够帮助其他人（或者成为任何接替者的警告！），我将其保留下来。

原始问题：

我正在尝试使用zippers操作树。具体问题是，我需要在运行时生成两个节点之间匹配任意条件的路由，这些节点位于任意树中。

我认为我可以使用path函数通过在当前位置调用path来获取到达该位置的路径。但是返回的路径似乎省略了到达该位置所需的最后一步（步骤）。

例如：

(def test-zip (vector-zip [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]))
(-> test-zip 
    down right right down 
    right down right right
    node)

该代码返回5，但是

(-> test-zip 
    down right right down 
    right down right right
    path)

提供

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

这并不是同一个位置（它缺少最后三个步骤的效果，down right right）。

看起来路径函数只能让你到达树中父级位置，忽略了在你和实际位置之间的任何兄弟节点。

我是否误解了 path 函数的含义？我本以为，给定一棵树和一条路径，将该路径应用于树将使您到达路径的原始位置，而不是部分到达。

更新：我已使用以下函数定义将节点的路径从起始位置编译为结束位置：

(defn lca-path [start-loc end-loc]
  (let [sczip (z/root start-loc)
        start-path (z/path start-loc)
        start-node (z/node start-loc)
        end-path (z/path end-loc)
        end-node (z/node end-loc)
        lca-path (filter (set start-path) end-path)
        lca-node [(last lca-path)]
        lca-to-start (conj (vec (drop (count lca-path) start-path)) start-node)
        lca-to-end (conj (vec (drop (count lca-path) end-path)) end-node)
        ]

    (concat (reverse lca-to-start) lca-node lca-to-end))
  )

在与@Mark Fisher的聊天中，我受到了很大的启发，谢谢！

- Oliver Mooney

Answer 1

我认为你是正确的，它指向的是父级，这在查看这个网站时得到了证实，path 返回“从树的根到当前 loc 上方的所有子树”。

对于您的结构，树如下：

   A
 / | \
0  o  B
   | / \
   1 2  C __
       /|\  \
      3 o 5  o
        |   /|\
        4  6 o o
             | |
             7 8

所以标记为 A、B、C 的三个节点是指向 5 的父节点的父节点，它们分别是：

A: [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]]
B: [2 [3 [4] 5 [6 [7] [8]]]]
C: [3 [4] 5 [6 [7] [8]]]

这是您获得的结果。

编辑：我创建了此函数以在向量中搜索两个值并返回它们之间的路径。这有帮助吗？我不是拉链专家，所以这也是我学习的过程。

(defn between [v s e]
  (let [zv (zip/vector-zip v)
        find-loc (fn [zv l]
                   (loop [loc zv]
                     (if (= l (zip/node loc))
                       loc 
                       (if (zip/end? loc)
                           nil
                           (recur (zip/next loc))))))
        sv (zip/vector-zip (-> (find-loc zv s) zip/up zip/node))
        e-in-sv (find-loc sv e)
        path-s-e (when (some? e-in-sv)
                   (zip/path e-in-sv))]
    path-s-e))

它会找到起始值的父节点和结束值的父节点之间的路径，你可以像这样使用：

(def sov [0 [1] [2 [3 [4] 5 [6 [7] [8]]]]])
(between sov 2 6)
=> [[2 [3 [4] 5 [6 [7] [8]]]] [3 [4] 5 [6 [7] [8]]] [6 [7] [8]]]

我在树上走，以找到起始值的父节点，并从其父级创建一个新的zipper，以使路径从起点开始限制。辅助函数“find-loc”返回所寻找条目的zipper，例如在向量中的“5”。然后，sv是包含起始值的父向量。

如果没有路径，则返回nil，例如在1和4之间，您必须上移2个元素。

这是针对您在最终节点中查找值（例如[3 [4] 5 [6 [7] [8]]]中的5）的评论而做出的回应，我认为您不需要这样做，但是如果没有您正在做的实际示例很难发表评论。

顺便说一句，可能有比自定义函数更好的遍历/查找向量中的值的方法，但正如我所说，zippers对我来说也是相当新的。

- Mark Fisher

---

那么一旦你到达父子树，你必须在最后一个子树的直接后代中手动搜索所需的节点？鉴于直接下降节点是3、[4]、5和[6 [7] [8]]，在这种情况下搜索范围不会太宽。但是，四个位置返回相同的路径是否不奇怪？我是否错过了在拉链中捕获位置路线的其他惯用方法？ - Oliver Mooney

我在这方面与您分享旅程。我更新了我的答案，包括在两点之间查找您的向量。这符合您想要实现的目标吗？ - Mark Fisher

这不是重复了 path 函数的功能吗？一旦您找到起始位置和结束位置，并在这两个位置上调用路径，您可以执行 (filter (set start-path) end-path) 来获取两点的最低公共祖先。我还做了 lca-to-start-parent (drop (count lca-loc) start-path)以获取从最低公共祖先到起点的路径，以及 (drop (count lca-loc) end-path) 另一条腿到终点。我喜欢您的自包含实现方式，以及如何使用 identical? 导航到父位置... - Oliver Mooney

刚看到你的下一个评论 - 我实际上是在使用向量作为简化示例来掌握拉链，我正在使用自定义拉链处理我的实际数据，但希望将其排除为一个复杂因素。 - Oliver Mooney

也许值得注意的是，我们都假设节点的值是唯一的（在我的情况下是真的）。 - Oliver Mooney