Haskell

Examples From the lecture

For Problems 3 and 4, use the following binary tree definition modified from lecture: It takes two type arguments, so nodes and leafs can contain different types of values. data Tree a b = Leaf b | Node a (Tree a b) (Tree a b) deriving (Read, Show, Eq) 3. (6 points) Write a isFull :: Tree a b -> Bool function that tests for a full tree (every node has two leafs or two trees; a tree that's just a leaf is also full). Note: 2 of the 6 points are for using just pattern matching to check for a leaf or a node (no defining isNode or isLeaf functions to figure out what the argument looks like). For Problem 8 and 9, look back to a datatype declared earlier: data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Read, Show, Eq) 8. Define a recursive function that returns the height of a binary tree. (A tree that's just a leaf has height zero [2/3].) 9. Repeat Problem 8 using a helper function height' tree n that returns n + height(tree). (Since you need two recursive calls, the routine won't be fully tail-recursive.) For Problems 8 and 9, we have data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Read, Show, Eq) I'll name the functions height1 and height2 just to make them different 8. height (Leaf _) = 0 - leafs have height 0 not 1 height1 (Node_left right) = 1 + max (height1 left) (heightl right) 9. height2 tree = height' tree o height' (Leaf ) h = h -- height' tree n = height of tree + n height' (Node left right) h = max (height' left (h+1)) (height' right (h+1)). (There isn't much difference between the two definitions, since we need two recursive calls and we're doing work after the calls.) For Problems 3 and 4, use the following binary tree definition modified from lecture: It takes two type arguments, so nodes and leafs can contain different types of values. data Tree a b = Leaf b | Node a (Tree a b) (Tree a b) deriving (Read, Show, Eq) 3. (6 points) Write a isFull :: Tree a b -> Bool function that tests for a full tree (every node has two leafs or two trees; a tree that's just a leaf is also full). Note: 2 of the 6 points are for using just pattern matching to check for a leaf or a node (no defining isNode or isLeaf functions to figure out what the argument looks like). For Problem 8 and 9, look back to a datatype declared earlier: data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Read, Show, Eq) 8. Define a recursive function that returns the height of a binary tree. (A tree that's just a leaf has height zero [2/3].) 9. Repeat Problem 8 using a helper function height' tree n that returns n + height(tree). (Since you need two recursive calls, the routine won't be fully tail-recursive.) For Problems 8 and 9, we have data Tree a = Leaf a | Node a (Tree a) (Tree a) deriving (Read, Show, Eq) I'll name the functions height1 and height2 just to make them different 8. height (Leaf _) = 0 - leafs have height 0 not 1 height1 (Node_left right) = 1 + max (height1 left) (heightl right) 9. height2 tree = height' tree o height' (Leaf ) h = h -- height' tree n = height of tree + n height' (Node left right) h = max (height' left (h+1)) (height' right (h+1)). (There isn't much difference between the two definitions, since we need two recursive calls and we're doing work after the calls.)