二叉树折叠函数

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 ((.) (+) . (+))

二叉树折叠函数

Binary Tree Fold Functions

binary-tree

haskell

fold