Home Articles

显示树Haskell [重复]

Asked
Viewed 928 times
2

这个问题在这里已有答案:

请考虑以下数据类型

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

我正在尝试定义一个Show的实例(不导入任何模块或使用派生),它会像这样显示树

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

到目前为止,这是我想出来的

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'

不幸的是,这使得最深度最低的节点和最低深度节点的节点缩进 . 我知道findDepth函数实际上应该为leaf赋予最大值并且分支最低值,但是无法找到为两个参数递归写入函数的方法 . 有什么建议?

2 Answers

  • 4

    实际上,不需要额外的 findDepth 功能 - 每次显示孩子时,您都可以轻松遍历树并增加深度:

    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'
    

    测试用例:

    *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
    
  • 2

    这是一个没有完整解决方案的提示:写一个函数 showWithDepth :: Int -> Tree -> String 到目前为止向下传递"accrued depth" . 然后你可以写 show = showWithDepth 0 .

    请注意,通常您不应该像这样编写 show 实例,因为它的"semi-standard"显示实例应该基本上像派生实例一样工作并生成类似于有效Haskell代码的东西 . (此外,在存在 Read 实例的情况下,我们需要 read . show === id .

Related