Indexing depth with Clojure using clojure.walk

Question

Given the following tree (or any other form in Clojure, including maps and vectors):

'( (ab) (cd) ) 

I would like to generate a map in Clojure that indexes each subform according to traversing the entire depth of the entire form and also provides a vector (or list) of child form indices (if any).

 0 -> a [] 1 -> b [] 2 -> (ab) [0 1] 3 -> c [] 4 -> d [] 5 -> (cd) [3 4] 6 -> ( (ab) (cd) ) [2 5] 

So far I have managed to use clojure.walk to create the first part (indexing subforms), but I don’t understand how to generate indexes of children. My code is added at the end and creates:

 user=> (depthFirstIndexing '( (ab) (cd) )) {6 ((ab) (cd)), 5 (cd), 4 d, 3 c, 2 (ab), 1 b, 0 a} 

Thus, the indices for the subforms are generated correctly in accordance with the depth traversal for the first time, but I do not see how I can get the indices of the children of each subform. I tried using the lightning module, but I could not figure out how to do a depth traversal to collect indexes.

halfway code

 (use 'clojure.walk) (defn depthFirstIndexing [aform] (let [counter (atom -1) idxToSubform (atom {}) ] (postwalk (fn [x] (def idx (swap! counter inc)) (swap! idxToSubform assoc idx x) x) aform) @idxToSubform)) 

Answer 1

 (use '[clojure.walk :only (postwalk)]) (use '[clojure.set :only (map-invert)]) (defn idx [col] (let [m (map vector (range) (let [v (atom [])] (postwalk (fn [f] (swap! v conj f) f) col) @v)) rm (map-invert m)] (into {} (map (fn [[ie]] [i [e (if (sequential? e) (mapv rm e) [])]]) m)))) (idx '((ab) (cd))) => {0 [a []], 1 [b []], 2 [(ab) [0 1]], 3 [c []], 4 [d []], 5 [(cd) [3 4]], 6 [((ab) (cd)) [2 5]]} 

Answer 2

A walk is recursive and does not contain a battery argument, so you had to resort to updating atoms.

A zipper is iterative, so you can transfer other information without breaking the functional template.

Natural rewinding in depth is a preliminary detour, but you are after the post-order, so this requires a little extra work.

Here is a workaround after a lightning workout:

 (require '[clojure.zip :as z]) (defn dfs-post-order-traversal [zipper] (loop [loc zipper, a []] (cond (z/end? loc) (conj a (z/node loc)) (z/branch? loc) (recur (z/next loc) a) :else (recur (z/next loc) (into (conj a (z/node loc)) (reverse (drop ((fnil count [nil]) (z/path (z/next loc))) (z/path loc)))))))) 

And a test case:

 (dfs-post-order-traversal (z/seq-zip '((ab) (cd)))) => [ab (ab) cd (cd) ((ab) (cd))] 

Now, to complete your request, we need to match the locations of the trees with their indices:

 (defn dfs-post-order-indexing [branch? children root] (let [pot (dfs-post-order-traversal (z/zipper branch? children conj root)) m (zipmap pot (range))] (for [n pot] [(mn) n (if (branch? n) (map m (children n)) (list))]))) (dfs-post-order-indexing seq? identity '((ab) (cd))) => ([0 a ()] [1 b ()] [2 (ab) (0 1)] [3 c ()] [4 d ()] [5 (cd) (3 4)] [6 ((ab) (cd)) (2 5)]) 

Something more exotic:

 (dfs-post-order-indexing coll? seq [{:a :b :c :d} :e [:f [:g '(:h :i)]]]) => ([0 :a ()] [1 :b ()] [2 [:a :b] (0 1)] [3 :c ()] [4 :d ()] [5 [:c :d] (3 4)] [6 {:a :b, :c :d} (2 5)] [7 :e ()] [8 :f ()] [9 :g ()] [10 :h ()] [11 :i ()] [12 (:h :i) (10 11)] [13 [:g (:h :i)] (9 12)] [14 [:f [:g (:h :i)]] (8 13)] [15 [{:a :b, :c :d} :e [:f [:g (:h :i)]]] (6 7 14)])