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

## はじめに

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

```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でディレクトリ構造エディタを作る](https://qiita.com/care0717/items/1978250a6750698999b8)という記事を読み、木構造に変換をしてから操作するのが良さそうだと気がつきました。ところが、肝心の変換をするコードがなかなか見つからず、しばらく悩んだ末に自分なりの答えが見つかったので記事にしてみました。

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

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

## データの定義

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

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

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

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

またTEA[^1]における`Model`の一部として多分木を定義します。

```elm
type alias Model =
    { tree : Tree Node
    }
```

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

## 変換の手順

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

```elm
fromAdjacencyList : List Node -> Tree Node
```

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

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

### 1番目の階層をつくる

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

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

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

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

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

```elm
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`に変換する必要があります。

```elm
zipper : Zipper Node
zipper = Zipper.fromTree newTree1
```

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

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

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

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

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

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

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

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

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

newZipper = Zipper.replaceTree subTree zipper
```

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

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

### N番目の階層をつくる

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

```elm
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
```

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

```elm
newTree1 = foldFunc node1 rootNode

newTree2 = foldFunc node2 newTree1

...

newTreeN = foldFunc nodeN newTree(N-1)
```

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

```elm

newTreeN = foldFunc nodeN (... foldFunc node3 (foldFunc node2 (foldFunc node1 rootNode)))
```
> Haskellと引数の順番が異なっていて一瞬混乱しましたがElmの場合はこの順番でよさそうです

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

```elm
newTreeN = List.foldl foldFunc rootNode data
```

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

```elm
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でディレクトリ構造エディタを作る](https://qiita.com/care0717/items/1978250a6750698999b8)」の記事と同じようなEllieの[サンプル](https://ellie-app.com/7rCFFcmmjnqa1)を用意しましたのでお試しください。
- この木構造をベースに、メ○カリのようなカテゴリー選択をするUIもできてはいるのですがそれはまたの機会に…`Tree`と`Zipper`のおかげで、不具合なく書けたと思います。


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