On Thu, Dec 24, 2009 at 07:18:37PM -0600, Matt Young wrote:
Hi guys! Just so we are all on the same page, this problem is an exercise from the end of Chapter 3 in the book Real World Haskell (#8).
The problem calls for me to write a function to figure out the height of our user defined binary tree type. Here is the type: --chapter3 binary tree recursive type data Tree a = Node a (Tree a) (Tree a) | Empty deriving (Show) With this type, we'd create a tree with no leaves like: Node "tree" Empty Empty, and a tree with a single leaf like Node "tree2" = Empty (Node "leaf" Empty Empty)
It seems that you are perhaps a little confused about values of this type. First of all, I would say that the value Node "tree" Empty Empty is a tree with one node, which is a leaf. A leaf is any node with no children --- as you can see this node's children are both Empty. The only tree with no leaves is the Empty tree. Also, this: Empty (Node "leaf" Empty Empty) is a type error. Empty cannot be applied to (Node "leaf" Empty Empty), since it is a constructor that takes no arguments. I am not sure what tree you had in mind. Did the other replies help you figure out how to find the height of a tree or would you like more detailed explanation? -Brent