clojure - 如何在 Clojure 中查找深度嵌套数据结构(向量和列表)中的索引？

Question

我正在尝试从嵌套数据结构中获取值的索引路径。

我写了一些代码，但它不能正常工作

(defn helper
  [val form c index]
  (loop [f form
         i index
         l 0]
    (if (seq f)
      (if (or (list? (first f)) (vector? (first f)))
        (helper val (first f) (conj c l) (inc i))
        (if (= val (first f))
          (conj c l)
          (recur (rest f) (inc i) (inc l))))
      nil)))

(defn find-indexes
  [val form c index]
  (when (seq form)
    (if-let [result (helper val form c index)]
      result
      (find-indexes val (rest form) c (inc index)))))

(defn find-index-route
  [val form]
  (find-indexes val form [] 0))

当前行为:

(find-index-route :my-key '(1 2 ("a" :my-key))) ;=> [2 1] "Works"

(find-index-route :my-key '(1 2 ("a" ["b" 3 :my-key]))) ;=> [2 1 2] "Works"

(find-index-route :my-key '(1 2 ("a" ["b" 3 () :my-key]))) ;=> nil "Does NOT Work"

(find-index-route :my-key '(1 2 ("a" [] ["b" 3 :my-key]))) ;=> nil "Does NOT Work"

(find-index-route :my-key '(1 2 [] ("a" ["b" 3 :my-key]))) ;=> [0 1 2] "It has to be [3 1 2]"

问题是如果函数 点击空列表或向量 在找到它返回的值之前 零或 0 (仅针对第一个级别)

我需要的行为:

                                          ;=> [indexes...]

(find-index-route :my-key '(1 2 :my-key)) ;=> [2]

(find-index-route :my-key '(1 2 "a" :my-key "b")) ;=> [3]

(find-index-route :my-key '(1 2 [:my-key] "c")) ;=> [2 0]

(find-index-route :my-key '(1 2 [3 [:my-key]])) ;=> [2 1 0]

(find-index-route :my-key '(1 2 [3 [[] :my-key]])) ;=> [2 1 1]

(find-index-route :my-key '(1 2 [3 [4 5 6 (:my-key)]])) ;=> [2 1 3 0]

(find-index-route :my-key '(1 2 [3 [[]]])) ;=> nil or []

Answer 1

(defn find-index-route [x coll]
  (letfn [(path-in [y]
            (cond
              (= y x) '()
              (coll? y) (let [[failures [success & _]]
                              (->> y
                                   (map path-in)
                                   (split-with not))]
                          (when success (cons (count failures) success)))))]
    (path-in coll)))

例子:

(find-index-route :my-key '(1 2 :my-key)) ;=> [2]
=> (2)

(find-index-route :my-key '(1 2 "a" :my-key "b")) ;=> [3]
=> (3)

(find-index-route :my-key '(1 2 [:my-key] "c")) ;=> [2 0]
=> (2 0)

(find-index-route :my-key '(1 2 [3 [:my-key]])) ;=> [2 1 0]
=> (2 1 0)

(find-index-route :my-key '(1 2 [3 [[] :my-key]])) ;=> [2 1 1]
=> (2 1 1)

(find-index-route :my-key '(1 2 [3 [4 5 6 (:my-key)]])) ;=> [2 1 3 0]
=> (2 1 3 0)

(find-index-route :my-key '(1 2 [3 [[]]])) ;=> nil or []
=> nil

性能思考
split-with扫描序列两次，使用 take-while和 drop-while , 产生两个惰性序列。如果性能紧张，可以写一个版本 drop-while这也告诉你它掉了多少元素:

(defn counted-drop-while [pred coll]
  (loop [takes 0, tail coll]
    (if (and (seq tail) (pred (first tail)))
      (recur (inc takes) (rest tail))
      [takes tail])))

它只进行一次扫描。我们可以轻松适应 find-index-route使用它:

(defn find-index-route [x coll]
  (letfn [(path-in [y]
            (cond
              (= y x) '()
              (coll? y) (let [[fail-count [success & _]]
                              (->> y
                                   (map path-in)
                                   (counted-drop-while not))]
                          (when success (cons fail-count success)))))]
    (path-in coll)))

...具有相同的结果。