How to get all values for a given key in a nested structure in clojure

Question

(def threads
  {:values
   [{:_id "t1"
     :u {:uid 1}
     :members {:values [{:uid 1} {:uid 2}]}
     :messages {:values
                [{:_id "m1" :u {:uid 1}}
                 {:_id "m2" :u {:uid 2}}]}}
    {:_id "t2"
     :u {:uid 12}
     :members {:values [{:uid 11} {:uid 12}]}
     :messages {:values
                [{:_id "m3" :u {:uid 13}}
                 {:_id "m4" :u {:uid 12}}]}}]})

Need to find out all values for the key :uid In this case answer should return [1 2 11 12 13] without using any global bindings. Needs solution scale for any level of nested structure.

Thanks

Answer 1

This can be done with tree-seq and filter, or with post-walk. Both appraoches are interesting to me:

tree-seq:

user> (map :uid 
           (filter #(if (and (map? %) (:uid %)) true  false)  
                   (tree-seq #(or (map? %) (vector? %)) identity threads)))
(1 2 1 1 2 13 12 12 11 12) 

Which looks better when threaded out with ->> (and with set and vec to remove dups)

user> (->> (tree-seq #(or (map? %) (vector? %)) identity threads) 
           (filter #(if (and (map? %) (:uid %)) true  false)) 
           (map :uid)  
           set 
           vec)                                
[1 2 11 12 13] 

or with postwalk:

user> (let [results (atom [])]
        (clojure.walk/postwalk
           #(do (if-let [uid (:uid %)] (swap! results conj uid)) %)
           threads)
         @results)
[1 2 1 1 2 13 12 12 11 12]

This walks the structure with a function that, if the structure contains a key named :uid, appends it to a local atom. Then at the end return the accumulated contents of the atom. This differs slightly from your example because it accumulates duplicates. If you want to eliminate them efficiently then use a set as the accumulator instead of a vector, then turn it into a vector once at the end (your example has results in a vector)

user> (let [results (atom #{})] 
         (clojure.walk/postwalk 
            #(do (if-let [uid (:uid %)] (swap! results conj uid)) %) 
            threads) 
         (vec @results))
[1 2 11 12 13]