Inserting a value into an ordered tree in Haskell

Question

Hi

Basically I have defined a Tree data type which is defined as follows:

data Tree a = Empty
| Leaf a
| Node (Tree a) a (Tree a)
deriving (Eq, Ord, Show)

Now I have to create a function to insert a value into an ordered tree (it doesn't have to sort the tree, just add the value). This is what I've come up with so far:

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)

However, when I run this I get the following error message:

Couldn't match expected type 'a' (a rigid variable) against inferred type 'Tree a' 'a' is bound by the type signature for 'insert' at Main.hs:11:10 In the first argument of 'Leaf', namely 'l' In the first argument of 'Node', namely '(Leaf l)' In the expression: Node (Leaf l) m (insert x r)

I assume it's something to do with types but I can't see where I've put any types that shouldn't be there.

Answer 1

Your problem is that

insert x (Node l m r)   | x > m     = Node (Leaf l) m (insert x r)
                        | otherwise = Node (insert x l) m (Leaf r)

should probably be

insert x (Node l m r)   | x > m     = Node l m (insert x r)
                        | otherwise = Node (insert x l) m r

because l and r are already Trees.

Answer 2

l is the first parameter of Node and so it is of type Tree a (the whole left subtree). Leaf on the other hand just takes a single value as a parameter, not a whole tree. Therefore Leaf l gives a type error, since it tries to make a Leaf out of a whole tree. Probably you simply wanted l instead of Leaf l in this place.

Also, what is the difference between Leaf x and Node Empty x Empty? Are you sure you need both constructors?

Answer 3

Translating roughly from type-checker-ese into English:

Couldn't match expected type 'a' (a rigid variable)

This means that it was expecting an arbitrary type a, that's also used elsewhere (hence "rigid") so it can't just take any old type.

against inferred type 'Tree a'

This means that instead it found a Tree containing elements of the expected rigid polymorphic type. This obviously doesn't make sense, so it complains.

'a' is bound by the type signature for 'insert' at Main.hs:11:10

This just says that the type is being restricted because you specified it in that type signature.

In the first argument of 'Leaf', namely 'l' In the first argument of 'Node', namely '(Leaf l)' In the expression: Node (Leaf l) m (insert x r)

This is just telling you which specific term it's complaining about, with some context.

So, to sort things out: The variable l is a Tree a being used in a context that needs just a. In this case l obviously has the correct type, so the mistake is in how it's used. Why was the type checker looking for type a? Because you applied a Tree data constructor to it. But wait, l is already a Tree a! et voila, the scales fall from our eyes and the truth is beheld.

...which was all just a lengthy way of explaining why Edward Kmett's quick-draw answer is correct, and what kind of reasoning one might use to arrive at such an answer.