如何在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（僅用於第一級）

The be haviour我需要：

          ;=> [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))) 

...有相同的結果。

Answer 2

而且我發現另一種解決辦法：

(defn find-index-route 
    [x form] 
    (letfn [(get-nodes [form] 
      (tree-seq coll? identity form)) 

      (get-tree [form] 
      (rest (get-nodes form))) 

      (get-level [form] 
      (if (or (not (coll? form)) (not (seq form))) 
       0 
       (count (filter coll? (get-nodes form))))) 

      (get-result [x form] 
      (reduce (fn [v form] 
         (let [[idx lvl _] (last v) 
          form-lvl (get-level form) 
          contains? ((set (get-nodes form)) x)] 
         (conj v [(if (or (not idx) (< form-lvl lvl)) 0 (+ idx 1)) 
           form-lvl 
           contains?]))) [] (get-tree form))) 

      (get-indices [x form] 
      (map (fn [[idx _ _]] idx) 
       (filter 
        (fn [[_ _ contains?]] contains?) (get-result x form))))] 

    (get-indices x form))) 

Answer 3

我做了發現所有路線的一個版本。

(defn find-index-route 
    "find all routes to some value" 
    ([k x] (find-index-route k x [])) 
    ([k x p] 
    (cond 
    (= k x) [p] 
    (coll? x) (->> (if (map? x) x (vec x)) 
        (reduce-kv (fn [acc i v] 
           (into (vec (find-index-route k v (conj p i))) acc)) [])) 
    :else nil))) 

編輯：也適用於地圖

(find-index-route :my-key '{:bar 33 
          :foo [{:my-key ("0" :my-key)}] 
          "bar" ["key" {:foo ([:my-key])}]}) 
;=> [["bar" 1 :foo 0 0] [:foo 0 :my-key 1]] 

Answer 4

這個問題似乎完美的幽靈庫，這是所有關於導航和轉化嵌套數據結構。我昨天問彌敦道馬茲有關可能解決這一問題上Clojurians - 看到他原來的答案here：

(defn find-index-route [v data] 
    (let [walker (recursive-path [] p 
           (if-path sequential? 
             [INDEXED-VALS 
             (if-path [LAST (pred= v)] 
                FIRST 
                [(collect-one FIRST) LAST p])])) 
     ret (select-first walker data)] 
    (if (vector? ret) ret [ret]))) 

注意它返回[無]如果：我的鍵不存在。你可以很容易地修改它返回零通過更改最後一個「如果」部分：

(if (or (vector? ret) (nil? ret)) ret [ret])