Clojure - Recursively Semi-Flatten Nested Map

Question

In clojure, how can I turn a nested map like this:

(def parent {:id "parent-1"
             :value "Hi dude!"
             :children [{:id "child-11"
                         :value "How is life?"
                         :children [{:id "child-111"
                                     :value "Some value"
                                     :children []}]}
                        {:id "child-12"
                         :value "Does it work?"
                         :children []}]})

Into this:

[
[{:id "parent-1", :value "Hi dude!"}]
[{:id "parent-1", :value "Hi dude!"} {:id "child-11", :value "How is life?"}]
[{:id "parent-1", :value "Hi dude!"} {:id "child-11", :value "How is life?"} {:id "child-111", :value "Some value"}]
[{:id "parent-1", :value "Hi dude!"} {:id "child-12", :value "Does it work?"}]
]

I'm stumbling through very hacky recursive attempts and now my brain is burnt out.

What I've got so far is below. It does get the data right, however it puts the data in some extra undesired nested vectors.

How can this be fixed? Is there a nice idiomatic way to do this in Clojure?

Thanks.

(defn do-flatten [node parent-tree]
  (let [node-res (conj parent-tree (dissoc node :children))
        child-res (mapv #(do-flatten % node-res) (:children node))
        end-res (if (empty? child-res) [node-res] [node-res child-res])]
    end-res))

(do-flatten parent [])

Which produces:

[
[{:id "parent-1", :value "Hi dude!"}] 
[[
[{:id "parent-1", :value "Hi dude!"} {:id "child-11", :value "How is life?"}]
[[
[{:id "parent-1", :value "Hi dude!"} {:id "child-11", :value "How is life?"} {:id "child-111", :value "Some value"}]
]]]
[
[{:id "parent-1", :value "Hi dude!"} {:id "child-12", :value "Does it work?"}]
]]
]

Answer 1

I don't know if this is idiomatic, but it seems to work.

(defn do-flatten
  ([node]
   (do-flatten node []))
  ([node parents]
   (let [path (conj parents (dissoc node :children))]
     (vec (concat [path] (mapcat #(do-flatten % path)
                                 (:children node)))))))

You can leave off the [] when you call it.

Answer 2

another option is to use zippers:

(require '[clojure.zip :as z])

(defn paths [p]
  (loop [curr (z/zipper map? :children nil p)
         res []]
    (cond (z/end? curr) res
          (z/branch? curr) (recur (z/next curr)
                                  (conj res
                                        (mapv #(select-keys % [:id :value])
                                              (conj (z/path curr) (z/node curr)))))
          :else (recur (z/next curr) res))))

Answer 3

I'd be inclined to use a bit of local state to simplify the logic:

(defn do-flatten
  ([node]
   (let [acc (atom [])]
     (do-flatten node [] acc)
     @acc))
  ([node base acc]
   (let [new-base (into base (self node))]
     (swap! acc conj new-base)
     (doall
      (map #(do-flatten % new-base acc) (:children node))))))

Maybe some functional purists would dislike it, and of course you can do the whole thing in a purely functional way. My feeling is that it's a temporary and entirely local piece of state (and hence isn't going to cause the kinds of problems that state is notorious for), so if it makes for greater readability (which I think it does), I'm happy to use it.