Clojureのデータ構造の変換

Question

私はこのような構造を持つ配列マップ翻訳する必要があります：私は深くないためだけで正常に動作し、この機能を持っている

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

：この等価リストに

{A [(A B) (A C)], C [(C D)], B [(B nil)], D [(D E) (D 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

入力データは、隣接関係リストのように見えます。あなたが取ることができる1つのアプローチは、あなたのデータをグラフに変換し、そこからツリーを作成することです。

ここでは、loomを使用してグラフを処理する方法を示します。この例では、織機（loom.graph/digraph）の関数を1つしか使用しないため、依存関係を追加することはオプションではない場合もあります。

まず、データ構造から有向グラフを作成します。

(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))) 

グラフを作成したら、グラフのルートノードからツリーを生成する必要があります。あなたの例では、1つのルートノード（A）しかありませんが、実際には1つに限定するものはありません。

グラフには、グラフ内のすべてのノードのリストと、エッジの入っているすべてのノードのセットがグラフの特定のノードに格納されます。これらを使用してルートノードを見つけることができます。

(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?を使用してこの条件をテストすることができます。