Show Tree Haskell [duplicate]

Question

Consider the following data type

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

I'm trying to define an instance of Show (without importing any modules or using deriving) that would display the tree like so

Main*> let a = Branch "x" (Branch "y" (Leaf 4) (Leaf 7)) (Leaf 9)
Main*> a
"x"
     "y"
          4
          7
     9

So far, this is what I've come up with

findDepth (Leaf a) = 0
findDepth (Branch a (b) (c)) = 1 + (max (findDepth b) (findDepth c))
data Tree a b = Branch b (Tree a b) (Tree a b) | Leaf a
instance (Show a, Show b) => Show (Tree a b) where
     show (Leaf x) = show x
     show (Branch a (b) (c)) =
          show a ++ "\n" ++ s2 ++ show b ++ "\n" ++ s2 ++ show c ++ "\n" ++ s1
               where
                    d = findDepth (Branch a (b) (c))
                    s1 = addSpace (d-1)
                    s2 = addSpace d
                    addSpace n = replicate n '\t'

Unfortunately, this indents the nodes with the lowest depth the most and the highest depth nodes the least. I know that the findDepth function should actually be giving leaf the greatest value and branch the lowest value, but can't figure out a way to write the function recursively for both arguments. Any suggestions?

Answer 1

Actually, there is no need for additional findDepth function - you could easily traverse through the tree and increase the depth each time you shows the children:

import Text.Printf

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

instance (Show a, Show b) => Show (Tree a b) where
  show = showAtLevel 0
    where
      showAtLevel l (Leaf x) = addSpace l ++ show x
      showAtLevel l (Branch x (lt) (rt)) = printf "%s%s\n%s\n%s" (addSpace l) (show x) (showAtLevel (l + 1) lt) (showAtLevel (l + 1) rt)
      addSpace = flip replicate '\t'

Test cases:

*Main>  let a = Branch "x" (Branch "y" (Leaf 4) (Leaf 7)) (Leaf 9)
*Main> a
"x"
    "y"
        4
        7
    9
*Main> Branch "x" (Branch "y" (Leaf 4) (Branch "z" (Leaf 42) (Leaf 314))) (Leaf 9)
"x"
    "y"
        4
        "z"
            42
            314
    9

Answer 2

Here's a hint without he whole solution: Write a single function showWithDepth :: Int -> Tree -> String that passes down the "accrued depth" so far. Then you can write show = showWithDepth 0.

Note that in general you shouldn't write show instances like this, as its "semi-standard" that show instances should work essentially like the derived ones and generate something resembling valid Haskell code. (And additionally, in the presence of a Read instance, we want read . show === id.