sorting - 在 Haskell 中将值插入到有序树中

Question

基本上我已经定义了一个 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)

我认为这与类型有关，但我看不到我在哪里放置了任何不应该存在的类型。

Answer 1

大致从 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 !瞧，鳞片从我们的眼睛里掉下来，真相被看到了。

...这只是解释原因的冗长方式 爱德华·克米特 的快速得出的答案是正确的，人们可能会使用什么样的推理来得出这样的答案。