PLEASE HELP!! this is a Haskell programming assignment! I've attached the given skeleton at the very bottom.

Part 1. Recursive functions, higher order functions [Read Chapter 7] Problem 1. This problem has two subproblems.

1. Define a recursive function mergeBy that merges two sorted lists by the given criterion, for example, in an ascending order or in a descending order, so that the resulting list is also sorted (by the given criterion). Type signature of mergeBy is as follows. mergeBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] 1 Notice the difference from merge :: Ord a => [a] -> [a] -> [a] in Ch. 6 Exercise 7, in that mergeBy accepts three arguments, the first of which is a comparison function of type (a -> a -> Bool) that determines in which way the list is to be sorted. Such comparison function that returns a Boolean value (true or false) is called a predicate.

2. Using mergeBy that you wrote above define a recursive function msortBy. The problem specification stays the same as that for msort in Ch. 6 Exercise 8, except the additional requirement of the first argument being a predicate. Thus, the type of msortBy is: msortBy :: (a -> a -> Bool) -> [a] -> [a] Problem 2. (10 points) Chapter 7. Exercise 9, page 90. altMap :: (a -> b) -> (a -> b) -> [a] -> [b]

Problem 3. Using map, filter, and . (function composition operator), define a function that examines a list of strings, keeping only those whose length is odd, converts them to upper case letters, and concatenates the results to produce a single string. concatenateAndUpcaseOddLengthStrings :: [String] -> String You need to import Data.Char in order to use the toUpper function (see the skeleton code).

Problem 4. This problem has two parts: 1. (7 points) Using guarded equations, implement a function myInsert that behaves the same way as the insert function defined in Data.List package. The Data.List.insert function takes an element and a list and inserts the element into the list at the first position where it is less than or equal to the next element. In particular, if the list is sorted before the call, the result will also be sorted. myInsert :: Ord a => a -> [a] -> [a] 2. Using myInsert and foldr, implement insertion sort. insertionSort :: Ord a => [a] -> [a] Part 2: Data types, type classes, proof by induction [Read Chapters 8 and 16] Use the following data type for Problems 5 and 6. data Tree2 a b = Leaf a | Branch b (Tree2 a b) (Tree2 a b)

Problem 5. 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 6. 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] 2 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 7. [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) First define functions that count the number of leaves (leaves) and the number of internal nodes (nodes) in a tree. The function types are as follows. leaves :: Tree -> Int nodes :: Tree -> Int 2. (Base case 10 points + inductive case 10 points) Prove the following property by induction on trees. leaves t = nodes t + 1 Part 3: A tiny language [Read Chapter 8] Let E (for expression) be a tiny programming language that supports the declaration of arithmetic expressions involving only addition and multiplication, and equality comparisons on integers. Here is an example program in E: 1 + 9 == 5 * ( 1 + 1 ) When evaluated, this program should evaluate to the truth value true. In this exercise, we will not write E programs as strings, but as values of a Haskell data type E, that can represent E programs as their abstract syntax trees (ASTs). Given the following data type E, data E = IntLit Int -- for Int literal, e.g., (IntLit 3) | BoolLit Bool -- for Bool literal, e.g., (BoolLit False) | Plus E E -- for addition | Mult E E -- for multiplication | Equals E E deriving (Eq, Show) The above example program is represented as its AST: program = Equals (Plus (IntLit 1) (IntLit 9)) (Mult (IntLit 5) (Plus (IntLit 1) (IntLit 1)))

Problem 8. Define an evaluator for the language E. Its name and type should be eval :: E -> E The result of eval should not contain any operations or comparisons, just a value constructed either with IntLit or BoolLit constructors. The result of the example program above should be BoolLit True. Note that E allows nonsensical programs, such as Plus (BoolLit True) (IntLit 1). For such programs, the evaluator can abort.

Skeleton Code

module Main where

import Test.HUnit import System.Exit import Data.List import Data.Char

---- Part 1. Recursive functions, higher order functions [Read Chapter 7] -- Problem 1.1 mergeBy :: (a -> a -> Bool) -> [a] -> [a] -> [a] mergeBy = undefined

-- Problem 1.2 msortBy :: (a -> a -> Bool) -> [a] -> [a] msortBy = undefined

-- Problem 2 -- altMap altMap :: (a -> b) -> (a -> b) -> [a] -> [b] altMap = undefined

-- Problem 3 concatenateAndUpcaseOddLengthStrings :: [String] -> String concatenateAndUpcaseOddLengthStrings = undefined

-- Problem 4.1 myInsert :: Ord a => a -> [a] -> [a] myInsert = undefined

-- Problem 4.2 insertionSort :: Ord a => [a] -> [a] insertionSort = undefined

---- Part 2. Data types, type classes, proof by induction ---- [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 5 and 6 tree2a = Branch "A" (Branch "B" (Leaf2 1) (Leaf2 2)) (Leaf2 3)

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

-- Problem 5 instance (Show a, Show b) => Show (Tree2 a b) where show t = undefined -- Problem 6 preorder :: (a -> c) -> (b -> c) -> Tree2 a b -> [c] preorder = undefined

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

-- Problem 7

data Tree = Leaf Int | Node Tree Tree

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

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

-- Problem 7.1 leaves :: Tree -> Int leaves = undefined

nodes :: Tree -> Int nodes = undefined

-- Problem 7.2 {-- (Write your induction proof within this block comment.) Base case:

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

--}

---- Part 3. A tiny language [Read Chapter 8] data E = IntLit Int -- for Int literal, e.g., (IntLit 3) | BoolLit Bool -- for Bool literal, e.g., (BoolLit False) | Plus E E -- for addition | Mult E E -- for multiplication | Equals E E deriving (Eq, Show)

-- Problem 8. eval :: E -> E eval = undefined

--------------- E objects prog1 :: E -- to be used to test Problem 8 prog1 = Equals (Plus (IntLit 1) (IntLit 9)) (Mult (IntLit 5) (Plus (IntLit 1) (IntLit 1)))

prog2 :: E -- to be used to test Problem 8 prog2 = Equals (Equals (Mult (IntLit 4) (IntLit 2)) (Plus (IntLit 5) (Mult (IntLit 2) (IntLit 1)))) (Equals (BoolLit True) (BoolLit True)) --------------- myTestList =

let te s e a = test $ assertEqual s e a tb s b = test $ assertBool s b in TestList [ te "mergeBy 1" "GFEDBA" (mergeBy (>) "FED" "GBA") , te "mergeBy 2" "HMaouiwdy" (mergeBy (<) "Howdy" "Maui") , te "msortBy 1" " 'eggim" (msortBy (<) "gig 'em") , te "msortBy 2" "nmlkieecbbaJ " (msortBy (>) "Jack be nimble") , te "msortBy 3" "" (msortBy (<) "")

, te "altMap 1" [10,200,30,400,50] (altMap (* 10) (* 100) [1,2,3,4,5]) , te "altMap 2" False (and (altMap even odd [1..10])) , te "altMap 3" "hAsKeLl iS FuN!" (altMap toLower toUpper "Haskell IS fun!")

, te "concatenateAndUpcaseOddLengthStrings" "HERE'S AN EXAMPLE" (concatenateAndUpcaseOddLengthStrings ["here's ", "an ", "a ", "example"])

, te "myInsert 1" "How are you?" (myInsert 'o' "Hw are you?") , te "myInsert 2" "abcdefg" (myInsert 'c' "abdefg")

, te "insertionSort" " Jabcceikkqu" (insertionSort "Jack be quick")

, te "preorder 1" "AB123" (concat (preorder show id tree2a)) , te "inorder 1" "1B2A3" (concat (inorder show id tree2a)) , te "preorder 2" "+*3+45+*678" (concat (preorder show id tree2b)) , te "inorder 2" "3*4+5+6*7+8" (concat (inorder show id tree2b))

, te "leaves 1" 6 (leaves tree3) , te "leaves 2" 5 (leaves tree4) , te "nodes 1" 5 (nodes tree3) , te "nodes 2" 4 (nodes tree4)

, te "eval1" (BoolLit True) (eval prog1) , te "eval2" (BoolLit False) (eval prog2) ]

main = do c <- runTestTT myTestList putStrLn $ show c let errs = errors c fails = failures c exitWith (codeGet errs fails) codeGet errs fails | fails > 0 = ExitFailure 2 | errs > 0 = ExitFailure 1 | otherwise = ExitSuccess