Haskell帶鍵值的二叉樹

我想用帶元組（k，v）的鍵值葉子構建二叉樹。Haskell帶鍵值的二叉樹

我的代碼：

data Tree k v = EmptyTree 
       | Node (k, v) (Tree k v) (Tree k v) 
       deriving (Show, Eq, Ord, Read) 

emptyTree :: (k,v) -> Tree k v 
emptyTree (k,v) = Node (k, v) EmptyTree EmptyTree 

treeInsert :: (Ord k) => (k,v) -> Tree k v -> Tree k v 
treeInsert (k,v) EmptyTree = emptyTree (k, v) 
treeInsert (a, b) (Node (k,v) left right) 
     | a == k = (Node (a,b) left right) 
     | a < k = (Node (a, b) (treeInsert (a, b) left) right) 
     | a > k = (Node (a, b) left (treeInsert (a, b) right))

現在我試圖填補這棵樹：

fillTree :: Int -> Tree k v -> Tree k v 
fillTree x tree = treeInsert (x, x) tree

但我得到這個錯誤：

Couldn't match type `v' with `Int' 
     `v' is a rigid type variable bound by 
      the type signature for fillTree :: Int -> Tree k v -> Tree k v

有什麼原因和如何我修復它？

來源

2011-07-20 0xAX

在這種情況下，刪除類型簽名，在GHCi中加載文件以及查看編譯器*認爲的類型應該是什麼會有幫助。 –

'emptyTree'是該函數的一個非常糟糕的名稱，因爲每個人都希望它返回一個'EmptyTree'。一個更好的名字就像'singleton'或'singleNode'。 – Landei

您的類型要麼太籠統，要麼太具體。它應該是

fillTree :: Int -> Tree Int Int -> Tree Int Int

或

fillTree :: (Ord a) => a -> Tree a a -> Tree a a

你原來的宣言試圖插入(Int, Int)成Tree k v任何k，v。這是說，無論你有什麼樣的樹，我們都可以在其中插入一對Int。這顯然是無稽之談，並且由於treeInsert的簽名表明，只有類型(k, v)可以插入到Tree k v中。

treeInsert :: (Ord k) => (k, v) -> Tree k v -> Tree k v

來源

2011-07-20 17:47:21 hammar

或者，像'（Ord a）=> a - > Tree a a - > Tree a a'這樣的東西。 –

是的，謝謝。 – 0xAX

Haskell帶鍵值的二叉樹

回答

相關問題