找到深度的樹haskell

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的I已經與測試：

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函數，該函數只需將Int傳遞給它即可：

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

但是你可以使用你喜歡的任何版本，三者幾乎相當。

總之我們現在有

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

我有這一個多的問題，我們已經多次我們的邏輯單個節點的深度，有沒有什麼辦法可以減少這個問題的地方我們Don't Repeat Ourselves？如果不是檢查基本情況，我們想出一種方法來使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將返回有效結果。現在我們有一個表達式，它可以精確地計算樹的深度，而無需處理任何特殊情況。