Pretty printing expression structure in Haskell?

Question

We're given the following data structure for our assignment:

-- Question 2: Expression tree.
data Expr
  = Lit Float
  | Add Expr Expr
  | Sub Expr Expr
  | Mul Expr Expr
  | Div Expr Expr
  | X

Which represents either a floating-point value, an add/sub/mul/div of two sub-trees, or an X which stands for an unknown variable. We have to write a method that will pretty-print the tree. This is what I have so far:

draw :: Expr -> Int -> String
draw (Lit f) _ = show f
draw (X) _ = "X"
draw (Add a b) lvl = indent lvl ++ "(+) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ "|\n" ++ indent lvl ++ "---" ++ draw b (lvl+1) 
draw (Sub a b) lvl = indent lvl ++ "(-) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ "|\n" ++ indent lvl ++ "---" ++ draw b (lvl+1) 
draw (Mul a b) lvl = indent lvl ++ "(*) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ "|\n" ++ indent lvl ++ "---" ++ draw b (lvl+1) 
draw (Div a b) lvl = indent lvl ++ "(/) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ "|\n" ++ indent lvl ++ "---" ++ draw b (lvl+1) 

indent :: Int -> [Char]
indent 0 = []
indent n = "\t"++indent (n-1)

This works for simple trees:

myE2 :: Expr
myE2 = Add (Lit 4) (Sub (Lit 4) (Lit 2))

Prints out as:

*Main> putStr(draw myE2 0)
(+) ---4.0
|
--- (-) ---4.0
     |
     ---2.0

Which is what I intended, however, more complicated trees such as:

myExpr :: Expr
myExpr = (Add (Add (Sub (Mul (Lit 4) (X)) (Lit 1)) (Lit 4)) (Lit 6))

Print out as:

*Main> putStr(draw myExpr 0)
(+) --- (+) ---     (-) ---         (*) ---4.0
            |
            ---X
        |
        ---1.0
    |
    ---4.0
|
---6.0

Can anyone offer advice as to how I may fix this problem?

Answer 1

You can try the following:

data Expr
  = Lit Float
  | Add Expr Expr
  | Sub Expr Expr
  | Mul Expr Expr
  | Div Expr Expr
  | X

draw :: Expr -> Int -> String
draw (Lit f) _ = show f
draw (X) _ = "X"
draw (Add a b) lvl = "(+) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ " |\n" ++ indent lvl ++ " ------" ++ draw b (lvl+1) 
draw (Sub a b) lvl = "(-) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ " |\n" ++ indent lvl ++ " ------" ++ draw b (lvl+1) 
draw (Mul a b) lvl = "(*) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ " |\n" ++ indent lvl ++ " ------" ++ draw b (lvl+1) 
draw (Div a b) lvl = "(/) ---" ++ draw a (lvl+1) ++ "\n" ++ indent lvl ++ " |\n" ++ indent lvl ++ " ------" ++ draw b (lvl+1) 

indent :: Int -> [Char]
indent 0 = []
indent n = "       " ++ indent (n-1)

myE2 = Add (Lit 4) (Sub (Lit 4) (Lit 2))
myE3 = Add (Add (Lit 4) (Lit 3)) (Sub (Lit 4) (Lit 2))
myE4 = Add (Add (Lit 4) (Add (Lit 4) (Sub (Lit 4) (Lit 2)))) (Sub (Lit 4) (Lit 2))
myExpr = (Add (Add (Sub (Mul (Lit 4) (X)) (Lit 1)) (Lit 4)) (Lit 6))

It worked for me for the different conditions that I used. Main change: 1. I changed the "\t" to spcaes. 2. I removed the first indent.

[ghci] putStrLn $ draw myExpr 0
(+) ---(+) ---(-) ---(*) ---4.0
                      |
                      ------X
               |
               ------1.0
        |
        ------4.0
 |
 ------6.0

[ghci] putStrLn $ draw myE4 0
(+) ---(+) ---4.0
        |
        ------(+) ---4.0
               |
               ------(-) ---4.0
                      |
                      ------2.0
 |
 ------(-) ---4.0
        |
        ------2.0

[ghci] putStrLn $ draw myE3 0
(+) ---(+) ---4.0
        |
        ------3.0
 |
 ------(-) ---4.0
        |
        ------2.0

Answer 2

Firstly, do you have to use the expression format style you are currently using? This format requires many nodes to be printed to a single line. If you look at the format used by Data.Tree.Pretty, it only ever prints a single node to any line. If you formatted your code that way, the myExpr would have a format like:

(+)
 |
 +-(+)
 |  |
 |  +-(-)
 |  |  |
 |  |  +-(*)
 |  |  |  |
 |  |  |  +-4
 |  |  |  |
 |  |  |  +-X
 |  |  |
 |  |  +-1
 |  |
 |  +-4
 |
 +-6

This makes the problem much, much simpler, as each node will have one line. All you need to do to print out a node is to know how deep within the tree it is. Eg a node 3 deep will have a line starting with " | | +-". Then print each node from left to right, and you will get the result. Try looking at the source for the Data.Tree.drawTree for some inspiration if you are stuck.

If you do have to stick with your current format, be ready for a lot of work. You will have to dynamically layout the tree depending on the width of the text in each nodes. You will also need to spread out the nodes so you don't get overlap. You will need to consider the whole tree before starting. This is an NP-Complete problem. See this tree article for some more details. This is surely beyond a homework problem though...