depth first tree traversal accumulation in clojure

Question

I'd like to take a tree-like structure like this:

{"foo" {"bar" "1" "baz" "2"}}

and recursively traverse while remembering the path from the root in order to produce something like this:

["foo/bar/1", "foo/baz/2"]

Any suggestions on how this can be done without zippers or clojure.walk?

Answer 1

As nberger does, we separate enumerating the paths from presenting them as strings.

Enumeration

The function

(defn paths [x]
  (if (map? x)
    (mapcat (fn [[k v]] (map #(cons k %) (paths v))) x)
    [[x]]))

... returns the sequence of path-sequences of a nested map. For example,

(paths {"foo" {"bar" "1", "baz" "2"}})
;(("foo" "bar" "1") ("foo" "baz" "2"))

Presentation

The function

#(clojure.string/join \/ %)

... joins strings together with "/"s. For example,

(#(clojure.string/join \/ %) (list "foo" "bar" "1"))
;"foo/bar/1"

Compose these to get the function you want:

(def traverse (comp (partial map #(clojure.string/join \/ %)) paths))

... or simply

(defn traverse [x]
  (->> x
      paths
      (map #(clojure.string/join \/ %))))

For example,

(traverse  {"foo" {"bar" "1", "baz" "2"}})
;("foo/bar/1" "foo/baz/2")

---

• You could entwine these as a single function: clearer and more useful to separate them, I think.
• The enumeration is not lazy, so it will run out of stack space on deeply enough nested maps.