寻找树的深度哈斯克尔

Question

我想找到STree的深度，但在我的代码中它不会计算第一级。

data STree = SNode Label [STree] deriving (Eq,Show)
tdepth :: STree -> Label
tdepth (SNode _ [])= 0
tdepth (SNode l s) = 1 + naiveSumList([tdepth t | t <- s])
naiveSumList :: [Int] -> Label
naiveSumList (x:xs) = x + (naiveSumList xs)
naiveSumList [] = 0

tdepth SNode _ []必须给出 1，但我如何计算水平？以下是我一直在测试的STree：

s1 = SNode 1 []
s2 = SNode 1 [
        SNode 2 [],
        SNode 3 []
        ]
s3 = SNode 1 [
        SNode 2 [
            SNode 4 [],
            SNode 5 [],
            SNode 6 []
            ],
        SNode 3 []
        ]
s4 = SNode 1 [
        SNode 2 [
            SNode 4 [],
            SNode 5 [
                SNode 7 []
                ],
            SNode 6 []
            ],
        SNode 3 []
        ]

我的结果与代码示例：

tdepth s1  = 0
tdepth s2  = 1
tdepth s3  = 2
tdepth s4  = 3

结果应该是：

 tdepth s1  = 1
 tdepth s2  = 2
 tdepth s3  = 3
 tdepth s4  = 4

Answer 1

让我们从基本情况开始。 您希望tdepth (SNode label [])返回1，所以让我们编写这种情况：

tdepth :: STree -> Int
tdepth (SNode _ []) = 1

现在我们需要知道如何计算树的深度。 树的深度是最长分支上的节点数，而您对函数的期望示例正是我们正在寻找的。 由于我们正在寻找最长的分支，我们应该找到每个分支的最大深度。 幸运的是，Prelude已经内置了一个maximum :: Ord a => [a] -> a函数，所以我们可以

tdepth (SNode _ branches) = 1 + maximum [tdepth branch | branch <- branches]

或等效（以及我更喜欢的版本）

tdepth (SNode _ branches) = 1 + maximum (map tdepth branches)

但是，我不喜欢map tdepth branches周围的括号，并且由于我们正在使用Int因此我们可以使用 succ 函数，该函数只需将 1 添加到传递给它的任何Int中：

tdepth (SNode _ branches) = succ $ maximum $ map tdepth branches

但是你可以使用任何你喜欢的版本，这三个版本几乎是等效的。

我们现在一起拥有

tdepth :: STree -> Int
tdepth (SNode _ []) = 1
tdepth (SNode _ branches) = 1 + maximum (map tdepth branches)

我确实还有一个问题，我们已经重复了单个节点深度的逻辑，有没有办法将这个问题减少到我们不重复自己的程度？ 如果我们不是检查基本情况，而是想出一种方法来使maximum返回0如果branches == []，那么我们的函数就不需要两个语句。 不幸的是，如果传递一个空列表，maximum当前会出现错误，但我们可以非常简单地解决这个问题。 我们所要做的就是确保传递给maximum的列表始终至少包含一个元素：

tdepth :: STree -> Int
tdepth (SNode _ branches) = 1 + maximum (0 : map tdepth branches)
-- Or if you prefer
--                        = succ $ maximum $ 0 : map tdepth branches

我们可以安全地将0附加到我们的深度上，因为我们知道我们的深度将始终大于 0，因此在该列表中调用maximum将返回有效结果。 现在我们有一个表达式，可以准确地计算树的深度，而无需处理任何特殊情况。