在Haskell的一个有序树中插入一个值
基本上我定义了一个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)
但是，当我运行这个时，我得到以下错误信息：
无法匹配预期类型'a'（一个刚性变量）针对推断类型'Tree a''a'由Main.hs：11：10的'insert'类型签名绑定在'Leaf'的第一个参数中， ，即'l'在'Node'的第一个参数中，即'（Leaf l）'在表达式：Node（Leaf l）m（insert xr）
我认为这与类型有关，但我不知道我在哪里放置了哪些类型不应该在那里。
大致从类型检查器转换成英语：
无法匹配预期的类型'a'（一个刚性变量）
这意味着它需要一个任意类型a ，这也被用在其他地方（因此“刚性”），所以它不能只是采用任何旧类型。
反对推断的类型'树a'
这意味着它会找到一个包含预期刚性多态类型元素的Tree 。 这显然没有意义，所以它抱怨。
'a'在Main.hs：11：10处由'insert'的类型签名绑定
这只是说该类型因为在该类型签名中指定而受到限制。
在'Leaf'的第一个参数中，即'l'在'Node'的第一个参数中，即'（Leaf l）'在表达式：Node（Leaf l）m（insert xr）
这只是告诉你，在某些情况下，它抱怨哪个具体的术语。
因此，理清头绪：可变l是一Tree a在需要只是一个上下文中存在a 。 在这种情况下， l显然有正确的类型，所以错误在于它的使用方式。 为什么类型检查器正在寻找类型a ？ 因为你应用了一个Tree数据构造函数。 但是等等， l已经是一Tree a ！ 等瞧，鳞片从我们的眼睛上掉下来，看到真相。
......这只是解释为什么爱德华·凯梅特的快速回答是正确的一个冗长的方式，以及用什么样的推理来得出这样的答案。
你的问题是
insert x (Node l m r) | x > m = Node (Leaf l) m (insert x r)
| otherwise = Node (insert x l) m (Leaf r)
应该可能是
insert x (Node l m r) | x > m = Node l m (insert x r)
| otherwise = Node (insert x l) m r
因为l和r已经是树。
l是Node的第一个参数，因此它是Tree a类型（整个左子树）。 另一方面， Leaf仅仅将单个值作为参数，而不是整个树。 因此， Leaf l会给出一个类型错误，因为它试图从整棵树中创建一个Leaf。 也许你只是想l而不是Leaf l在这个地方。
另外， Leaf x和Node Empty x Empty之间有什么区别？ 你确定你需要两个构造函数吗？