Beginning Haskell - getting "not in scope: data constructor" error

Question

I'm going through the problems in the Haskell O'Reilly book. The problem I am working on is

Using the binary tree type that we defined earlier in this chapter, write a function that will determine the height of the tree. The height is the largest number of hops from the root to an Empty. For example, the tree Empty has height zero; Node "x" Empty Empty has height one; Node "x" Empty (Node "y" Empty Empty) has height two; and so on.

I'm writing my code in a file called ch3.hs. Here's my code:

36 data Tree a = Node a (Tree a) (Tree a)
37             | Empty
38               deriving (Show)
39
40 --problem 9:Determine the height of a tree
41 height :: Tree -> Int
42 height (Tree node left right) = if (left == Empty && right == Empty) then 0 else max (height left) (height right) 

opening ghci in the terminal and typing :load ch3.hs. When I do that I get the following error:

Prelude> :load ch3.hs
[1 of 1] Compiling Main             ( ch3.hs, interpreted )

ch3.hs:42:7: Not in scope: data constructor `Tree'
Failed, modules loaded: none.

I expect that the Tree data constructor should be there, because I defined it in the lines above the height method. But when I try to load the file, I'm told that the data constructor is not in scope. I appreciate your help and explanation of why this error occurs. Thanks, Kevin

Answer 1

Change

 height (Tree node left right) 

to

height (Node node left right)

I.e. the pattern matching works on the constructors of the algebraic data type. Tree is not a constructor, it is the name of the ADT.

Btw, you have to comment out your function signature declaration to compile the code, because it contains an error.

You can then check the inferred type via

:t height

Answer 2

You pattern-match against constructors, i.e. the cases, of your Tree ADT. Tree is just what sums them all up.

It's much more straightforward like this, and, most of all, correct:

height Empty = 0
height (Node _ l r) = 1 + max (height l) (height r)

Answer 3

Your code is wrong, on several levels. It looks like you misunderstood algebraic data types.

• The type signature is wrong, a Tree is always a Tree of a specific type - which you called a in its declaration, and which may be any type (since you didn't constraint it). So heigth has to take a Tree of some type - a Tree SomeType, too. You can and should use the most generic type for SomeType, i.e. a type variable like a.
• When pattern matching, you name a specific constructor - Node a (Tree a) (Tree a) or Empty - to match against, not against the type as a whole. So height (Node ...) would match a Node, height (Empty) would match a Empty, and height (Tree ...) would try to match a constructor named Tree, but there is none. That's the error message you recieve.
• You never ever compare (via ==) with a Constructor. It would actually work if you wrote deriving (Show, Eq). But you should use pattern matching to determine if you reached an Empty
• Which leads to: You're only matching Node, not Empty - you should add a clause for Empty.
• Also, your function still returns 0 for all inputs if you fix all the above issues. You never return anything but 0 or the max of the childrens' height - which can, in turn, only return 0 or the max of their childrens' height, etc ad infinitum. You have to increment the result at each level ;)