哈斯克爾漂亮的打印表達結構？

Question

我們給出了我們的分配數據結構如下：

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

這代表一個浮點值，加/子/ MUL /兩子樹格，或代表一個X一個未知的變量。我們必須編寫一個能夠很好地打印樹的方法。這是我到目前爲止有：

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) 

這適用於簡單的樹：

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

打印出爲：

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

這是我預期的，但是，更復雜的樹如：

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

打印爲：

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

任何人都可以提供有關如何解決此問題的建議嗎？

Answer 1

你可以嘗試以下方法：

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

它的工作對我來說，我使用了不同的條件。主要變化： 1.我改變了「\ t」以spcaes。 2.我刪除了第一個縮進。

[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

首先，您是否必須使用當前使用的表達格式樣式？這種格式需要將許多節點打印到一行。如果您查看Data.Tree.Pretty使用的格式，它只會將任一行打印一個節點。如果你格式化你的代碼，這樣，myExpr就會有這樣的格式：

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

這使得許多問題，多簡單，因爲每個節點都會有一條線。所有你需要做的打印出一個節點就是知道樹內有多深。例如，節點3深度將具有從" | | +-"開始的行。然後從左到右打印每個節點，然後您會得到結果。如果您遇到困難，請嘗試在source for the Data.Tree.drawTree尋找靈感。

如果您必須堅持使用您當前的格式，請準備好進行大量工作。您必須根據每個節點中文本的寬度動態佈局樹。您還需要分散節點，以免重疊。開始之前，您需要考慮整棵樹。這是一個NP完全問題。有關更多詳細信息，請參閱this tree article。這無疑是超出了家庭作業的問題，但...