CODEWITHSUNDEEP
haskell
user3324236
user3324236

Reputation: 5

Haskell display Tree without Data.Tree or deriving(show)

Hi guys I'm having an issue with my instance to show a tree in Haskell: here is my code:

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 ++"\n"
show (Branch val l r) = show val ++ "\n" ++" " ++ show l ++ " " ++ show r

here is my test case and output( which is wrong):

 Branch "<" (Branch "<" (Leaf 'a') (Leaf 'c')) (Branch "<" (Leaf 'g') (Branch     "<" (Leaf 'n') (Leaf 'y'))))
 "<"
  "<"
    'a'
    'c'
  "<"
    'g'
  "<"
    'n'
    'y'

the right output

 "<"
  "<"
    'a'
    'c'
  "<"
    'g'
    "<"
      'n'
      'y'

any help would be great!

Upvotes: 1

Views: 1163

Answers (4)

dfeuer
dfeuer

Reputation: 48581

Your Tree type annoys me a little bit because it's a monad but can't be a Monad. Let me fix that for you by flipping the type arguments:

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

display' :: (Show a, Show b) => String -> Tree b a -> String -> String
display' prefix (Leaf a) =
  (prefix ++) . shows a . ('\n' :)
display' prefix (Branch v l r) =
  (prefix ++) . shows v . ('\n' :) . display' prefix' l . display' prefix' r
  where prefix' = ' ' : prefix

display :: (Show a, Show b) => Tree b a -> String
display t = display' ' ' t ""

Upvotes: 0

Zeta
Zeta

Reputation: 105886

Note: This post is written in literate Haskell. Copy it into your favourite editor, save it as Tree.lhs or similar and load it in GHCi.

Let's try a slightly other approach. Instead of showing the tree as a single string, we create the lines of our string:

> 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 tree = magic (go tree)
>      where
>        go :: (Show a, Show b) => Tree a b -> [String]

Don't worry about magic yet, it's going to have the type magic :: [String] -> String. Let us focus on go first. If we want to show a single Leaf, we only have to concern a single value:

>        go (Leaf v)       = [show v]

Now about the branches and their indentation. We can still show the value as in the Leaf case:

>        go (Branch v l r) = show v

but we have to make sure that the actual branches have the correct amount of whitespace in front. We use a (yet to be defined) function called indent:

>                        : indent (go l ++ go r)

Now we've got almost everything in place: if indent does what its name suggests, it's going to indent all the strings in the [String] returned by go l ++ go r by a single space. Therefore, the branches of a tree will always have one more space in the front as the root itself. All that's missing is now indent and magic:

>        indent :: [String] -> [String]
>        indent = map (' ':)

That was rather easy. You can of course exchange (' ':) with something else.

It's now magic's job to take all the strings and glue them together. Since you want to indent the whole tree by a single space, let's use indent a last time:

>        magic = unlines . indent

And that's it. Here's the whole code for a better overview:

instance (Show a, Show b) => Show (Tree a b) where
  show tree = magic (go tree)
    where
      go (Leaf v)       = [show v]
      go (Branch v l r) = show v : indent (go l ++ go r)
      indent            = map (' ':)
      magic             = unlines . indent

The nice part about this technique is that we never have to use explicit levels or state the number of spaces somewhere. We can just walk the tree, create our [String], and have magic and indent do the rest for us.

Upvotes: 1

comingstorm
comingstorm

Reputation: 26097

Your display function has no way of knowing how deeply to indent each line. Prepending a space to your subtrees won't work because they will generally have more than one line.

You need to define an auxiliary function which takes the indentation as a parameter:

indent n x = concat (replicate n " ") ++ show x ++ "\n"

f n (Leaf x) = indent n x
f n (Branch val l r) = indent n val ++ f (n+1) l ++ f (n+1) r

instance (Show a, Show b) => Show (Tree a b) where
  show tree = f 0 tree

Upvotes: 4

Kapol
Kapol

Reputation: 6463

Consider the following:

putStrLn ("First line" ++ "   " ++ "\n" ++ "Second line")

The output is

First line   
Second line

because newline character doesn't keep indentation. You need to find a way to inform show how big of an indent you need for each item you want to print out.

Upvotes: 2

Related Questions