I am trying to pretty print a binary tree in Haskell so that if you turn your head to the left, it should look like a tree. Each level in the tree should be indented 2 spaces from the previous level.
This is the expected output:
-- 18
-- 17
-- 16
-- 15
-- 14
-- 13
-- 12
-- 11
-- 10
-- 9
-- 8
-- 7
-- 6
-- 5
-- 4
-- 3
-- 2
-- 1
For this tree:
treeB = (Node (Node (Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node (Node Empty 8 Empty) 9 Empty))) 10 (Node (Node (Node Empty 11 Empty) 12 (Node Empty 13 (Node Empty 14 Empty))) 15 (Node (Node Empty 16 Empty) 17 (Node Empty 18 Empty))))
This is how tree is defined:
data BinTree a =
Empty
| Node (BinTree a) a (BinTree a)
deriving (Eq,Show)
However, my result does not look like that. Here is my result:
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
Here is my code:
prettyTree :: (Show a) => BinTree a -> String
prettyTree Empty = "\n"
prettyTree (Node Empty x Empty) = " " ++ show x ++ "\n"
prettyTree (Node Empty x r) = prettyTree' r ++ " " ++ show x ++ "\n"
prettyTree (Node l x Empty) = show x ++ "\n" ++ " " ++ prettyTree' l
prettyTree (Node l x r) = prettyTree' r ++ show x ++ "\n" ++ prettyTree' l
prettyTree' :: (Show a) => BinTree a -> String
prettyTree' Empty = "\n"
prettyTree' (Node Empty x Empty) = " " ++ show x ++ "\n"
prettyTree' (Node Empty x r) = " " ++ prettyTree' r ++ " " ++ show x ++ "\n"
prettyTree' (Node l x Empty) = " " ++ show x ++ " " ++ "\n" ++ prettyTree' l
prettyTree' (Node l x r) = " " ++ prettyTree' r ++ " " ++ show x ++ "\n" ++ " " ++ prettyTree' l
I don't understand what I'm doing wrong. Any help would be greatly appreciated.
I think you need to think more recursively about this problem. Your data structure
data BinTree a =
Empty
| Node (BinTree a) a (BinTree a)
deriving (Eq,Show)
is inherently recursive because it's defined in terms of itself, so we should exploit that. bheklilr's comment about lines is very sensible, but we can take it further. Here's the general plan for how to print a tree:
You're trying to deal with the detail from one layer down by analysing all the cases for whether there's a Node or Empty subtree. Don't. Let recursion do that. Here's how we deal with the empty tree:
Notice that we can still go ahead with the general plan, because if you indent nothing you still get nothing
Great. Now we've got that sorted, we can write some code. First let's sort that indentation thing:
indent :: [String] -> [String]
indent = map (" "++)
So whatever strings there are get " " appended on the front. Good. (Notice that it works on the empty list and leaves it alone.)
layoutTree :: Show a => BinTree a -> [String]
layoutTree Empty = [] -- wow, that was easy
layoutTree (Node left here right)
= indent (layoutTree right) ++ [show here] ++ indent (layoutTree left)
Wasn't that nice? We just did the left, then the current, then the right. Isn't recursion great!
Here's your sample tree again:
treeB = (Node (Node (Node (Node Empty 1 (Node Empty 2 Empty)) 3 (Node Empty 4 Empty)) 5 (Node (Node Empty 6 Empty) 7 (Node (Node Empty 8 Empty) 9 Empty))) 10 (Node (Node (Node Empty 11 Empty) 12 (Node Empty 13 (Node Empty 14 Empty))) 15 (Node (Node Empty 16 Empty) 17 (Node Empty 18 Empty))))
> layoutTree treeB
[" 1"," 2"," 3"," 4"," 5"," 6"," 7"," 8"," 9","10"," 11"," 12"," 13"," 14"," 15"," 16"," 17"," 18"]
You can see we've just made a String representing line for each element, but each line has been indented as many times as it's been included inside another Node.
Now we just need to actually put that together, but that's not hard. Notice that the previous function was easy because this step was left till the end.
prettyTree :: Show a => BinTree a -> String
prettyTree = unlines.layoutTree
We just needed to compose the two functions layoutTree and unlines. (unlines concatenates all the strings with newlines between.)
> putStrLn (prettyTree treeB)
18
17
16
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1