Haskell Binary tree with key-value

Question

I want to build binary tree with key - value leafs with tuple (k,v).

My code:

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))

Now i'm trying to fill this tree:

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

But I get this error:

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

What's the cause and how can I fix it?

In situations like this, it can be helpful to remove the type signature, load the file in GHCi, and see what the compiler thinks the type should be. — C. A. McCann
– C. A. McCann, Commented Jul 20, 2011 at 17:52
emptyTree is a really bad name for that function, as everybody would expect that it returns an EmptyTree. A better name would something like singleton or singleNode. — Landei
– Landei, Commented Jul 22, 2011 at 14:14

hammar · Accepted Answer · 2011-07-20 17:53:33Z

6

Your type is either too general or too specific. It should be

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

or

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

Your original declaration was trying to insert (Int, Int) into a Tree k v for 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 for treeInsert indicates, only pairs of type (k, v) can be inserted into a Tree k v.

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

edited Jul 20, 2011 at 17:53

answered Jul 20, 2011 at 17:47

hammar

140k18 gold badges310 silver badges388 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

C. A. McCann Over a year ago

Alternatively, something like (Ord a) => a -> Tree a a -> Tree a a.

Collectives™ on Stack Overflow

Haskell Binary tree with key-value

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related