Nicely printing/showing a binary tree in Haskell

Question

I have a tree data type:

data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a

...and I need to make it an instance of Show, without using deriving. I have found that nicely displaying a little branch with two leaves is easy:

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

But how can I extend a nice structure to a tree of arbitrary size? It seems like determining the spacing would require me to know just how many leaves will be at the very bottom (or maybe just how many leaves there are in total) so that I can allocate all the space I need there and just work 'up.' I would probably need to call a size function. I can see this being workable, but is that making it harder than it is?

Answer 1

You might study the drawTree function in the base Data.Tree module. Just shamelessly importing it would give you something like this:

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
-}