algorithm - 具有键值的Haskell二叉树

Question

我想用元组 (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

是什么原因造成的，我该如何解决？

Answer 1

您的类型过于笼统或过于具体。应该是

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