插入值的有序樹在Haskell

Question

基本上我已經定義，其定義一個樹數據類型如下：

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」型（剛性在'Leaf'的第一個參數中，即'l' 在第一個參數中，'l'在'Main' '節點'，即 '（葉子L）' 在表達式的參數：節點（葉升）米（插入XR）

我認爲這件事情做的類型，但我看不到，我已經把任何類型的不應該存在。

Answer 1

從大致翻譯類型檢查器-ESE成英文：

不能匹配預期類型 'A'（一個 剛性可變）

這意味着，它期待一個任意鍵入a，這也是在其他地方使用（因此「剛性」），所以它不能只是採取任何舊的類型。

針對推斷類型「樹一個」

這意味着，代替它發現預期的剛性多態型的一個Tree含有的元素。這顯然沒有意義，所以它抱怨。

'a'由Main處的'insert'類型簽名綁定。hs：11：10

這只是說該類型因爲您在該類型簽名中指定而受到限制。

在「葉」，即「L」的第一個參數在「節點」，即「（葉升）」在表達的第一 參數：節點（葉升）米（插入XR）

這只是告訴你哪些具體的術語，抱怨，在某些情況下。

所以，要理清：變量l是一個Tree a正在使用的上下文，只需要a。在這種情況下，l顯然具有正確的類型，所以錯誤在於它的使用方式。爲什麼類型檢查器正在尋找類型a？因爲你應用了Tree數據構造函數。但是等一下，l已經是Tree a！這些鱗片從我們的眼睛上掉下來，真相就被看到了。

......這就是解釋爲什麼Edward Kmett的快速繪製答案是正確的，以及用什麼樣的推理來達到這樣的答案。

Answer 2

您的問題是

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已經樹。

Answer 3

l是Node第一參數，所以它是Tree a類型（全左子樹）的。另一方面，Leaf只是將單個值作爲參數，而不是整個樹。因此，Leaf l會給出一個類型錯誤，因爲它會嘗試從整個樹中創建一個Leaf。也許你只是在這個地方想l而不是Leaf l，

而且，是什麼Leaf x和Node Empty x Empty之間的區別？你確定你需要兩個構造函數嗎？