Haskell預訂遍歷樹到列表

Question

我無法讓我的代碼做一個樹的前序遍歷到工作列表。對於樹的定義如下：

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

和我的前序遍歷的定義如下：

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c] 
preorder f g (Leaf b) = [g b] 
preorder f g (Branch a left right) = [f a] ++ preorder f g left ++ preorder f g right 

但是我得到的錯誤是：

Couldn't match type `b' with `a' 
    `b' is a rigid type variable bound by 
     the type signature for 
     preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c] 
    `a' is a rigid type variable bound by 
     the type signature for 
     preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c] 
In the first argument of `f', namely `a' 
In the expression: f a 
In the first argument of `(++)', namely `[f a]' 

我知道我的問題是該函數的第一個參數的類型以及它需要如何使用[c]類型，但我無法弄清楚我的生活如何得到它。我已經嘗試過圍繞f a的括號的所有組合並且沒有括號，也沒有給我一個成功的跑步。

Answer 1

您已經將您的類型或函數調用混合起來 - 可能是類型，因爲您已命名變量。

你說Tree a b在其第一個參數b，但f參數preorder需要一個a。同樣的Leaf需要一個a，但你打電話g，它需要一個b。

這就是錯誤信息告訴你的：你傳遞給f的第一個參數的類型是b，當它預計爲a。

如果你改變你的數據類型爲：

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

然後你的代碼編譯罰款。

或者改變preorder到

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c] 
preorder f g (Leaf a) = [f a] 
preorder f g (Branch b left right) = [g b] ++ preorder f g left ++ preorder f g right