基本上我已经定义了一个 Tree 数据类型,定义如下:
data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)
现在我必须创建一个函数来将值插入到有序树中(它不必对树进行排序,只需添加值)。到目前为止,这是我想出的:
insert :: a -> Tree a -> Tree a
insert x Empty = Leaf x
insert x (Leaf m) | m < x = Node (Leaf x) m Empty
| otherwise = Node Empty m (Leaf x)
insert x (Node l m r) | x > m = Node (Leaf l) m (insert x r)
| otherwise = Node (insert x l) m (Leaf r)
但是,当我运行它时,我收到以下错误消息:
Couldn't match expected type 'a' (a rigid variable) against inferred type 'Tree a' 'a' is bound by the type signature for 'insert' at Main.hs:11:10 In the first argument of 'Leaf', namely 'l' In the first argument of 'Node', namely '(Leaf l)' In the expression: Node (Leaf l) m (insert x r)
我认为这与类型有关,但我看不到我在哪里放置了任何不应该存在的类型。
最佳答案
大致从 type-checker-ese 翻译成英文:
Couldn't match expected type 'a' (a rigid variable)
这意味着它期待任意类型
a
,这也用于其他地方(因此是“刚性”),因此它不能只采用任何旧类型。against inferred type 'Tree a'
这意味着它找到了
Tree
包含预期的刚性多态类型的元素。这显然没有意义,所以它提示。'a' is bound by the type signature for 'insert' at Main.hs:11:10
这只是说该类型受到限制,因为您在该类型签名中指定了它。
In the first argument of 'Leaf', namely 'l' In the first argument of 'Node', namely '(Leaf l)' In the expression: Node (Leaf l) m (insert x r)
这只是在某些上下文中告诉您它在提示哪个特定术语。
所以,整理一下:变量
l
是 Tree a
在只需要 a
的上下文中使用.在这种情况下 l
显然有正确的类型,所以错误在于它的使用方式。为什么类型检查器要查找类型 a
?因为你申请了 Tree
数据构造函数。但是等等,l
已经是 Tree a
!瞧,鳞片从我们的眼睛里掉下来,真相被看到了。...这只是解释原因的冗长方式爱德华·克米特 的快速得出的答案是正确的,人们可能会使用什么样的推理来得出这样的答案。
关于sorting - 在 Haskell 中将值插入到有序树中,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2222325/