Как я могу превратить упорядоченное дерево в коллекцию именованных узлов в Clojure?

Question

Я думаю, что лучше использовать пример. Допустим, у меня есть упорядоченное дерево:

(def abcd [:a [:b :c] :d])

Я хочу построить из него коллекцию карт ключ-значение, каждая карта представляет собой узлы этого дерева со случайным именем и всей соответствующей информацией, которая is, его родитель (nil для узла root), его индекс (0, 1, 2 ..) и, если это листовой узел, его содержимое (например, ": a"). Например, в этом случае это может быть:

[{:name G__36654, :parent nil, :index 0}
 {:name G__36655, :content :a, :parent G__36654, :index 0}
 {:name G__36656, :parent G__36654, :index 1}
 {:name G__36657, :content :b, :parent G__36656, :index 0}
 {:name G__36658, :content :c, :parent G__36656, :index 1}
 {:name G__36659, :content :d, :parent G__36654, :index 2}]

Я определил функцию, которая, кажется, делает то, что я хочу, но она использует рекурсию, вызывая себя, и у меня возникают проблемы с выяснением, как использовать l oop - повториться, и я верю, что должно быть что-то лучшее там. Вот моя попытка:

(defn mttrav "my tree traversal"
  ([ptree parent index]
   (let [name (gensym)]
     (cond
       (not (coll? ptree)) [ {:name name :content ptree :parent parent :index index}]

       :else (reduce into
                     [{:name name  :parent parent :index index}]
                     (map-indexed #(mttrav %2 name  %1) ptree)))))
  ([ptree]
   (mttrav ptree nil  0)))

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

Заранее спасибо!

Редактировать: просто уточнить, было бы также допустимо, чтобы каждый узел имел список: дочерних узлов вместо: родительского узла и некоторых других вариантов, если это плоская коллекция карт, каждая карта представляет узел с уникальным: name, и положение, содержание и родительско-дочерние отношения узлов фиксируются в этой структуре. Предполагается, что входными данными являются деревья разбора сбоя, обычно поступающие из Instaparse, а карты должны стать записями для вставки в сеанс Клары.

Answer 1

Ширина первого обхода - это то, что вам нужно. Поэтому, если вы хотите построить список родителей при обходе дерева, вам необходимо сначала однозначно идентифицировать все ваши конечные узлы. Я не уверен, что это можно сделать без этого, за исключением случаев, когда вы точно знаете, что ваши листовые узлы уникальны. Здесь также становится очень поздно / рано, поэтому мой мозг не работает оптимально. Я уверен, что моё решение может сильно испортиться.

Так что если у вас есть дерево вроде [: a [: b: c]: d [: b: c]], [: b: c ] является родителем: b и: c, но последние два конечных узла также являются: b и: c, так какой родитель вы выбираете?

Итак, давайте создадим дерево, листья которого имеют уникальный идентификатор.

(defn attach-ids [tree]
  (clojure.walk/postwalk (fn [node]
                           (if (coll? node) node
                               {:node node :id (gensym)}))
                         tree))


(def tree (attach-ids [:a [:b :c] :d]))

;; produces this
;; [{:node :a, :id G__21500}
;; [{:node :b, :id G__21501} {:node :c, :id G__21502}]
;;  {:node :d, :id G__21503}]

Теперь для остальной части решения

(defn add-parent [parent-map id branch]
  (assoc parent-map id {:children-ids (set (map :id branch))
                        :child-nodes (map :node branch)}))


(defn find-parent-id [node parent-map]
  (->> parent-map
    (filter (fn [[parent-id {children-ids :children-ids}]]
              (contains? children-ids (:id node))))
    ffirst))


(defn find-index [node parent-map tree]
  (if-let [parent-id (find-parent-id node parent-map)]
    (let [children (:child-nodes (get parent-map parent-id))]
      (.indexOf children (:node node)))
    (.indexOf tree node)))


(defn bfs [tree]
  (loop [queue tree
         parent-map {}
         ret []]
    (if (not-empty queue)
      (let [node (first queue)
            rst (vec (rest queue))]
        (cond
          (map? node)
          (recur rst
                 parent-map
                 (conj ret (assoc node :parent (find-parent-id node parent-map) 
                                       :index (find-index node parent-map tree))))
          (vector? node)
          (let [parent-id (gensym)]
            (recur (into rst node)
                   (add-parent parent-map parent-id node)
                   (conj ret {:id parent-id 
                              :index (find-index node parent-map tree)
                              :parent (find-parent-id node parent-map)})))))
      ret)))

(def tree  (attach-ids [:a [:b :c] :d]))
(bfs tree)

;; children with :parent nil value point to root
;;[{:node :a, :id G__21504, :parent nil, :index 0}
;; {:id G__21513, :index 1}
;; {:node :d, :id G__21507, :parent nil, :index 2}
;; {:node :b, :id G__21505, :parent G__21513, :index 0}
;; {:node :c, :id G__21506, :parent G__21513, :index 1}]

Answer 2

Когда дерево сопротивляется хвостовой рекурсии, еще одна вещь, которую стоит попробовать - это «молния» из стандартной библиотеки Clojure. Молния хороша для редактирования, но она также довольно хороша для линеаризации обхода в глубину, сохраняя при этом доступный контекст структуры. Типичная застежка-молния l oop выглядит следующим образом:

user> (def abcd '(:a (:b :c) :d))
#'user/abcd'
user> (loop [ret [], z (zip/seq-zip abcd)] 
        (if (zip/end? z)
          ret
          (let [o {:name 42, :content (zip/node z), :parent 42, :index 42}]
            (recur (conj ret o) (zip/next z)))))
[{:name 42, :content (:a (:b :c) :d), :parent 42, :index 42}
 {:name 42, :content :a, :parent 42, :index 42}
 {:name 42, :content (:b :c), :parent 42, :index 42}
 {:name 42, :content :b, :parent 42, :index 42}
 {:name 42, :content :c, :parent 42, :index 42}
 {:name 42, :content :d, :parent 42, :index 42}]

Чтобы заполнить :parent и :index, вы найдете обозначение застежки-молнии для поиска «вверх» у родителей, «влево» для братьев и сестер , et c., в официальных документах на https://clojure.github.io/clojure/clojure.zip-api.html.

Я создал почтовый индекс с seq-zip, в котором смоделированы узлы в виде списка. Ваш конкретный c case моделирует узлы как векторы , которые seq-zip не распознает, поэтому вы, вероятно, будете использовать vector-zip или придумать свой собственный адаптер. Вы можете перейти по ссылке «Источник» в документации, чтобы увидеть, как работают seq-zip и vector-zip.