一千萬個為什麽

搜索

具有鍵值的Haskell二叉樹

我想用帶有元組(k,v)的鍵值葉子構建二叉樹。

我的代碼:

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

原因是什麽,我該如何解決?

最佳答案

您的類型太籠統或太具體。它應該是

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

要麽

fillTree :: (要麽d a) => a -> Tree a a -> Tree a a

Your 要麽iginal declaration was trying to insert (Int, Int) into a Tree k v f要麽 any k, v. It was saying that no matter what kind of tree you have, we can insert a pair of Ints in it. This is clearly nonsense, and as your signature f要麽 treeInsert indicates, only pairs of type (k, v) can be inserted into a Tree k v.

treeInsert :: (要麽d k) => (k, v) -> Tree k v -> Tree k v

轉載註明原文: 具有鍵值的Haskell二叉樹