Haskell: Tail recursion and Datatypes
PLEASE TRY TO ANSWER IT THIS TIME AS BEST POSSIBLE.
Assigned someone who knows how to do HASKELL!!!!!!!
Example for BINARY TREE DEFINITION from lecture
Recursive Structures
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) (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. heighti (Leaf _) = 0 -- leafs have height 0 not i heightl (Node left right) = 1 + max (height 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.) H. Recursive Structures If the body of a data declaration uses the type being defined, we get a recursive datatype. :{ | data List a = Node a (List a) | Nil deriving (Show, Read, Eq) | null Nil = True | null (Node _ _) = False | len Nil = 0 | len (Node_ x) = 1 + len x | lenl x = lenl' 0 x | lenl' res Nil = res | lenl' res (Node - t) = lenl' (res+1) t :} > x = Node 1 (Node 2 (Node 3 (Node 4 (Node 5 Nil)))) > len x > lenl x For another example of a recursive datatype, here's a simple binary tree type, where the nodes and leafs are labeled by values. > data Tree a = Leaf a Node a (Tree a) (Tree a) deriving (Read, Show, Eq) > t1 = Leaf "abc". > t2 = Node "ab" ti (Leaf "de") -- using ti, a leaf >:t ti ti :: Tree (Char] > it t2 t2 :: Tree (Char] Here's a function that checks to see if a given value is every value in the tree. (Note we can only run this function on trees where the values are of a type that supports Ord.) :{ | ge_tree :: Ord t => t -> Tree t -> Bool | ge_tree val (Leaf val') = val >= val' | ge_tree val (Node val' ti t2) = val >= val' && ge tree val tl && ge tree val t2 > t2 Node "ab" (Leaf "abc") (Leaf "de") 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) (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. heighti (Leaf _) = 0 -- leafs have height 0 not i heightl (Node left right) = 1 + max (height 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.) H. Recursive Structures If the body of a data declaration uses the type being defined, we get a recursive datatype. :{ | data List a = Node a (List a) | Nil deriving (Show, Read, Eq) | null Nil = True | null (Node _ _) = False | len Nil = 0 | len (Node_ x) = 1 + len x | lenl x = lenl' 0 x | lenl' res Nil = res | lenl' res (Node - t) = lenl' (res+1) t :} > x = Node 1 (Node 2 (Node 3 (Node 4 (Node 5 Nil)))) > len x > lenl x For another example of a recursive datatype, here's a simple binary tree type, where the nodes and leafs are labeled by values. > data Tree a = Leaf a Node a (Tree a) (Tree a) deriving (Read, Show, Eq) > t1 = Leaf "abc". > t2 = Node "ab" ti (Leaf "de") -- using ti, a leaf >:t ti ti :: Tree (Char] > it t2 t2 :: Tree (Char] Here's a function that checks to see if a given value is every value in the tree. (Note we can only run this function on trees where the values are of a type that supports Ord.) :{ | ge_tree :: Ord t => t -> Tree t -> Bool | ge_tree val (Leaf val') = val >= val' | ge_tree val (Node val' ti t2) = val >= val' && ge tree val tl && ge tree val t2 > t2 Node "ab" (Leaf "abc") (Leaf "de")
