How to find an element in deeply nested data structure?

Question

I have this structure (which it is the result of parsing JSON response):

 [{"a" {"b" 1 "c" 2} 
       "children" [{"a" {"b" 3 "c" 4} "children" []}]}
  {"a" {"b" 5 "c" 6} "children" []}
  {"a" {"b" 7 "c" 8}
        "children" [{"a" {"b" 9 "c" 10} "children" []}]}]

So it is a tree. children is a vector of node. Each node is a map that has a, b and children.

I'm trying to find the node that has the value 9 for its b property. So, the result of the lookup is:

I tried to traverse the structure with tree-seq:

(tree-seq #(not-empty? % "children") identity structure)

But actually I'm getting the same structure. I was expecting to get a sequence of nodes where the relation is flattened and then I can filter on the sequence.

How to do that in an idiomatic way (and hopefully performant)? Feel free to blow my mind with zippers or walk.

Answer 1

You can get the desired tree-seq like so:

(def ts (mapcat (partial tree-seq #(contains? % "children") 
                                  #(get % "children"))
                your-data-structure))

mapcat is required because your input datastructure contains multiple root-nodes.

E. g. find a node like so:

(first (filter #(= (get-in % ["a" "b"]) 9) ts))
;-> {"a" {"b" 9, "c" 10}, "children" []}