LoginSignup
13
7

More than 5 years have passed since last update.

ClojureAdvent Calendar 2016Day 16
@ayato_p

Clojureで木構造を扱う

Posted at

一般的な業務アプリケーションを開発している際、木構造というのはいたるところに出てきて開発者の頭を悩ませます。 例えば会社の組織なんかは典型的な木構造になると思うので、そのあたりに近いアプリケーションを開発されている方も良く遭遇したりするのではないでしょうか。

というわけで今回は色々考えてたんですが、実用的話題として木構造を Clojure で扱うという話を書きたいと思います。

木構造をナイーブツリーなデータへと変換する

例えば次のような木構造のデータがあったとします。

[{:id :A}
  [{:id :B} {:id :C} {:id :D}]
  [{:id :E} [{:id :F} {:id :G}]]
  {:id :H}
  [{:id :I} {:id :J}]]

だいたい、どういう感じのデータか分かりますよね？

もしかしたらちょっと分かり難いかもしれないので、 clojure.spec で記述してみるとこんな感じでしょうか。

(s/def ::tree
  (s/or :leaf ::leaf
        :node (s/cat :parent ::leaf
                     :children (s/* ::tree))))

ここで ::leaf の定義は一旦忘れましょう。たぶん map? とかそんな感じです。こうすると意味がだいぶ分かりますよね。ちなみに spec を書きましたが、この記事のこれ以降では全く利用しません。

こういうデータをデータベースに保存したいとしましょう。木構造では親と子の関係も表現されているので、当然それもデータベースのレコードに落とし込みたいです。

木構造をデータベースに保存する場合、経路列挙や入れ子集合などやり方が色々とありますが、今回は最も簡単なナイーブツリーに変換したいと思います。 つまり、次のようなデータに変換します。

[{:id :A :parent-id nil}
 {:id :B :parent-id :A}
 ;; ...
 ]

Clojure には木構造を辿るためのネームスペースが clojure.zip として用意されているのでそれを使います。

(require '[clojure.zip :as z])

(defn tree-structure->naive-tree [tree]
  (flatten
   (loop [loc (z/vector-zip tree)
          prev-branch? true]
     (cond
       (z/end? loc) (z/root loc)
       (z/branch? loc) (recur (z/next loc) true)
       :else (recur (-> (if prev-branch? (-> loc z/up) loc)
                        z/leftmost
                        z/node
                        :id
                        (->> (z/edit loc assoc :parent-id))
                        z/next)
                    false)))))

こんな感じの関数が作れるので、これを使うと最初のデータは次のようになります。

(require '[clojure.test :as test])

(test/is
 (= (tree-structure->naive-tree
     [{:id :A}
      [{:id :B} {:id :C} {:id :D}]
      [{:id :E} [{:id :F} {:id :G}]]
      {:id :H}
      [{:id :I} {:id :J}]])
    [{:id :A :parent-id nil}
     {:id :B :parent-id :A}
     {:id :C :parent-id :B}
     {:id :D :parent-id :B}
     {:id :E :parent-id :A}
     {:id :F :parent-id :E}
     {:id :G :parent-id :F}
     {:id :H :parent-id :A}
     {:id :I :parent-id :A}
     {:id :J :parent-id :I}]))
;; true

良さそうですね。利用していた関数の紹介をします。

  • clojure.zip/vector-zip
    • ネストしたベクタを clojure.zip で扱える形式のデータを返却するための関数です。この関数が返すデータの初期位置はルートにいることになっています。
  • clojure.zip/end?
    • 木構造を探索している中で現在位置が深さ優先探索において、終端である場合に真を返します。
  • clojure.zip/root
    • 木構造のルートを返却します(つまり、全体)。この関数を呼び出した場合、 clojure.zip/edit で起こした全ての変更を適用します。
  • clojure.zip/branch?
    • 現在位置のノードがブランチ(この例の場合、ベクタ)である場合、真を返します。
  • clojure.zip/up
    • 現在位置のノードの親にあたる位置を返します。
  • clojure.zip/leftmost
    • 現在位置のブランチの中で最左端にあるノードを返します。
  • clojure.zip/node
    • 現在位置のノードの値を返します。
  • clojure.zip/edit
    • 現在位置のノードを編集します。この変更はすぐには反映されません。
  • clojure.zip/next
    • 次の位置にあるノードを返します。このとき次は深さ優先で探索されます。

ここでやっていたことを簡単に説明すると clojure.zip/next が深さ優先で探索するのを利用して、単純な loop / recur で処理できるように落し込んでいます。 元の木構造の表現方法に従って、直前のノードがブランチであった場合は現在位置のノードの親のブランチ内の最左端にあるノードをそのノードの親として扱い、そうでなければ現在位置のノードのブランチ内の最左端を親とするようにします(日本語が難しい)。

木構造を辿りながら親の id を付けていき、 clojure.zip/root で変更を適用した木全体を返却し、 flatten でネストしていた構造を平滑化しています。

とても簡単ですね。

ナイーブツリーなデータを木構造へと変換する

今度は逆です。データベースから取得したナイーブツリーなデータを木構造へと変換します。

つまり、このデータを…

[{:id :A :parent-id nil}
 {:id :B :parent-id :A}
 {:id :C :parent-id :B}
 {:id :D :parent-id :B}
 {:id :E :parent-id :A}
 {:id :F :parent-id :E}
 {:id :G :parent-id :F}
 {:id :H :parent-id :A}
 {:id :I :parent-id :A}
 {:id :J :parent-id :I}]

こうしたいわけですね。

[{:id :A :parent-id nil}
 [{:id :B :parent-id :A}
  {:id :C :parent-id :B}
  {:id :D :parent-id :B}]
 [{:id :E :parent-id :A}
  [{:id :F :parent-id :E} {:id :G :parent-id :F}]]
 {:id :H :parent-id :A}
 [{:id :I :parent-id :A} {:id :J :parent-id :I}]]

こんな感じの関数を書けば、いけそうな気がします。

(defn bad-naive-tree->tree-structure [tree]
  (let [dependents (group-by :parent-id tree)]
    (letfn [(make-tree [{:keys [id parent-id] :as m}]
              (if-let [dependents' (get dependents id)]
                (apply conj [m] (map make-tree dependents'))
                m))]
      (make-tree (first (get dependents nil))))))

実際に使ってみるとこれは動作します。

(bad-naive-tree->tree-structure
 [{:id :A :parent-id nil}
  {:id :B :parent-id :A}
  {:id :C :parent-id :B}
  {:id :D :parent-id :B}
  {:id :E :parent-id :A}
  {:id :F :parent-id :E}
  {:id :G :parent-id :F}
  {:id :H :parent-id :A}
  {:id :I :parent-id :A}
  {:id :J :parent-id :I}])
;; [{:id :A, :parent-id nil}
;;  [{:id :B, :parent-id :A}
;;   {:id :C, :parent-id :B}
;;   {:id :D, :parent-id :B}]
;;  [{:id :E, :parent-id :A}
;;   [{:id :F, :parent-id :E} {:id :G, :parent-id :F}]]
;;  {:id :H, :parent-id :A}
;;  [{:id :I, :parent-id :A} {:id :J, :parent-id :I}]]

ですが、内部で直接的な再帰呼び出しを利用しているためある一定以上のデータを与えるとスタックオーバーフローが発生します。

(let [tree (->> (range 1000)
                (map (comp keyword str))
                (partition 2 1)
                (map #(hash-map :id (second %) :parent-id (first %)))
                (cons {:id :0 :parent-id nil}))]
  (bad-naive-tree->tree-structure tree))
;; StackOverflowError   clojure.lang.RestFn.applyTo (RestFn.java:130)

というわけでこれを clojure.zip の関数を利用して書き換えます。

(require '[clojure.zip :as z])

(defn naive-tree->tree-structure [tree]
  (let [dependents-map (group-by :parent-id tree)
        root (first (get dependents-map nil))]
    (loop [loc (z/vector-zip [root])
           [node & rest-nodes] (get dependents-map (:id root))
           dependents-list ()]
      (cond
        (and (nil? node) (empty? dependents-list)) (z/root loc)
        (nil? node) (recur (z/up loc) (peek dependents-list) (pop dependents-list))
        :else (if-let [dependents (seq (get dependents-map (:id node)))]
                (recur (-> loc (z/append-child []) z/down z/rightmost (z/append-child node))
                       dependents
                       (conj dependents-list rest-nodes))
                (recur (z/append-child loc node) rest-nodes dependents-list))))))

(naive-tree->tree-structure
 [{:id :A :parent-id nil}
  {:id :B :parent-id :A}
  {:id :C :parent-id :B}
  {:id :D :parent-id :B}
  {:id :E :parent-id :A}
  {:id :F :parent-id :E}
  {:id :G :parent-id :F}
  {:id :H :parent-id :A}
  {:id :I :parent-id :A}
  {:id :J :parent-id :I}])
;; [{:id :A, :parent-id nil}
;;  [{:id :B, :parent-id :A}
;;   {:id :C, :parent-id :B}
;;   {:id :D, :parent-id :B}]
;;  [{:id :E, :parent-id :A}
;;   [{:id :F, :parent-id :E} {:id :G, :parent-id :F}]]
;;  {:id :H, :parent-id :A}
;;  [{:id :I, :parent-id :A} {:id :J, :parent-id :I}]]

ここまでは最初の bad-naive-tree->tree-structure と変わりませんが、大きなデータを渡してみましょう。

(let [tree (->> (range 1000)
                (map (comp keyword str))
                (partition 2 1)
                (map #(hash-map :id (second %) :parent-id (first %)))
                (cons {:id :0 :parent-id nil}))]
  (naive-tree->tree-structure tree))
;; [{:id :0, :parent-id nil}
;;  [{:id :1, :parent-id :0}
;;   [{:id :2, :parent-id :1}
;;    [{:id :3, :parent-id :2}
;;     [{:id :4, :parent-id :3}
;;      [{:id :5, :parent-id :4}
;;       [{:id :6, :parent-id :5}
;;        [{:id :7, :parent-id :6}
;;         [{:id :8, :parent-id :7}
;; ... 略

良さそうですね。

ここで新しく登場した関数は次の通りです。

  • clojure.zip/down
    • 現在位置のノードの子の最左端の位置を返します。
  • clojure.zip/append-child
    • 現在位置のノードの子の最右端にアイテムを挿入します。現在位置は変わらないことに注意します。

この関数を日本語で説明するの難しいのでコードを読んでなんとなくこんなことしてるんだなーと感じてもらえたらと思います。

まとめ

clojure.zip の関数を利用すれば、木構造を走査する場合であっても普段書いているような Clojure の綺麗なコードを維持することが出来ます。

木構造と格闘する機会はもしかしたらそんなに多くないかもしれませんが、もしそのような機会があれば思い出して使ってみたらいいのではないでしょうか。

参考

13
7
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
13
7