WHAT KIND OF MORE INFORMATION DO YOU WANT? THIS IS ALL THE INFORMATION I HAVE.

module Main where

import Test.HUnit import System.Exit

-- *** Read Chapters 8 and 16 ***

data Tree2 a b = Leaf2 a | Branch b (Tree2 a b) (Tree2 a b)

--------------- Tree2 objects tree2a :: Tree2 Int String -- to be used to test Problems 2 and 3 tree2a = Branch "A" (Branch "B" (Leaf2 1) (Leaf2 2)) (Leaf2 3)

tree2b :: Tree2 Int String -- to be used to test Problems 2 and 3 tree2b = Branch "+" (Branch "*" (Leaf2 3) (Branch "+" (Leaf2 4) (Leaf2 5))) (Branch "+" (Branch "*" (Leaf2 6) (Leaf2 7)) (Leaf2 8)) ---------------

-- Problem 2 (15 points) instance (Show a, Show b) => Show (Tree2 a b) where show t = undefined

-- Problem 3 (15 points) preorder :: (a -> c) -> (b -> c) -> Tree2 a b -> [c] -- 8 points preorder = undefined

inorder :: (a -> c) -> (b -> c) -> Tree2 a b -> [c] -- 7 points inorder = undefined

-- Problem 4 (10 + 15 = 25 points) -- Chapter 16, Exercise 6 (Modified)

data Tree = Leaf Int | Node Tree Tree

--------------- Tree objects tree1 :: Tree -- to be used to test Problem 4.1 tree1 = Node (Node (Node (Leaf 1) (Leaf 2)) (Leaf 3) ) (Node (Leaf 4) (Node (Leaf 5) (Leaf 6)) )

tree2 :: Tree -- to be used to test Problem 4.1 tree2 = Node (Leaf 7) (Node (Node (Leaf 8) (Leaf 9)) (Node (Leaf 10) (Leaf 11)) ) ---------------

-- Problem 4.1 (5 + 5 = 10 points) leaves :: Tree -> Int leaves = undefined

nodes :: Tree -> Int nodes = undefined

-- Problem 4.2 (Base case 5 points + inductive case 10 points = 15 points) {-- (Write your induction proof within this block comment.) Base case:

Inductive case: (Make sure that you state the induction hypothesis!)

--}

-- Problem 5 (40 points) Chapter 8, Exercise 9 data Expr = Val Int | Add Expr Expr | Mul Expr Expr

type Cont = [Op]

data Op = EVALA Expr | ADD Int | EVALM Expr | MUL Int

eval :: Expr -> Cont -> Int -- Give three definitions for eval. -- First two definitions, -- 1) for (Val n) and c as arguments and -- 2) for (Add x y) and c as arguments -- are already given in the text Section 8.7, but -- you need to modify the second definition slightly -- and give the third definition for (Mul x y) eval = undefined

exec :: Cont -> Int -> Int -- Give five definitions for exec, one for an empty list and -- one for each of the four constructors of the data type Op -- Some of these are already given in the text Section 8.7. exec = undefined

value :: Expr -> Int value e = eval e []

-- Following expressions are to test your eval and exec definitions -- (2 + 3) + 4 = 9 e1 = (Val 3) -- 3 e2 = (Add (Val 4) (Val 3)) -- 4 + 3 = 7 e3 = (Mul (Val 4) (Val 3)) -- 4 * 3 = 12 e4 = (Add (Add (Val 2) (Val 3)) (Val 4)) -- (2 + 3) + 4 = 9 e5 = (Mul (Mul (Val 2) (Val 3)) (Val 4)) -- (2 * 3) * 4 = 24 e6 = (Mul (Add (Val 2) (Val 3)) (Val 4)) -- (2 + 3) * 4 = 20 e7 = (Add (Mul (Val 2) (Val 3)) (Val 4)) -- (2 * 3) + 4 = 10 e8 = (Add (Mul (Val 2) (Val 3)) (Add (Val 4) (Val 5))) -- (2 * 3) + (4 + 5) = 15 e9 = (Mul (Add (Val 2) (Val 3)) (Add (Val 4) (Val 5))) -- (2 + 3) * (4 + 5) = 45 e10 = (Add (Mul (Add (Val 2) (Val 3)) (Mul (Val 4) (Val 5))) (Mul (Val 3) (Add (Val 4) (Val 7)))) -- ((2 + 3) * (4 * 5)) + (3 * (4 + 7)) = 133

myTestList = TestList [ "preorder 1" ~: (concat (preorder show id tree2a)) ~=? "AB123" , "inorder 1" ~: (concat (inorder show id tree2a)) ~=? "1B2A3" , "preorder 2" ~: (concat (preorder show id tree2b)) ~=? "+*3+45+*678" , "inorder 2" ~: (concat (inorder show id tree2b)) ~=? "3*4+5+6*7+8" , "leaves 1" ~: leaves tree1 ~=? 6 , "leaves 2" ~: leaves tree2 ~=? 5 , "nodes 1" ~: nodes tree1 ~=? 5 , "nodes 1" ~: nodes tree2 ~=? 4

, "value 1" ~: value e1 ~=? 3 , "value 2" ~: value e2 ~=? 7 , "value 3" ~: value e3 ~=? 12 , "value 4" ~: value e4 ~=? 9 , "value 5" ~: value e5 ~=? 24 , "value 6" ~: value e6 ~=? 20 , "value 7" ~: value e7 ~=? 10 , "value 8" ~: value e8 ~=? 15 , "value 9" ~: value e9 ~=? 45 , "value 10" ~: value e10 ~=? 133 ]

main = do c 0 = ExitFailure 2 | errs > 0 = ExitFailure 1 | otherwise = ExitSuccess

Use the following data type for Problems 2 and 3. data Tree2 a b = Leaf2 a Branch b (Tree2 a b) (Tree2 a b) Problem 2. (15 points) Make Tree2 an instance of Show. Do not use deriving; define the instance yourself. Make the output look somewhat nice (e.g., indent nested branches). Problem 3. (8 + 7 = 15 points) Implement the two functions that traverse the tree in the given order collecting the values from the tree nodes into a list: preorder :: (a -> c) -> (b-> c) -> Tree2 a b -> [c] inorder :: (a -> c) -> (b-> c) -> Tree2 a b -> [c] Notice that the data type Tree2 can store different types of values in the leaves than on the branching nodes. Thus, each of these functions takes two functions as arguments: The first function maps the values stored in the leaves to some common type c, and the second function maps the values stored in the branching nodes to type c, thus, resulting in a list of type [c] Problem 4. (10 + 15 = 25 points) [Make sure you read Chapter 16 before attempting this problem.] Chapter 16. Exercise 6, page 247. This problem has two parts. Given the following data type data Tree = Leaf Int | Node Tree Tree 1. (5+5 = 10) Given a tree, function leaves counts the number of leaves in the tree, and function nodes the number of internal nodes in the tree. Define leaves and nodes. The function types are as follows. leaves :: Tree -> Int nodes :: Tree -> Int 2. (Base case 5 points + inductive case 10 points = 15 points) Prove the following property by induction on trees. leaves t = nodes t + 1 Problem 5. (40 points) Chapter 8, Exercise 9. Study Section 8.7 carefully before attempt- ing this problem. The skeleton code contains more explanation on what you are supposed to do. Use the following data type for Problems 2 and 3. data Tree2 a b = Leaf2 a Branch b (Tree2 a b) (Tree2 a b) Problem 2. (15 points) Make Tree2 an instance of Show. Do not use deriving; define the instance yourself. Make the output look somewhat nice (e.g., indent nested branches). Problem 3. (8 + 7 = 15 points) Implement the two functions that traverse the tree in the given order collecting the values from the tree nodes into a list: preorder :: (a -> c) -> (b-> c) -> Tree2 a b -> [c] inorder :: (a -> c) -> (b-> c) -> Tree2 a b -> [c] Notice that the data type Tree2 can store different types of values in the leaves than on the branching nodes. Thus, each of these functions takes two functions as arguments: The first function maps the values stored in the leaves to some common type c, and the second function maps the values stored in the branching nodes to type c, thus, resulting in a list of type [c] Problem 4. (10 + 15 = 25 points) [Make sure you read Chapter 16 before attempting this problem.] Chapter 16. Exercise 6, page 247. This problem has two parts. Given the following data type data Tree = Leaf Int | Node Tree Tree 1. (5+5 = 10) Given a tree, function leaves counts the number of leaves in the tree, and function nodes the number of internal nodes in the tree. Define leaves and nodes. The function types are as follows. leaves :: Tree -> Int nodes :: Tree -> Int 2. (Base case 5 points + inductive case 10 points = 15 points) Prove the following property by induction on trees. leaves t = nodes t + 1 Problem 5. (40 points) Chapter 8, Exercise 9. Study Section 8.7 carefully before attempt- ing this problem. The skeleton code contains more explanation on what you are supposed to do