Haskell n元樹遍歷

Question

我對Haskell來說很新，而且我正試着研究如何遍歷n元樹。作爲輸出我希望得到葉值的列表（如樹枝沒有任何價值），所以testtree這將是：4,5

我的定義到目前爲止是：

data Tree a = Leaf a | Branch [Tree a] deriving (Show) 

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

testtree = Branch [(Leaf "4"), (Leaf "5")] 

但它給出了錯誤：

Couldn't match expected type `Tree a' 
    against inferred type `[Tree a]' 
In the first argument of `travTree', namely `xs' 
In the second argument of `(:)', namely `travTree xs' 
In the expression: travTree x : travTree xs 

我假設這是由於xs是一個樹列表和期望單數樹。有沒有辦法做到這一點？我一直試圖在地圖功能，沿着線：

travTree (Branch (x:xs)) = travTree x : map travTree xs 

但隨後抱怨的：

Occurs check: cannot construct the infinite type: a = [a] 
When generalising the type(s) for `travTree' 

我也試圖改變函數簽名：

travTree     :: Tree a -> [b] 

這給出了錯誤：

Couldn't match expected type `a' against inferred type `[b]' 
    `a' is a rigid type variable bound by 
     the type signature for `travTree' at Main.hs:149:36 
In the first argument of `(:)', namely `travTree x' 
In the expression: travTree x : map travTree xs 
In the definition of `travTree': 
    travTree (Branch (x : xs)) = travTree x : map travTree xs 

任何幫助將不勝感激，所以在此先感謝..！

Answer 1

遍歷樹意味着遍歷所有子樹並將生成的列表展平成一個。

這相當於

travTree (Branch branches) = concat $ map travTree branches 

注意，甚至有像branches >>= travTree或concatMap travTree branches此定義的右側更簡潔的符號，但我認爲上面的一個是最清晰的。

編輯：再次引入列表修真版本完整起見：

travTree (Branch branches) = [ elem | br <- branches, elem <- travTree br ] 

Answer 2

你右邊線與map，但遍歷每個子樹後要產生的名單concat在一起。當使用map時，也沒有關係使用(x:xs)模式中斷列表的第一個元素。我寫這篇文章的：

travTree (Branch xs) = concatMap travTree xs 

（但請注意，我沒有測試過但是我經常發現我的「無限類型= [A]」問題是由map其中需要concatMap造成的！ ）

Answer 3

當我剛接觸Haskell時，遇到了同樣的問題。我終於想出瞭如何通過放慢速度和觀察類型來解決問題。 （回來時，我寫了很多計劃，我反而慢了下來，並期待在非常簡單的輸入/輸出對。我這樣做，有時在Haskell，但直到我看了類型。）

travTree     :: Tree a -> [a] 
travTree (Leaf x)   = [x] 
travTree (Branch (x:xs)) = travTree x : travTree xs 

你的類型看起來不錯：Tree a -> [a]聽起來像「所有的葉子」給我。

travTree (Leaf x) = [x] 

此情況下正確轉換一個Tree a爲[a]。

travTree (Branch (x:xs)) = travTree x : travTree xs 

好的，輸入肯定是Tree a。如果輸出爲[a]，並且第一個運算符爲(:) :: a -> [a] -> [a]，那麼我們需要travTree x :: a和travTree xs :: [a]。這是否工作？

嗯，它失敗的原因有兩個：實際上，travTree x :: [a]，你不能列表到另一個列表（你需要(++) :: [a] -> [a] -> [a]）。你不能通過[Tree a]到travTree :: Tree a -> [a] - 當你期望一棵樹時，你會給它一個樹列表。

您可以通過使用map：map travTree xs來解決第二個問題。這有類型[Tree a] -> [[a]]。幸運的是，現在這個適合travTree x :，使

(travTree x : map travTree xs) :: [[a]] 

現在你只是有問題，你有[[a]]而不是[a]。 concat通過展開一次解決了這個問題，所以

travTree (Branch (x:xs)) = concat (travTree x : map travTree xs) :: [a] 

相匹配的預期Tree a -> [a]。

其他答案是正確的說這裏的解構是毫無意義的，但我希望看到類型的拼寫有助於你理解如何模仿頭腦中的類型推斷。這樣你就可以計算出其他類似問題出了什麼問題。