HaskellのData.Treeを使ってみる

関数型言語 Haskell

Tic Tac Toe(○×ゲーム)のゲーム履歴(History)の保存に使えそうな、Data.Treeというデータ型を標準ライブラリから見つけました。自分でほぼ同じものを作ろうとしていたのでちょっと調べてみて使えそうなら使おうと思います。
まず、どんなものか調べてみます。

Prelude> import Data.Tree

Prelude Data.Tree> :info Tree

data Tree a = Node {rootLabel :: a, subForest :: Forest a}

        -- Defined in Data.Tree

instance Eq a => Eq (Tree a) -- Defined in Data.Tree

instance Monad Tree -- Defined in Data.Tree

instance Functor Tree -- Defined in Data.Tree

instance Read a => Read (Tree a) -- Defined in Data.Tree

instance Show a => Show (Tree a) -- Defined in Data.Tree
Tree aというのは、a型のrootLabelというフィールドとForest aというフィールドを持ったNodeで構成されているようです。
さらにForestを調べてみます。
Prelude Data.Tree> :info Forest

type Forest a = [Tree a]        -- Defined in Data.Tree
Forest aというのはTree aのリストだそうです。
だいたい分かりました。Treeというのは子供を何個でも持てる木構造のデータ型のようです。

では、木構造を作ってみましょう。

import Data.Tree
main = putStrLn $ drawTree $ Node "top" [Node "first" [Node "third" [Node "fourth" []]], Node "second" []]


$ runhaskell tree_test.hs

top

|

+- first

|  |

|  `- third

|     |

|     `- fourth

|

`- second
うん、しっかり作れているようです。ちなみに子供を持たないNodeは2番目のフィールドを空リスト[]にします。
では、プログラムから木構造をいじってみましょう。って、どうするんでしょう？


手続き型言語的に子供を追加するNodeを求めてそれに追加しようかと思ったけど無理ですね。変数変更出来ないから途中のNode貰っても何にも出来ない…
ってことは引数で木構造全体を受け取って、子供を追加した木構造をまるごと返すしかない。子供を一つ追加する度に木全体を作り直すわけですね。

ある値が入っているNodeの子供を追加する関数を作ってみました。

-- x 追加する場所 -> y 追加する値 -> z zs ツリー -> 戻り値
insert :: (Eq a) => a -> a -> Tree a -> Tree a
insert x y (Node z zs) = if x == z then Node z (zs ++ [Node y []])
                                   else Node z (map (insert x y) zs)

で、"third"の下に"fives"を追加してみます。

main = putStrLn $ drawTree $ insert "third" "fives" $ Node "top" [Node "first" [Node "third" [Node "fourth" []]], Node "second" []]


top

|

+- first

|  |

|  `- third

|     |

|     +- fourth

|     |

|     `- fives

|

`- second
うん、成功です。でも、こりゃ骨ですね…