CODEWITHSUNDEEP
clojure
dmz73
dmz73

Reputation: 1608

Nested list traversal

I would like to write a function that given a possibly nested list would return me a list of the indexes of each leaf, such that I can reduce the list with nth and those indexes and obtain each leaf. Ex: Given lst = ((a b) c) it would return ((0 0) (0 1) (1)) because (reduce nth lst [0 0]) = a (reduce nth lst [0 1]) = b and (reduce nth lst [1]) = c.

EDIT: Here is my solution using clojure.zip. Anyone can come up with a more elegant one?

(defn tree-indexes [zipper matcher pos accumulator]
  (loop [loc zipper pos pos accumulator accumulator]
    (if (z/end? loc)
      accumulator
      (if (matcher (z/node loc))        
        (if (z/right loc)
          (recur (z/next loc) (update-in pos [(- (count pos) 1)] inc) (conj accumulator [(z/node loc) pos]))
          (if (z/end? (z/next loc))
            (recur (z/next loc) pos (conj accumulator [(z/node loc) pos]))
            (recur (z/next loc) (update-in (vec (butlast pos)) [(- (count (vec (butlast pos))) 1)] inc) (conj accumulator [(z/node loc) pos]))))
        (recur (z/next loc) (conj pos 0) accumulator)))))

Upvotes: 1

Views: 196

Answers (1)

xsc
xsc

Reputation: 6073

I have a (non-tail-)recursive solution but there probably is some kind of iterative approach:

(defn list-indices
  ([l] (list-indices l []))
  ([l parent-indices]
   (->> l
        (map-indexed
          (fn [i element]
            (let [indices (conj parent-indices i)]
              (if (sequential? element)
                (list-indices element indices)
                [indices]))))
        (apply concat))))

Upvotes: 1

Related Questions