薔薇木

(2009.6)

GHCには薔薇木 (rose tree; multi-way tree; 複数の子を持つ木) クラスが用意されています。Data.Tree

次のように宣言されています。

Haskell
[POPUP]
  1. data Tree a = Node {
  2. rootLabel :: a
  3. subForest :: Forest a
  4. }
  5. type Forest a = [Tree a]

ノードの値はrootLabelで、子の木のリストがsubForestです。

Treeはいくつかのクラスのインスタンスです。

  • Monad, Functor, Typeable1, Traversable, Foldable, Applicative

また、型aが以下のクラスのインスタンスであれば、Tree aもまたそのクラスのインスタンスです。

  • Eq, Data, Read, Show

簡単な木

オブジェクトを作ってみます。

Haskell
[POPUP]
  1. import Data.Tree
  2. t :: Tree Int
  3. t = Node 1 [Node 2 [Node 3 [], Node 4 []], Node 5 []]
  4. main = do
  5. print t
  6. -- Node {rootLabel = 1, subForest = [Node {rootLabel = 2, subForest = ...
  7. print $ flatten t
  8. -- [1,2,3,4,5] ノードそのものが先で、子はその後ろ。

コンパイルは次のようにします。コンパイルには、ghc-containers-devel パッケージが必要です (Fedora 15, ghc 7.0)。

$ ghc tree.hs

木を舐める

ノードの値を足したり、個数を数えたりしてみます。

Haskell
[POPUP]
  1. import Data.Tree
  2. import GHC.PArr
  3. t :: Tree Int
  4. t = Node 1 [Node 2 [Node 3 [Node 6 []], Node 4 [], Node 7[]], Node 5 []]
  5. -- 木のノードの値をすべて足し上げる
  6. sum_tree tree = rootLabel tree + (sum $ map sum_tree $ subForest tree)
  7. -- 足し上げる. 並列バージョン
  8. -- toP で型を変換する。
  9. sum_treeP tree = rootLabel tree + (sumP $ mapP sum_tree $ toP $ subForest tree)
  10. -- 木のノードの個数を数える
  11. length_tree :: Tree a -> Int
  12. length_tree tree = 1 + (sum $ map length_tree $ subForest tree)
  13. -- 木のノードの個数を数える. reduce で。
  14. length_tree2 :: Tree a -> Int
  15. length_tree2 tree = 1 + (foldr (\n result -> result + length_tree2 n) 0 $ subForest tree)
  16. -- 木の高さ
  17. height_tree (Node _ []) = 1
  18. height_tree tree = 1 + (maximum $ map height_tree $ subForest tree)
  19. main = do
  20. print $ sum_tree t
  21. print $ sum_treeP t
  22. print $ length_tree t
  23. print $ length_tree2 t
  24. print $ height_tree t

テキストファイルから木を生成

Problem 67 - Project Euler のtriangle.txtファイル(これはグラフだが)から木オブジェクトを作ってみます。

まず、文字列を区切り文字で区切る関数。

Haskell
[POPUP]
  1. import Data.Tree
  2. -- 文字列などを区切る
  3. split :: (a -> Bool) -> [a] -> [[a]]
  4. split _ [] = []
  5. split p xs = a : case length b of 0 -> []
  6. 1 -> []:[] -- 区切りで終端
  7. otherwise -> split p $ tail b
  8. where
  9. (a, b) = break p xs

後は、テキストを読み込んで、地道に木にします。

Haskell
[POPUP]
  1. -- 木を作る
  2. make_tree text_ary = foldr add_tree [] text_ary
  3. add_tree line result
  4. | null result = make_nodes line
  5. | otherwise = add_children (make_nodes line) result
  6. -- テキストの1行からノードの配列を得る
  7. make_nodes :: String -> [Tree Int]
  8. make_nodes line =
  9. map (\x -> Node (read x) []) $ split (== ' ') line
  10. -- 親に繋いでいく
  11. add_children :: [Tree Int] -> [Tree Int] -> [Tree Int]
  12. add_children [] _ = []
  13. add_children parents@(p:ps) children@(c1:c2:cs) =
  14. (Node (rootLabel p) [c1, c2]) : add_children ps (c2:cs)
  15. main = do
  16. cs <- getContents
  17. print $ make_tree $ lines cs