1章P1：Tree型の表示について

http://fop.sampou.org/chap01.html に載ってるものの説明．

import qualified Data.Tree as T

data (Ord a) => Tree a = Null | Fork a (Tree a) (Tree a)
 
drawTree :: (Ord a, Show a) => Tree a -> String
drawTree = T.drawTree . conv
  where 
    conv Null = T.Node "Null" []
    conv (Fork x a b) = T.Node (show x) (map conv [a,b])
 
instance (Ord a, Show a) => Show (Tree a) where
  show = drawTree

Data.Treeの説明

http://users.skynet.be/jyp/html/base/Data-Tree.html より．

data Tree a = Node {
  rootLabel :: a
  subForest :: (Forest a)
}

drawTree :: Tree String -> String

実際に表示させてみた

tree1 = (Fork 1 (Fork 2 Null Null) (Fork 3 Null Null))
main = print $ tree1

とやったときの表示を以下に示す．

deriving Show とやったとき

Fork 1 (Fork 2 Null Null) (Fork 3 Null Null)

drawTree を使ったとき

この方法では，左側の部分木が先，すなわち，上の行に，右側の部分木が後，すなわち，下の行に印字されることに注意すること．

1
|
+- 2
|  |
|  +- Null
|  |
|  `- Null
|
`- 3
   |
   +- Null
   |
   `- Null

適当に手で評価したのを見てみる．評価順序がぐちゃぐちゃなのはご愛嬌．

drawTree (Fork 1 (Fork 2 Null Null) (Fork 3 Null Null))
T.drawTree . conv (Fork 1 (Fork 2 Null Null) (Fork 3 Null Null))
--ややこしいので関数合成を変換
T.drawTree $ conv (Fork 1 (Fork 2 Null Null) (Fork 3 Null Null))
T.drawTree $ T.Node (show 1) (map conv [(Fork 2 Null Null), (Fork 3 Null Null)])
T.drawTree $ T.Node "1" (map conv [(Fork 2 Null Null), (Fork 3 Null Null)])
T.drawTree $ T.Node "1" [conv (Fork 2 Null Null), conv (Fork 3 Null Null)]
T.drawTree $ T.Node "1" [T.Node "2" (map conv [Null, Null]), T.Node "3" (map conv [Null, Null])]
T.drawTree $ T.Node "1" [T.Node "2" [T.Node "Null" [], T.Node "Null" []], T.Node "3" (map conv [Null, Null])]
T.drawTree $ T.Node "1" [T.Node "2" [T.Node "Null" [], T.Node "Null" []], T.Node "3" [T.Node "Null" [], T.Node "Null" []]]