"nth not supported" 在循环中解构 Set 时在 PersistentHashSet 上 header

Question

这里是 Clojure 菜鸟。

我想拉前面和休息出一套。做 (front #{1}) 和 (rest #{1}) 分别产生 1 和 ()，这主要是我所期望的。

但是在下面的代码中，我在我的循环中使用解构 [current-node & open-nodes] #{start} 从集合中提取一些东西（此时我并不真正关心它是第一个还是最后一个项目。我只想让这个表格正常工作）但它坏了。

这是我的函数，half-implementing 网格搜索：

(defn navigate-to [grid start dest]
  "provides route from start to dest, not including start"
  (loop [[current-node & open-nodes] #{start} ;; << throws exception
         closed-nodes #{}]
    (if (= dest current-node)
      [] ;; todo: return route
      (let [all-current-neighbours (neighbours-of grid current-node) ;; << returns a set
            open-neighbours (set/difference all-current-neighbours closed-nodes)]
        (recur (set/union open-nodes open-neighbours)
               (conj closed-nodes current-node))))))

单步执行（使用 Cider）时，在第一个循环开始时抛出此异常：

UnsupportedOperationException nth not supported on this type: PersistentHashSet  clojure.lang.RT.nthFrom (RT.java:933)

我可以使用手动执行 first/rest 的嵌套 let 表单，但这似乎很浪费。有没有办法让解构的集合在循环形式中像这样工作？它只是不支持 Sets 吗？

Answer 1

集合是无序的，所以位置解构没有多大意义。

根据 Special Forms 的文档，它也处理解构，指定顺序（矢量）绑定使用 nth 和 nthnext 来查找要绑定的元素。

Vector binding-exprs allow you to bind names to parts of sequential things (not just vectors), like vectors, lists, seqs, strings, arrays, and anything that supports nth.

Clojure 哈希集（作为 java.util.Set 的实例）不支持按索引查找。

我不知道你的示例代码的上下文，但无论如何将集合内容倒入有序集合中，例如 (vec #{start})，将使解构工作。

Answer 2

正如其他人所提到的，您不能将集合绑定到向量文字，因为集合不是连续的。因此，即使是这个简单的 let 也会因 nth not supported:

而失败

(let [[x] #{1}])

您可以通过使用 first 和 disj:

“解构”集合来解决这个问题

(loop [remaining-nodes #{start}
       closed-nodes #{}]
    (let [current-node (first remaining-nodes)
          open-nodes   (disj  remaining-nodes current-node)]
        ;; rest of your code ...
    ))

使用 (rest remaining-nodes) 代替 (disj remaining-nodes current-node) 是可能的，但由于集合是无序的，rest 理论上没有义务取出与 [= 提取的元素相同的元素18=]。无论如何 disj 会完成这项工作。

注意：一定要检测remaining-nodes为nil，这可能会导致无限循环。

返回路线的算法

为了实现算法中缺失的部分（返回路线），您可以维护路径图。每个访问的节点都有一条路径：一个向量，其中的节点从起始节点通向该节点，由该节点作为键。

您可以使用 reduce 在您访问新节点时维护该路径图。使用与 reduce 一起使用的新函数和添加的 nil 测试，程序可能如下所示：

(defn add-path [[path paths] node]
    "adds a node to a given path, which is added to a map of paths, keyed by that node"
    [path (assoc paths node (conj path node))])

(defn navigate-to [grid start dest]
    "provides route from start to dest, including both"
    (loop [remaining-nodes #{start}
           closed-nodes    #{}
           paths           (hash-map start [start])]
        (let [current-node           (first remaining-nodes)
              current-path           (get paths current-node)
              all-current-neighbours (neighbours-of grid current-node)
              open-neighbours        (set/difference all-current-neighbours closed-nodes)]
            (if (contains? #{dest nil} current-node)
                current-path ;; search complete
                (recur (set/union (disj remaining-nodes current-node) open-neighbours)
                    (conj closed-nodes current-node)
                    (second (reduce add-path [current-path paths] open-neighbours)))))))

算法的本质仍然是一样的，尽管我将原来的 let 与解构节点所需的算法合并了。这不是绝对需要的，但它可能会使代码更具可读性。

测试

我根据这张图（数字是节点，条形表示链接节点：

0--1  2
|  |  |
3--4--5
|
6--7--8

这张图似乎很适合测试，因为它有一个循环、一个死胡同并且是相连的。

图表使用 grid 编码，作为向量，其中每个元素代表一个节点。该向量中元素的索引是节点的标识符。每个元素的内容是一组邻居，使 neighbours-of 函数变得微不足道（您的实现会有所不同）：

(def grid [#{1 3}   #{0 4}   #{5}
           #{0 4 6} #{1 3 5} #{2 4}
           #{3 7}   #{6 8}   #{7}  ])
          
(defn neighbours-of [grid node]
    (get grid node))

那么测试就是找到节点0到节点8的路由：

(println (navigate-to grid 0 8))

输出为：

[0 1 4 3 6 7 8]

这个结果表明该算法不保证最短路线，只保证找到存在的路由。我想在不同的引擎上结果可能会有所不同，这取决于 Conjure 内部如何决定从具有 first.

的集合中获取哪个元素

删除必要的节点链接之一后，如节点 7 和 8 之间的链接，输出为 nil。

注意：我发现这是一个有趣的问题，我的回答可能有点过头了。

"nth not supported" 在循环中解构 Set 时在 PersistentHashSet 上 header

"nth not supported" on PersistentHashSet when destructuring Set in Loop header

clojure

set

destructuring

返回路线的算法

测试