从 Clojure 中的嵌套列表中获取平面记录数据结构

Question

假设我有一个表示 clojure 树结构的列表列表，例如

'(a (b (c d)) (e (f)))

我想将它翻译成这样的记录格式（为了将其传递给可视化包）：

[{:id "0" :label "a" :parent nil}
 {:id "1" :label "b" :parent "0"}
 {:id "2" :label "c" :parent "1"}
 {:id "3" :label "d" :parent "1"}
 {:id "4" :label "e" :parent "0"}
 {:id "5" :label "f" :parent "4"}]

解决这个问题的正确方法是什么？我对此很犹豫，但我会考虑从 defrecord 开始，然后以某种方式循环遍历树，但我不知道如何开始。

(def tree '(a (b (c d)) (e (f))))
(defn list-to-record [l]
  (defrecord rec [id name parent])
  (let [counter (atom 0)]
  (into [] (map ->rec 
                      ... ... ...))))

(list-to-record tree)

也许我应该使用 clojure.walk？

编辑：澄清一下，无论标签是什么，这都应该起作用，因此更改输入列表中的标签不应对结果结构（每个 :id 的 :parent 值）有任何影响。也就是下面的列表，和上面一样，但是标签都一样

'(a (a (a a)) (a (a)))

应该翻译成

[{:id "0" :label "a" :parent nil}
 {:id "1" :label "a" :parent "0"}
 {:id "2" :label "a" :parent "1"}
 {:id "3" :label "a" :parent "1"}
 {:id "4" :label "a" :parent "0"}
 {:id "5" :label "a" :parent "4"}]

Answer 1

这是一种方法。您只需添加有关为每个节点分配 "id" 的部分。

另请注意，您应该重新格式化输入数据，以便每个节点都采用 Hiccup 格式（即，即使是单节点 w/o 子节点也包含在向量中）。

(ns tst.demo.core
  (:use demo.core tupelo.core tupelo.test)
  (:require [tupelo.core :as t]))

(def tree
  [:a
   [:b
    [:c]
    [:d]]
   [:e
    [:f]]])

(def relationships (atom []))

(defn save-relationships
  [parent-id curr-node]
  (let [curr-id   (first curr-node)
        kid-nodes (rest curr-node)]
    (swap! relationships #(conj % {:parent parent-id :label curr-id}))
    (doseq [kid-node kid-nodes]
      (save-relationships curr-id kid-node))))

(dotest
  (reset! relationships [])
  (save-relationships nil tree)
  (spyx-pretty @relationships))

结果：

~/expr/demo > 
~/expr/demo > lein test

lein test _bootstrap

-------------------------------
   Clojure 1.10.1    Java 12
-------------------------------

lein test tst.demo.core
(clojure.core/deref relationships) => 
[{:parent nil, :label :a}
 {:parent :a, :label :b}
 {:parent :b, :label :c}
 {:parent :b, :label :d}
 {:parent :a, :label :e}
 {:parent :e, :label :f}]

Ran 2 tests containing 0 assertions.
0 failures, 0 errors.

Answer 2

这是一种使用 Clojure 拉链和 loop + recur:

的方法

(defn index-zipper [z]
  (loop [loc z, next-id 0, parent-ids [], acc []]
    (cond
      (z/end? loc) acc

      (and (z/node loc) (not (z/branch? loc)))
      (recur
        (z/next loc)
        (inc next-id)
        (cond
          (some-> (z/right loc) z/branch?) (conj parent-ids next-id)
          (not (z/right loc)) (some-> parent-ids not-empty pop)
          :else parent-ids)
        (conj acc
              {:id     (str next-id)
               :label  (str (z/node loc))
               :parent (when (seq parent-ids)
                         (str (peek parent-ids)))}))

      :else
      (recur (z/next loc) next-id parent-ids acc))))

loop 绑定了：

当前拉链location
下一个 :id 值，每次我们看到叶节点时递增
当前父级 :id 的堆栈（向量），将 pushed/popped 作为拉链 descends/ascends。每个叶节点的 :parent 值位于 parent-ids 堆栈的顶部。
acc叶节点映射的累加器向量

可以调用带拉链的函数：

(index-zipper (z/seq-zip '(a (b (c d)) (e (f)))))
=>
[{:id "0", :label "a", :parent nil}
 {:id "1", :label "b", :parent "0"}
 {:id "2", :label "c", :parent "1"}
 {:id "3", :label "d", :parent "1"}
 {:id "4", :label "e", :parent "0"}
 {:id "5", :label "f", :parent "4"}]

(index-zipper (z/seq-zip '(a (a (a a)) (a (a)))))
=>
[{:id "0", :label "a", :parent nil}
 {:id "1", :label "a", :parent "0"}
 {:id "2", :label "a", :parent "1"}
 {:id "3", :label "a", :parent "1"}
 {:id "4", :label "a", :parent "0"}
 {:id "5", :label "a", :parent "4"}]

从 Clojure 中的嵌套列表中获取平面记录数据结构

getting a flat record data structure out of a nested list in Clojure

clojure

record

tree-traversal