Data.Treeを初期化する方法を工夫してみた

詳しいことはそのうち書くとして、ReaderモナドとStateモナドの違いなんかを考えているうちにXMLやHTMLの記述を簡略化するDSLみたいなものがあったらいいなと思ったりしていたら、どちらのブログかは失念してしまったのですが、たしかmoeというライブラリがまさしくそれをやってるということがわかってしまって、ここに書いてあることはまったくの焼き直しになってしまうのですが、まぁなんとか自力でここまでやってきたので、一応かいときます。

スタンダードライブラリの一部に、Data.Treeというのがあって、

Data Tree a = Node { 
	rootLabel :: a
	subForest :: [Node a] }

といった型になっているわけです。

このTree型のデータを初期化したいと思ったら、一番単純な方法はこんなことをやるわけですね:

tree = Node "n1" [
	Node "n2-1" [
		Node "n3-1" [ ], 
		Node "n3-2" [ ] ] ],
	Node "n2-2" [ ] ]

ほかにもData.Treeにはunfold系の関数でTree型のデータを構築できるようになっていたり、TreeはReadのインスタンスだったりするわけですが、コードに直接データを書き込まなきゃいけないときにもうちょっと便利になったらいいなと思って、こんなことができるようにしてみました。

tree = node "n1" $ do
	node "n2-1" $ do
		node_ "n3 -1"
		node_ "n3-2"
	node "n2-2"

main = putStrLn $ drawTree $ buildtree tree

括弧がなくなる分すっきりするのがまぁ、良い所といった感じでしょうか…ほんとはdoだけでやりたかったのですが、$をつけないとコンパイルしてくれません。かといって、ndo = $ do などということは受け付けてくれないだろうし…(って、試したわけではないんですが…)

中身はこんな感じになってます:

import Data.Tree
import Control.Monad.State.Lazy

el :: a -> State ([a] -> [a]) ()
el a = modify (\f -> f . (\as -> a : as))

nul = return ()

node :: a -> State (Forest a -> Forest a) () ->
    State (Forest a -> Forest a) ( )
node a f = el $ Node a (buildForest f)
node_ a = node a nul

buildForest :: State ( [a] -> [a] ) () -> [a]
buildForest f = (snd $ runState (f) id) [ ]

buildTree = head . buildForest

Node型の中身の子Nodeのリストを生成する部分をモナド化しています。

中身としてはStateモナドを使って、ステート値の中にリストを作りこむ関数を構築しています。単純にステート値をForest aにしてしまうという方法を最初はとっていたのですが、難点はできあがったForestの中身の順序が記述と逆に出来上がってしまうので、reverseを呼ぶ羽目になるところです。reverseがいやだなーと思って、いろいろ試しているうちにたどり着いたのが、今回のやつなんですが、上記の方法でも、関数のビルドアップはelの中で逆順につながっているので、コスト的には変わらないように思います。ほんとにコストが気になったらData.Sequenceを使うといいんでしょうか、でも結局リスト方に戻す時点でコストがかかっちゃいますね…さらに、Stateモナドとかいろんなもので元データをくるんでいるので、生のNode型でデータを指定するよりはだいぶコストがかさんでるのかもしれません。簡潔性を追及したかったということで…

モナド型なのでreplicateM_なんかを使って繰り返してみたりとか、guard, when, unlessなんかを使って条件分岐なんかもできますね…

ではでは。