2

我对 Haskell 相当陌生，并且正在尝试完成我班上的作业。我正在尝试创建一个预排序函数来遍历以下格式的树对象

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g Empty = []
preorder f g (Leaf x) = [x]

我的树类如下

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

在定义预购函数时，我得到如下所示的错误。

Couldn't match expected type 'c' with actual type 'b'
'c' is a rigid type variable bound by the type signature for preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c].
'b' is a rigid type variable bound by the type signature for preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c].

它们发生在最后一个预购函数定义中

preorder f g (Leaf x) = [x]
4

1 回答 1

4

除了空叶子之外，该类型Tree a b还包含带有 type 元素的叶子和带有 type 元素的b分支。a您希望按顺序访问树的每个节点，收集应用函数的结果f :: a -> c并g :: b -> c在类型列表中[c]。编译器抱怨你的preorder函数的原因是它x有 type b; 这股势力c要统一起来b。但这是一种比您向编译器指示的更不通用的类型。作为练习，看看您是否可以为您的函数编写编译器接受的更具体的类型。提示：是b和c不同的类型？

但是，您被赋予了一个功能g :: b -> c。应用这个函数x产生一个类型的值c，这个值可以被收集到一个类型的列表中[c]。此列表可能包含也可能不包含类型a或的元素b。您可以通过以下方式根据给定的签名重写前序遍历：

preorder :: (a -> c) -> (b -> c) -> Tree a b -> [c]
preorder f g Empty          = []
preorder f g (Leaf b)       = [g b]
preorder f g (Branch a l r) = f a : preorder f g l ++ preorder f g r
于 2014-03-04T05:13:05.150 回答