二叉樹折功能

Question

我有一個二叉樹的定義在Haskell如下所示：

data BTree x = Nil | BNode x (BTree x) (BTree x) 

我再爲這個數據類型摺疊的定義：

foldB :: (x -> u -> u -> u) -> u -> BTree x -> u 
foldB f a Nil = a 
foldB f a (BNode x l r) = f x (foldB f a l)(foldB f a r) 

所以我希望，我可以簡單地使這個函數總和所有的值：

sumBFold :: (Num a) => BTree a -> a 
sumBFold x = foldB (+) 0 x 

但這不起作用，我不能爲我的生活找出原因。 我收到錯誤消息的有用的部分是：

Couldn't match type `a` with `a -> a' 
`a' is a rigid type variable bound by the type signature for: 
sumBFold :: forall a. Num a => BTree a -> a 
Expected type: (a -> a) -> a -> a -> a 
Actual type: (a -> a) -> (a -> a) -> a -> a 
In the first argument of folB namely `(+)` 

Answer 1

錯誤試圖使用

(+) :: (Num a) => a -> a -> a 

作爲參數類型

(x -> u -> u -> u) 

如果你來約開始嘗試去適應它，記住(x -> u -> u -> u)與(x -> (u -> (u -> u)))相同，

x == a 
u == a 
u -> u == a -> a == a 

這是不可能的，以及錯誤來自何處。

請考慮以下任一情況。

sumBFold :: (Num a) => BTree a -> a 
sumBFold = foldB add3 where add3 x y z = x + y + z 
sumBFold = foldB $ \x y z -> x + y + z 
sumBFold = foldB ((.) (+) . (+))