I have a vector of maps, that I'd like to transform in a nested fashion.

The data is structured as follows:

(def data
  [{:id 1 :name "a" :parent 0}
   {:id 2 :name "b" :parent 0}
   {:id 3 :name "c" :parent 0}
   {:id 4 :name "a_1" :parent 1}
   {:id 5 :name "a_2" :parent 1}
   {:id 6 :name "b_1" :parent 2}
   {:id 7 :name "a_1_1" :parent 4}])

Each map has an :id, some other keys and values not important for this discussion, and :parent key, denoting if the elements belong to another element. If :parent is 0, it's a top level element.

I want to nest this flattened list so that each element belonging to a parent gets stored under a key :nodes in the parent map, like this:

(def nested
  [{:id 1 :name "a" :parent 0 :nodes
    [{:id 4 :name "a_1" :parent 1 :nodes []}
     {:id 5 :name "a_2" :parent 1 :nodes
      [{:id 7 :name "a_1_1" :parent 4 :nodes []}]}]}
   {:id 2 :name "b" :parent 0 :nodes
    [{:id 6 :name "b_1" :parent 2}]}
   {:id 3 :name "c" :parent 0 :nodes []}])

To sum up - I have a flattened tree-like structure that I whish to transform into a tree again. I tried to achieve this using zippers, but failed to handle arbritarily nested levels.

The easiest way is to build it recursively by performing a full scan at each step:

(defn tree
  ([flat-nodes]
    (tree flat-nodes 0))
  ([flat-nodes parent-id]
    (for [node flat-nodes
          :when (= (:parent node) parent-id)]
      (assoc node
        :nodes (tree flat-nodes (:id node))))))

and then

=> (tree data)
({:parent 0, :name "a", :nodes 
   ({:parent 1, :name "a_1", :nodes 
     ({:parent 4, :name "a_1_1", :nodes (), :id 7}), :id 4}
    {:parent 1, :name "a_2", :nodes (), :id 5}), :id 1}
 {:parent 0, :name "b", :nodes
   ({:parent 2, :name "b_1", :nodes (), :id 6}), :id 2}
 {:parent 0, :name "c", :nodes (), :id 3})

Update: A more efficient variation

(defn tree [flat-nodes]
  (let [children (group-by :parent flat-nodes)
        nodes (fn nodes [parent-id]
                (map #(assoc % :nodes (nodes (:id %)))
                  (children parent-id)))]
    (nodes 0)))