Haskell: 薔薇木

(2009.6)

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

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

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

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

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

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

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

  • Eq, Data, Read, Show

簡単な木

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

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

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

$ ghc tree.hs

木を舐める

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

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

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

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

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

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

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

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