Elmで隣接リスト(adjacency list)を木構造に変換する

はじめに

ショッピングサイトの商品カテゴリーのような階層型のデータをSQLデータベースで管理する場合には、以下のような隣接リストを用いるのがわかりやすくて一般的です。

CREATE TABLE Category (
  id        SERIAL PRIMARY KEY,
  parent_id BIGINT UNSIGNED,
  name      TEXT,
  FOREIGN KEY (parent_id) REFERENCES Category(id)
)

例えば某ショッピングサイトで出品する際のカテゴリーを調べると、下記のようなデータとなっています。（不要な列は省略してあります）

id      parent_id   name
---------------------------------------
1       0           "レディース"
2       0           "メンズ"
3       1           "トップス"
4       1           "ジャケット/アウター"
5       2           "トップス"
6       2           "ジャケット/アウター"
7       6           "テーラードジャケット"
...

このようなデータからカテゴリーを選択するUIを作成する際に、Listのままでセレクトボックスをレンダリングしイベントのハンドリングをしていたのですが、Elmでディレクトリ構造エディタを作るという記事を読み、木構造に変換をしてから操作するのが良さそうだと気がつきました。ところが、肝心の変換をするコードがなかなか見つからず、しばらく悩んだ末に自分なりの答えが見つかったので記事にしてみました。

木構造にも色々な種類がありますが、カテゴリーのような複数の子を持つ階層構造の場合、先の記事でも使われている多分木(multi-way tree/rose tree)と呼ばれるデータ構造が使われます。多分木はTree a (List (Tree a))といった再帰を伴う構造です。イミュータブルな関数型言語において木構造の任意のデータにアクセスする場合、毎回先頭から辿らなければなりませんが、これを効率よくするためにZipperというデータ構造が用意されています。詳細についてはelm-monocle Lens/Optionalで多分木操作を隠蔽の記事の前半部分や次のパッケージのドキュメントをご参照ください。

TreeをキーワードにElmのパッケージサイトで検索をすると、多数のパッケージがヒットして迷ってしまいますが、この記事ではhttps://package.elm-lang.org/packages/zwilias/elm-rosetree/1.5.0/を使いました。

データの定義

先程のテーブルの各行を次のようなレコード型として定義します。

type alias Node =
    { id : Int
    , parentId : Int
    , name : String
    }

すると元となるデータの全体は下記のようになります。

data : List Node
data =
    [ Node 1 0 "レディース"
    , Node 2 1 "トップス"
    , Node 3 2 "ポロシャツ"
    ...

またTEA¹におけるModelの一部として多分木を定義します。

type alias Model =
    { tree : Tree Node
    }

ここではどちらもNode型を使っていますが同じ型である必要はありません。

変換の手順

目的はdataをModel.treeに変換することで、次のような型をもつ関数が必要であることに気がつきます。

fromAdjacencyList : List Node -> Tree Node

こういった場合にElmのような言語では再帰の考え方が重要となってくるのですが、長年forループに慣れた頭ですと混乱しやすいため、まずは愚直にコードを書いてみます。

dataの各要素にはparentIdが含まれていますので、Model.treeの中から該当するidを持つノードを見つけてその子ノードとして追加してけば良さそうです。

1番目の階層をつくる

まずは木構造の根となるrootNodeを定義します（Model.treeの初期値にもなります）。

rootNode : Tree Node
rootNode =
    Tree.singleton
        { id = 0
        , parentId = 0
        , name = "ルート"
        }

Tree.singleton関数は子ノードが空のリストであるノードを生成します。次にdataの最初の要素は

node1 : Node
node1 = 
    { id = 1
    , parentId = 0
    , name = "レディース"
    }
-- 以下では便宜的に同じようにnode2,node3としてdataの各要素を参照します。

となりますので、id == 0であるノードすなわちrootNodeの子ノードとして追加します。

newTree1 = Tree.prependChild (Tree.singleton node1) rootNode

ここで追加なのでTree.appendChildという関数を使いたくなりますが、パッケージのドキュメントを読むと、実際の処理がchildren ++ [ newChild ]となって効率が悪いため推奨されていません。特別な理由がない限り、Tree.prependChildを使うのが良いとされています。

2番目の階層をつくる

2番目の要素node2はparentId == 1であるため、newTree1の中でid == 1であるノードを探し、その子ノードとして追加します。Elmでは全てイミュータブルなためrootNodeではなくてnewTree1に追加する必要があります。ここで登場するのがTree.Zipperに定義された

findFromRoot : (a -> Bool) -> Zipper a -> Maybe (Zipper a)

という関数です。最初の引数の条件を満たすノードをZipper aの中から探して、結果をMaybe (Zipper a)として返す関数です。まずはnewTree1をZipper Nodeに変換する必要があります。

zipper : Zipper Node
zipper = Zipper.fromTree newTree1

ここで探しているのはnode2の親となりうる要素、すなわち木構造の中でidがnode2.parentIdと同じであることが条件となりますので、

maybeZipper 
    = findFromRoot (\node -> node.id == node2.parentId) zipper

となります。この関数の返り値はMaybe (Zipper Node)となるため、パターンマッチの登場です。

newTree2 =
    case maybeZipper of
        Nothing ->
            newTree1
        Just zipper ->
            prependNodeToZipper node2 zipper 
                |> Zipper.toTree

Nothingの場合はノードが孤児状態ということで本来はありえないはずなのですが²、ここではノードの追加は諦めて元のnewTree1をそのまま返します。一方Just zipperの場合のzipperは木構造を辿って見つけた、条件に一致するノードに注目した状態となります。これでnode2を追加するべきノードが見つかりました。

-- Zipper.tree : Zipper a -> Tree a
-- Zipperがフォーカスしているノードを起点にTreeに変換

subTree = Zipper.tree zipper
    |> Tree.prependChild (Tree.singleton node2)

次に、Zipper.treeでzipperが注目しているノードを起点とするTreeに変換して全体の木構造から分離し、新しく作られた木構造の子ノードとしてnode2を先程と同じように追加します。このsubTreeをzipperが注目している位置にある木構造と置き換えます。

-- replaceTree : Tree a -> Zipper a -> Zipper a
-- Zipperがフォーカスしているノードを新しいノードで置換

newZipper = Zipper.replaceTree subTree zipper

これらをまとめて関数にすると以下のようになります。

prependNodeToTree : Node -> Zipper Node -> Zipper Node
prependNodeToTree node zipper = 
    Zipper.replaceTree (
        Zipper.tree zipper
            |> Tree.prependChild (Tree.singleton node)
        ) zipper

N番目の階層をつくる

2番目の階層の場合と同じですが、これまで分割して書いてきた処理を下記のような関数にまとめて書くことができます。

foldFunc : Node -> Tree Node -> Tree Node
foldFunc nodeN tree =
    case Zipper.findFromRoot (\node -> node.id == nodeN.parentId) (Zipper.fromTree tree) of
        Just zipper ->
            prependNodeToTree nodeN zipper
                |> Zipper.toTree

        Nothing ->
            tree

この関数を使ってこれまでの処理を書き直してみると、

newTree1 = foldFunc node1 rootNode

newTree2 = foldFunc node2 newTree1

...

newTreeN = foldFunc nodeN newTree(N-1)

となりますが、実際には以下のように再帰的に関数foldFuncを適用していることがわかります。

newTreeN = foldFunc nodeN (... foldFunc node3 (foldFunc node2 (foldFunc node1 rootNode)))

Haskellと引数の順番が異なっていて一瞬混乱しましたがElmの場合はこの順番でよさそうです

こういった繰り返し関数を適用するのに便利な関数List.foldlが用意されています。

newTreeN = List.foldl foldFunc rootNode data

ここではdataの要素を一つ一つ取りだして関数foldFuncを適用しその結果を次の要素と組み合わせてリストの終わりで繰り返し適用していきます。rootNodeは木構造の初期値となります。求めていた関数として書き出して完成です！

fromAdjacencyList : Tree Node -> List Node -> Tree Node
fromAdjacencyList acc list =
    List.foldl foldFunc acc list 

-- または

fromAdjacencyList : Tree Node -> List Node -> Tree Node
fromAdjacencyList =
    List.foldl foldFunc 

おわりに

一通り説明をさせていただきましたが、文才がないため読みづらかったらすみません。最初はやっぱり紙に書いてあーだこーだ考えてブラッシュアップしていくのが良さそうです。そして、ある程度形になったら、実際にコードとして書いて試していくわけですが、Elmのコンパイラが優秀なおかげで、手書きと同じような感覚で進められるのがとても素晴らしいと思います。最後の方はだいぶ手抜きになってきた気もしますが不慣れなためご勘弁（汗

• 「Elmでディレクトリ構造エディタを作る」の記事と同じようなEllieのサンプルを用意しましたのでお試しください。
• この木構造をベースに、メ○カリのようなカテゴリー選択をするUIもできてはいるのですがそれはまたの機会に…TreeとZipperのおかげで、不具合なく書けたと思います。

1. The Elm Architecture : https://guide.elm-lang.jp/architecture/ ↩

2. データベースから受け取ったデータは、必ずしも階層の順番に並んでいるとは限りませんので、そのまま使うと孤児が発生する可能性があります。データベース側に階層の深さも一緒に記録してあるはずなので、そちらを基準にソートしてから適用すれば孤児は発生しないはずです。もし孤児が発生するとすれば、それは元になるデータに問題があるわけですが、クライアントサイドでエラー処理が必要かもしれません。 ↩