私はツリーデータ型を持っています：
data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a
Show...そして、を使用せずに、それをのインスタンスにする必要がありますderiving。2枚の葉のある小さな枝をうまく表示するのは簡単であることがわかりました。
instance (Show a, Show b) => Show (Tree a b) where
show (Leaf x) = show x
show (Branch val l r) = " " ++ show val ++ "\n" ++ show l ++ " " ++ show r
しかし、どうすれば素敵な構造を任意のサイズのツリーに拡張できますか？間隔を決定するには、必要なすべてのスペースを割り当てて作業を進めるために、一番下にある葉の数（または合計で葉の数）を知る必要があるようです。 ' おそらくサイズ関数を呼び出す必要があります。これは実行可能であることがわかりますが、それが実際よりも難しくなっているのでしょうか。
drawTree基本Data.Treeモジュールで機能を調べることができます。恥知らずにインポートすると、次のようになります。
import Data.Tree hiding (Tree )
data Tree a b = Branch b (Tree a b) (Tree a b)
| Leaf a deriving (Eq,Ord,Show)
toDataTree (Leaf a) = Node a []
toDataTree (Branch b cs ds) = Node b [toDataTree cs, toDataTree ds]
d = Branch "1" (Branch "11" (Leaf "111") (Leaf "112"))
(Branch "12" (Leaf "121") (Leaf "122"))
e = toDataTree d
f = putStrLn $ drawTree e
{-
*Main> f
1
|
+- 11
| |
| +- 111
| |
| `- 112
|
`- 12
|
+- 121
|
`- 122
-}
ソースへのアプリケーションのリンクを使用して、Data.Tree私はこれを思いついた。私はそれについてもっと学ぶことができるように自分で書きたかったのです。ソースのdrawTreeメソッドは、複数の子を持つノードで機能するように一般化されています。私は二分木のためだけです。
注：私のツリー定義は、OPのものとは少し異なります。typeパラメーターが何に使用されるのかよくわかりませんaが、アプローチは同じである必要があります
data Tree a
= Branch (Tree a) a (Tree a)
| Leaf
prettyprint (Leaf)
= "Empty root."
-- unlines concats a list with newlines
prettyprint (Branch left node right) = unlines (prettyprint_helper (Branch left node right n h))
prettyprint_helper (Branch left node right)
= (show node) : (prettyprint_subtree left right)
where
prettyprint_subtree left right =
((pad "+- " "| ") (prettyprint_helper right))
++ ((pad "`- " " ") (prettyprint_helper left))
pad first rest = zipWith (++) (first : repeat rest)
prettyprint_helper (Leaf)
= []
のような木を生成します
4
+- 8
| +- 9
| | +- 10
| `- 6
| +- 7
| `- 5
`- 2
+- 3
`- 1
pad関数がどのように機能するかを説明したかったのですが、それは私が理解するのが最も困難だったためです（shiftソースで呼び出されています）。
まず、zipWith関数（最初の引数）を適用して、2つのリストを「結合」します。zipWith (+) [1, 2, 3] [4, 5, 6]戻り[5, 7, 9]ます。リストの1つが空になると停止します。zipWith1つのリストにのみ適用すると、2番目のリストをzip形式で圧縮するために適用できる関数が返されます（これは関数カリー化として知られていると思います）。pad関数のより単純なバージョンは次のとおりです。
> let pad = zipWith (++) (repeat " ")
> :type pad
pad :: [[Char]] -> [[Char]]
> pad ["1", "2", "3"]
[" 1", " 2", " 3"]
注意：1。リストの1つは無限大（repeat " "）ですが、リストの1つが空になると圧縮が停止します。2。zipWith関数とリストのみを取ります。pad次に、文字/文字列のリストのリストを取得し、文字/文字列のリストのzipリストを返す関数です。したがってpad、1つのリストに適用して、最初のリストで圧縮します。
それでは見てみましょう
prettyprint_subtree left right =
((pad "+- " "| ") (prettyprint_helper left))
++ ((pad "`- " " ") (prettyprint_helper right))
(pad "+- " "| ")のような無限のリストを作成します["+- ", "| ", "| ", "| ", ...]。(prettyprint_helper right)右側のルートノードから始めて、右側のサブツリーを表す行のリストを作成します。ただし、そのツリー全体を右にシフトする必要があります。パディングでそれを圧縮することによってそれを行います。サブツリーの大きさがわからないため、無限リストを使用します。"| "余分な行を埋めるのに十分なsが常にあります（これは遅延評価のためにも機能します）。最初の行に注意してください。つまり、subtree-root-nodeには、"+- "代わりに、右側のノードの「表記」が埋め込まれます。
左側はほぼ同じです。左側のノードの表記はです"`- "。他の唯一の違いはパディングです。" "の代わりに"| "。では、なぜノードを離れるのに「ブランチ」が必要ないのでしょうか。さて、あなたはそれを右のノードの後ろ（パディングが追加されています;左側にあります）が下の左のノードに行くと考えることができます。左側のノード/サブツリーを親ノードに接続するには、右側の後ろにパディングが必要です。おそらく親ツリーを除いて、ツリーの左側の後ろには何もありません。これが私の最後のポイントになります。関数内の行のリストとして表されるすべてのサブツリーは、prettyprint_helperすべての親ツリーを上にパディングする追加レベルを取得します。例を挙げて説明するのが一番いいと思います。
上記のツリーを作成する際（特に遅延評価では、実行順序が正確にはわかりませんが、これは、なぜそれが機能するのかを視覚化するのに役立つだけです）：
に再帰するとし10ます。左側のサブツリーと右側のサブツリーは空なので、をprettyprint_helper (Branch Leaf 10 Leaf)返します["10"]。
今、私たちはまでです9。サブツリーは次のとおりです:("9" : ([] ++ ((pad "+- " "| ") [10]))左側なし）、または"9" : ["+- 10"]、または：
9
+- 10
今、私たちはまでです8。((pad "+- " "| ") (prettyprint_helper right))作成：
+- 9
| +- 10
自分でトレースできますが、左側は次のとおりです。
6
+- 7
`- 5
どのパッドに（最初の要素"`- "、残り" "）：
`- 6
+- 7
`- 5
したがって、左側が右側に追加された8の場合、次のようになります。
8
+- 9
| +- 10
`- 6
+- 7
`- 5
1つ上のステップに進むと、この8サブツリーに4ツリーが埋め込まれ、反対側をトレースして機能することを確認できます。あなたが得る
+- 8
| +- 9
| | +- 10
| `- 6
| +- 7
| `- 5
そして、最終的な結果は上記のとおりです。このプロセス全体を通して、ツリーは行のリストとして表されることを忘れないでください。最後にのみ、と一緒になりunlinesます。サブツリーが複数行の文字列として渡されているように見える可能性があるため、おそらく私の描画は誤解を招く可能性があります。これを理解すると、の関数の"|"ように、左右のノードの間に余分なブランチ（）を追加するのは非常に簡単です。私はあなたにそれを理解させます:)Data.TreedrawTree
これが過剰な場合はお詫び申し上げます。初心者としてソースから理解するのは非常に難しく、これは私にとって大きなジャンプでした。この問題を解決しようとしている他の誰かに役立つことを願っています。
さらに別の実装：
───"a"
└──"b"
└──"c"
| ┌──"g"
| ┌──"c"
| | └──"f"
| ┌──"a"
| | | ┌──"e"
| | └──"b"
| | └──"d"
| ┌──"x"
| | | ┌──"g"
| | | ┌──"c"
| | | | └──"f"
| | └──"a"
| | | ┌──"e"
| | └──"b"
| | └──"d"
| ┌──"f"
└──"d"
import Data.List
data Btree a = Empty | Node a (Btree a) (Btree a) deriving Show
tr_l = Node "b" (Node "d" Empty Empty) (Node "e" Empty Empty)
tr_r = Node "c" (Node "f" Empty Empty) (Node "g" Empty Empty)
tr = Node "a" tr_l tr_r :: Btree String
tx = Node "x" tr tr
trr = Node "a" (Node "b" (Node "c" (Node "d" Empty (Node "f" Empty tx)) Empty) Empty) Empty:: Btree String
data ParentDir = PLeft | PRight | NoParent deriving (Show,Eq)
type ParentPos = Int
type Level = Int
dline = '|'
factor = 4
m c1 c2 = if c1 == dline then c1 else c2
zipWith' f xs [] = xs
zipWith' f [] xs = xs
zipWith' f (x:xs) (y:ys) = f x y : zipWith' f xs ys
build_line pd a pp level = foldl (zipWith' m) "" (((++"|").(flip replicate ' ') <$> (factor*) <$> pp)++[(replicate (factor*level) ' ')++cn++show a])
where cn = case pd of PLeft -> "└──"
PRight -> "┌──"
NoParent -> "───"
tprint :: Show a => ParentDir -> [ParentPos] -> Level -> Btree a -> [String]
tprint _ _ _ Empty = []
tprint pd pp level (Node a l r) = tprint PRight new_pp_r (level+1) r ++
[build_line pd a pp level] ++
tprint PLeft new_pp_l (level+1) l
where new_pp_r = case pd of PRight -> pp
PLeft -> pp++[level]
NoParent -> pp
new_pp_l = case pd of PRight -> pp++[level]
PLeft -> pp
NoParent -> pp
printt t = putStr $ (intercalate "\r\n" (tprint NoParent [] 0 t))++"\r\n"