爲什麼我會遇到這些類型錯誤？

Question

我有一個數據類型：

data Tree = Empty | Node Int Tree Tree 

，我想功能

nodeDepth :: Tree -> [(Int, Int)] 

一對用於每個節點。第一個元素是標籤（值），第二個元素是深度。

我的意圖（原始代碼）是這樣的：

nodeDepth (Node label left right) = zip nodeDepth' (Node label left right) [0] 
nodeDepth' Empty _ = [] 
nodeDepth' (Node label left right) [level] = label : nodeDepth' (Node label left right) level : (1 + level) 

但是，這是行不通的。

有什麼不對？我使用的弗雷格REPL

Error message are like : 

E <console>.fr:22: t19906 occurs in type [t19906] rendering expression level{19727} untypable. 

E <console>.fr:22: type error in expression level 
    type is t19906 
    used as [t19906] 

E <console>.fr:22: type error in expression 
    nodeDepth' (Node label left right) level:+ 1 level 
    type is [[t19909]] 
    used as [Int] 


E <console>.fr:22: [[Int]] is not an instance of Num 


E <console>.fr:20: type error in expression nodeDepth' 
    type is apparently [t19961] 
    used as function 


H <console>.fr:20: too many or too few arguments perhaps? 


E <console>.fr:20: type error in expression Node label left right 
    type is Tree 
    used as [t19964] 


E <console>.fr:20: type error in expression 
    zip nodeDepth' (Node label left right) 
    type is apparently [(t19961,t19964)] 
    used as function 


H <console>.fr:20: too many or too few arguments perhaps? 


W <console>.fr:20: application of nodeDepth will diverge. 

Answer 1

至於錯誤考慮以下行例如：

nodeDepth (Node label left right) = zip nodeDepth' (Node label left right) [0] 

因爲Haskell的功能應用關聯到左邊，拉鍊取功能nodeDepth」作爲它的第一個參數。要解決此特定錯誤您可能希望這樣寫：

zip (nodeDepth' (Node label left right)) [0] 

但你仍然下落不明nodeDepth的」第二個參數，所以在括號中的表達式只返回一個函數，而不是一個列表。

另一個錯誤是，當您爲非空樹定義nodeDepth'時：您的模式匹配[level]將level作爲單個元素進行捕獲，並將它傳遞到同一行上的自身。這隻能通過假設層次本身是一個列表來解決，但這也沒有太大意義，因爲在行的末尾添加假定層次爲數字類型。

nodeDepth' (Node label left right) [level] = label : nodeDepth' (Node label left right) level : (1 + level) 

通過使用深度優先搜索樹下面的函數nodeDepth迭代，並構建了標籤和各個節點的深度的列表。

data Tree = Empty | Node Int Tree Tree 

wikiTree = Node 2 (Node 7 (Node 2 Empty Empty) (Node 6 (Node 5 Empty Empty) (Node 11 Empty Empty))) (Node 5 Empty (Node 9 (Node 4 Empty Empty) Empty)) 

nodeDepth :: Tree -> [(Int, Int)] 
nodeDepth Empty = [] 
nodeDepth (Node label left right) = nodeDepthAccumulator (Node label left right) 0 

nodeDepthAccumulator :: Tree -> Int -> [(Int, Int)] 
nodeDepthAccumulator Empty _ = [] 
nodeDepthAccumulator (Node label left right) depth = (label,depth) : nodeDepthAccumulator left (depth+1) ++ nodeDepthAccumulator right (depth+1) 

上wikiTree你得到的例子執行nodeDepth：

> nodeDepth wikiTree 
> [(2, 0),(7, 1),(2, 2),(6, 2),(5, 3),(11, 3),(5, 1),(9, 2),(4, 3)] 

你可能已經預期。

Answer 2

此：

zip nodeDepth' (Node label left right) [0] 

的zip功能expets兩個列表，但既不nodeDepth'也不(Node ...)是列表。然後你將結果（這是一個列表）應用到其他列表[0]，這解釋了第二個最後的消息。我猜你的意思是寫

zip (nodeDepth' (Node label left right)) [0] 

但即使在這種情況下，有一種說法失蹤nodeDepth」使括號中的列表中的表達式。

爲nodeDepth'第二個定義也不會去編譯，有以下原因：

• 與模式[level]你匹配一個元素的列表，並調用單個元素level。精細。但是您使用level作爲nodeDepth'（這是一個列表）的第二個參數，並且在表達式1+level中使用它作爲數字。

• 在像

  一個表達式：B：C

c必須是一個列表（它不是在你的例子）和b不能是列表，並且必須具有與a相同。但是nodeDepth'應該返回一個列表。因此，整個RHS毫無意義，因此你會得到很多錯誤。

一個技巧在這裏：因爲你顯然不希望的水平是一個列表，無處真傳列表來nodeDepth」，難道不更好只需更換模式[level]與level？