elm-monocle Lens/Optionalで多分木操作を隠蔽

前回の記事の発展の内容になります。前回は複雑なデータ構造のgetter, setterを隠蔽するLens, Focusの説明を行いました。今回は典型的なレコードではなく、多分木(multi-way tree)とZipperと呼ばれる多分木の操作をLensの応用機能であるOptionalを利用してgetter, setterを隠蔽していきたいと思います。

多分木(MultiwayTree)とZipper

Elmなどの関数型言語では、Union Types(代数的データ構造)とパターンマッチ、再帰等を利用すると、木構造は簡単に表現でき、扱えることが知られています。

-- 二分木の定義
type Tree a
    = Empty
    | Node a (Tree a) (Tree a)

-- パターンマッチと再帰を利用した木構造の深さを調べる関数
depth : Tree a -> Int
depth tree =
    case tree of
      Empty -> 0
      Node v left right ->
          1 + max (depth left) (depth right)

再帰を利用した手法は、木全体をスキャンするような操作は得意なのですが、指定したノードへのアクセス(取得・更新・削除)となると毎回、全てのノードへのアクセスが発生してしまい、計算量や扱いに難が生じます。

そこで、Zipperと言う、パンくずリスト(辿らなかった部分木)を残しながら、木を操作していくことで計算量を気にすること無く柔軟な走査を行うことができる手法を利用することで問題は解決することができます(詳しい解説は、某すごいHな本にあります)。今回は、elm-multiway-tree-zipperというライブラリを利用したいと思います。扱えるTreeとZipperの型は以下のようになります。

-- 多分木
type Tree a
    = Tree a (Forest a)

type alias Forest a = 
    List (Tree a)

-- Zipper
type Context a
    = Context a (List (Tree a)) (List (Tree a))

type alias Breadcrumbs a = 
    List (Context a)

type alias Zipper a = 
    (Tree a, Breadcrumbs a)

このライブラリを利用すると多分木に対して、以下のような操作が可能になります。

(&>) = flip Maybe.andThen

simpleTree : Tree String
simpleTree =
    Tree "a"
        [ Tree "b"
            [ Tree "e" [] ]
        , Tree "c" []
        , Tree "d" []
        ]

-- 0番目の子ノード(Tree "b")にアクセスし
-- ノードの値を "b" -> "bX" に更新し
-- 木のルートまで戻る
Just (simpleTree, [])
    &> goToChild 0
    &> updateDatum (\old -> old ++ "X") -- Appends an X to "b"
    &> goToRoot

Zipperは「アクセスしたノードが存在しない」などの理由で失敗する可能性があるため、Zipperの多くの関数の戻り値はMaybe (Zipper a)という型で返却されます。

Optional

Zipperライブラリで多分木を操作するのは直感的で楽なのですが、Maybe (Zipper a)という型で値が返却されるために、気軽に値の取り出しや木の更新が行いにくいという問題が発生しました。特にMaybeに包まって返ってくるというのが問題点です。前回は、Lensの使い方で確実にアクセスできるデータ構造を扱っていましたが、今回の例のようにアクセスが不確実な場合にはOptionalという機能を使うようにmonocleには備わっています。Lensと見比べてみると、何のことはありません。get -> getOptionとなり、b -> Maybe bとなっただけです。

type alias Lens a b = 
    { get : a -> b
    , set : b -> a -> a
    }

type alias Optional a b = 
    { getOption : a -> Maybe b
    , set : b -> a -> a
    }

多分木+ZipperでOptional

それでは、多分木+Zipperの操作をOptionalで包んでいきましょう。要するに今回は以下のようなことを目論んでいます。

-- Zipperを経由するので面倒かつ連続的な操作が行いにくい。
Tree a -> Zipper a -> Maybe a
Tree a -> Zipper a -> Tree a

-- Optionalで以下のような扱いがしたい
Tree a -> Optional a

前提

今回Optionalの対象となる多分木は、ノードがdataにString, Index(Int)の列をId(List Int)として持つ木構造となっています。

type alias Index =
    Int


type alias Id =
    List Int


type alias NodeData =
    { id : Id, data : String }


-- 操作対象となる多分木
nodeTree : Tree NodeData
nodeTree =
    Tree { id = [], data = "root" }
        [ Tree { id = [ 0 ], data = "aaa" } []
        , Tree { id = [ 1 ], data = "bbb" } []
        , Tree { id = [ 2 ], data = "ccc" } []
        ]

また、Optional (Tree a)を定義するためのユーティリティ関数群になります。

treeOfZipper : Zipper a -> Tree a
treeOfZipper ( tree, _ ) =
    tree


tree2Zipper : Tree a -> Zipper a
tree2Zipper tree =
    ( tree, [] )


(&>) : Maybe a -> (a -> Maybe b) -> Maybe b
(&>) =
    flip Maybe.andThen



-- id(List index)がある箇所のZipperを特定する。


goToNodeById : Id -> Maybe (Zipper a) -> Maybe (Zipper a)
goToNodeById id mZipper =
    List.foldl (\idx mz -> mz &> Zipper.goToChild idx) mZipper id

そして、以下がIdを起点としたOptionalの定義となります。

nodeOfTreeById : Id -> Optional (Tree a) a
nodeOfTreeById id =
    let
        -- treeをZipper化して、指定されたidまで潜る
        targetZipper tree =
            Just (tree2Zipper tree) |> goToNodeById id

        -- 指定されたidをdataで書き換え、Root Zipperに戻したもの
        replacedZipper tree data =
            targetZipper tree &> (Zipper.replaceDatum data) &> Zipper.goToRoot

        -- 指定されたidのnodeDataを得るgetter
        get tree =
            Maybe.map Zipper.datum (targetZipper tree)

        -- 指定されたidのnodeDateを書き換えるsetter, もし該当箇所が無ければ元のtreeを返す
        set data tree =
            Maybe.withDefault tree (Maybe.map treeOfZipper <| replacedZipper tree data)
    in
        Optional get set

Optionalを定義したお陰で、木の操作がとても簡単に統一出来ていると思います！

node =
    nodeTree |> (nodeOfTreeById [ 1 ]).getOption

-- modify(update)は、チェーン出来る(毎回rootに戻るので微妙に計算量掛かるけど、まあ要素数倍・・・)。

newTree =
    nodeTree
        |> Optional.modify (nodeOfTreeById [ 1 ]) (\nd -> { nd | data = "new bbb" })
        |> Optional.modify (nodeOfTreeById [ 2 ]) (\nd -> { nd | data = "new ccc" })

コードをまとめたものは、こちら

まとめ

今回、多分木とZipperの操作をOptionalで隠蔽してみて、改めて単純ながら強力な機能だと実感することができました。実際もっと楽にするには、Dict Int -> NodeData + 子ノードのように木を辞書の形で持つことだと思いますが、その場合でもmonocle/Optionalは役に立つと思います。自分のケースの場合は、どうしても木構造そのままを連続で変換する事案が発生したので、このような結果となりました。