list - Clojure 数据结构翻译

Question

我需要翻译具有以下结构的数组映射:

{A [(A B) (A C)], C [(C D)], B [(B nil)], D [(D E) (D F)]}

进入这个等效列表:

'(A (B (nil)) (C (D (E) (F))))

我有这个函数，对于不太深的结构来说效果很好:

(def to-tree (memoize (fn [start nodes]
     (list* start
          (if-let [connections (seq (nodes start))]
            (map #(to-tree (second %) nodes) connections))))))

但是，随着嵌套元素 n 的增加，它会产生堆栈溢出错误。我怎样才能优化这个功能，或者更确切地说，有没有办法使用步行或任何其他功能方法来做到这一点？

Answer 1

您提供的输入数据看起来很像邻接表。您可以采取的一种方法是将数据转换为图表，然后从中创建树。

这是使用 loom 的解决方案处理图表。此示例仅使用 loom 中的一个函数 ( loom.graph/digraph )，因此如果您无法选择添加依赖项，您可能可以构建类似的东西。

让我们首先根据数据结构创建一个有向图。

(defn adj-list
  "Converts the data structure into an adjacency list."
  [ds]
  (into {} (map
            ;; convert [:a [[:a :b] [:a :c]]] => [:a [:b :c]]
            (fn [[k vs]] [k (map second vs)])
            ds)))

(defn ds->digraph
  "Creates a directed graph that mirrors the data structure."
  [ds]
  (loom.graph/digraph (adj-list ds)))

构建图表后，我们希望从图表的根节点生成树。在您的示例中，只有一个根节点 (A)，但实际上没有什么限制它只有一个。

Loom 存储图中所有节点的列表，以及具有到图中给定节点的传入边的所有节点的集合。我们可以使用它们来查找根节点。

(defn roots
  "Finds the set of nodes that are root nodes in the graph.

   Root nodes are those with no incoming edges."
  [g]
  (clojure.set/difference (:nodeset g)
                          (set (keys (:in g)))))

给定根节点，我们现在只需为每个节点创建一棵树。我们可以在图中查询与给定节点相邻的节点，然后递归地为这些节点创建树。

(defn to-tree [g n]
  "Given a node in a graph, create a tree (lazily).

   Assumes that n is a node in g."
  (if-let [succ (get-in g [:adj n])]
    (cons n (lazy-seq (map #(to-tree g %) succ)))
    (list n)))

(defn to-trees
  "Convert a graph into a collection of trees, one for each root node."
  [g]
  (map #(to-tree g %) (roots g)))

...就是这样!根据您的输入，我们可以生成所需的输出:

(def input {:a [[:a :b] [:a :c]] :c [[:c :d]] :b [[:b nil]] :d [[:d :e] [:d :f]]})
(first (to-trees (ds->digraph input))) ; => (:a (:c (:d (:e) (:f))) (:b (nil)))

以下是用于生成较深或具有多个根节点的结构的几个输入。

(def input-deep (into {} (map (fn [[x y z]] [x [[x y] [x z]]]) (partition 3 2 (range 1000)))))
(def input-2-roots {:a [[:a :b] [:a :c]] :b [[:b nil]] :c [[:c :d]] :e [[:e :b] [:e :d]]})

(to-trees (ds->digraph input-2-roots)) ; => ((:e (:b (nil)) (:d)) (:a (:c (:d)) (:b (nil))))

这种方法的一个很酷的事情是它可以使用无限嵌套的数据结构，因为生成树是惰性的。如果你尝试渲染树(因为它也是无限嵌套的)，你将得到一个 StackOverflowException，但实际上生成它是没有问题的。

最简单的方法是创建一个带有循环的结构，如下例所示。 (请注意，:c 节点是必需的。如果图中只有 :a 和 :b ，则没有根节点!)

(def input-cycle {:a [[:a :b]] :b [[:b :a]] :c [[:c :a]]})

(def ts (to-trees (ds->digraph input-cycle)))
(-> ts first second first)        ;; :a
(-> ts first second second first) ;; :b

您可以使用loom.alg/dag?来测试这种情况。 .