Создайте дерево из списка узлов, родительских элементов

Question

У меня есть список узлов, каждый из которых имеет родительский элемент, и я хочу построить дерево из них.

(def elems '[{:node A :parent nil} {:node B :parent A} {:node C :parent A} {:node D :parent C}]) 
(build-tree elems) 
=> (A (B) (C (D))) 

В настоящее время у меня есть этот код:

(defn root-node [elems] 
    (:node (first (remove :parent elems)))) 

(defn children [elems root] 
    (map :node (filter #(= root (:parent %)) elems))) 

(defn create-sub-tree [elems root-node] 
    (conj (map #(create-sub-tree elems %) (children elems root-node)) root-node)) 

(defn build-tree [elems] 
    (create-sub-tree elems (root-node elems))) 

В этом решении рекурсии используется, но не с петлей повторялся синтаксис. Это плохо, потому что код не может быть оптимизирован и StackOverflowError is possible.
Кажется, что я могу использовать recur только в том случае, если у меня есть одна рекурсия на каждом шаге.
В случае дерева у меня есть рекурсия для каждого дочернего узла.

Я ищу скорректированное решение, которое бы не столкнулось с этой проблемой.
Если у вас есть совершенно другое решение этой проблемы, я бы с удовольствием ее увидел.
Я читал немного о молнии, возможно, это лучший способ построить дерево.

Answer 1

Это решение, с которым я бы пошел. Он по-прежнему восприимчив к StackOverflowError, но только для очень «высоких» деревьев.

(defn build-tree [elems] 
    (let [vec-conj (fnil conj []) 
     adj-map (reduce (fn [acc {:keys [node parent]}] 
          (update-in acc [parent] vec-conj node)) 
         {} elems) 
     construct-tree (fn construct-tree [node] 
         (cons node 
           (map construct-tree 
            (get adj-map node)))) 
     tree (construct-tree nil)] 
    (assert (= (count tree) 2) "Must only have one root node") 
    (second tree))) 

Мы можем удалить проблему StackOverflowError, но это немного больно для этого. Вместо того, чтобы обрабатывать каждый лист сразу с construct-tree, мы могли бы оставить что-то еще там, чтобы указать, что еще нужно сделать работу (например, нулевую функцию arg), а затем выполнить еще один шаг обработки для обработки каждого из них, постоянно обрабатывать, пока не осталось работы делать. Это можно было бы сделать в постоянном пространстве стека, но если вы не ожидаете действительно высоких деревьев, это, вероятно, не нужно (даже clojure.walk/prewalk и postwalk переполнит стек на достаточно высоком дереве).