WHAT DO I NEED TO REDEFINE IN THE IMPLEMENTATIONS, MENTIONED BELOW IN ORDER TO SATISFY THE FOLLOWING REQUIREMENTS? Define functions to perform reduction of both arithmetic and lambda expressions. Implement an innermost leftmost reduction strategy for both. Compare the differences between the lengths of reduction sequences to terminated values for innermost reduction for a given arithmetic expression and the lambda expression obtained by converting the arithmetic expression to a lambda expression as defined in the function churchEnc In order to understand evaluation in the language of arithmetic expressions, we need to identify the redexes of that language. We will express these using the Haskell datatype : Add (ArithNum n) (ArithNum m) ------> ArithNum ( n + m ) Mul (ArithNum n) (ArithNum m) ------> ArithNum ( n * m ) SecApp (Section (ArithNum n)) (ArithNum m) -----> ArithNum ( n + m ) all reductions of arithmetic expressions are an instance of one of these within a possibly larger expression. Define a function: innerRedn1 :: LamExpr -> Maybe LamExpr that takes a lambda expression and performs a single reduction on that expression, if possible, by returning the reduced expression. The func0on should implement the (leftmost) innermost reduction strategy. Similarly, define innerArithRedn1 :: ArithExpr -> Maybe ArithExpr that takes an arithme0c expression and performs a single reduction on that expression, if possible, by returning the reduced expression. Again, the function should implement the (leftmost) innermost reduction strategy. Define a function compareArithLam :: ArithExpr -> ( Int, Int ) that takes an arithmetic expression and returns a pair containing the length of two reduction sequences In each case the number returned should be the number of steps needed for the expression to terminate. Given an input arithmetic expression E, the pair should contain lengths for (in this order) : 1. Innermost reduction on E 2. Innermost reduction on the lambda calculus translation of E: < E > Example usages of the compareArithLam function (inputs are preAy printed) are: compareArithLam (ArithNum 4) = (0,0) compareArithLam (Add (ArithNum 4) (ArithNum 5)) = (1,6) compareArithLam (Mul (Add (ArithNum 4) (ArithNum 5)) (ArithNum 3)) = (2,28) compareArithLam (Mul (SecApp (Section (SecApp (Section (ArithNum 1)) (ArithNum 4))) (ArithNum 5)) (ArithNum 3)) = (3,36). You can use the already defined function churchEnc which has the following syntax without affecting any of its previous output : churchEncInPlace :: ArithExpr -> LamExpr -> LamExpr churchEncInPlace (ArithNum n) expr = LamAbs 0 (LamAbs 1 (churchEncInPlaceHelper n expr 0 1)) where churchEncInPlaceHelper :: Int -> LamExpr -> Int -> Int -> LamExpr churchEncInPlaceHelper 0 _ _ _ = LamVar 1 churchEncInPlaceHelper n expr f x = LamApp (LamVar f) (churchEncInPlaceHelper (n - 1) expr f x) churchEncInPlace (Add e1 e2) expr = LamAbs 0 (LamAbs 1 (LamAbs 2 (LamAbs 3 (LamApp (LamApp (LamVar 0) (churchEncInPlace e1 expr)) (LamApp (LamApp (LamVar 1) (churchEncInPlace e2 expr)) (LamVar 3)))))) churchEncInPlace (Mul e1 e2) expr = LamAbs 0 (LamAbs 1 (LamAbs 2 (LamAbs 3 (LamApp (LamApp (LamVar 0) (churchEncInPlace e1 expr)) (LamApp (LamVar 1) (churchEncInPlace e2 expr)))))) churchEncInPlace (SecApp (Section op) e1) expr = LamApp (LamApp (churchEncInPlace op expr) (churchEncInPlace e1 expr)) (churchEnc (ArithNum 1)) churchEncInPlace (Section (ArithNum n)) expr = LamAbs 0 (LamAbs 1 (LamApp (LamVar 0) (churchEnc (ArithNum n)))) churchEncInPlace expr _ = error "Invalid input" churchEnc :: ArithExpr -> LamExpr churchEnc (ArithNum 0) = LamAbs 0 (LamAbs 1 (LamVar 1)) churchEnc (ArithNum n) = LamAbs 0 (LamAbs 1 (churchEncHelper n 0 1)) where churchEncHelper :: Int -> Int -> Int -> LamExpr churchEncHelper 0 _ _ = LamVar 1 churchEncHelper n f x = LamApp (LamVar f) (churchEncHelper (n - 1) f x) churchEnc (Add e1 e2) = LamAbs 0 (LamAbs 1 (LamAbs 2 (LamAbs 3 (LamApp (LamApp (LamVar 0) (churchEnc e1)) (LamApp (LamApp (LamVar 1) (churchEnc e2)) (LamVar 3)))))) churchEnc (Mul e1 e2) = LamAbs 0 (LamAbs 1 (LamAbs 2 (LamAbs 3 (LamApp (LamApp (LamVar 0) (churchEnc e1)) (LamApp (LamVar 1) (churchEnc e2)))))) churchEnc (SecApp (Section op) e1) = LamApp (LamApp (churchEnc op) (churchEnc e1)) (churchEnc (ArithNum 1)) churchEnc (Section (ArithNum n)) = LamAbs 0 (LamAbs 1 (LamApp (LamVar 0) (churchEnc (ArithNum n)))) innerRedn1 :: LamExpr -> Maybe LamExpr innerRedn1 (LamAbs x e) = LamAbs x <$> innerRedn1 e innerRedn1 (LamApp e1 e2) = case innerRedn1 e2 of -- try to reduce the second argument first Just e2' -> Just (LamApp e1 e2') Nothing -> case innerRedn1 e1 of -- try to reduce the first argument Just e1' -> Just (LamApp e1' e2) Nothing -> case e1 of LamAbs x e1' -> Just (substitute e1' x e2) _ -> case e1 of LamApp e1'' e2'' -> Just (LamApp e1'' e2'') _ -> Nothing innerRedn1 (LamVar _) = Nothing -- Define the substitute function substitute :: LamExpr -> Int -> LamExpr -> LamExpr substitute (LamVar y) x e | x == y = e | otherwise = LamVar y substitute (LamAbs y e1) x e | x == y = LamAbs y e1 | x /= y && y `notElem` freeVars e = LamAbs y (substitute e1 x e) | otherwise = LamAbs z (substitute e1 x (shift e (z - y))) where z = freshVar e substitute (LamApp e1 e2) x e = LamApp (substitute e1 x e) (substitute e2 x e) -- Define the shift function shift :: LamExpr -> Int -> LamExpr shift (LamVar y) d | y >= d = LamVar (y + d) | otherwise = LamVar y shift (LamAbs y e1) d = LamAbs y' (shift e1 d') where y' = if y >= d then y + d else y d' = d + 1 shift (LamApp e1 e2) d = LamApp (shift e1 d) (shift e2 d) -- Define the freeVars function freeVars :: LamExpr -> [Int] freeVars (LamVar x) = [x] freeVars (LamAbs x e) = filter (/= x) (freeVars e) freeVars (LamApp e1 e2) = freeVars e1 ++ freeVars e2 -- Define the freshVar function freshVar :: LamExpr -> Int freshVar e = head (filter (\x -> x `notElem` freeVars e) [0..]) evalChurchEnc :: LamExpr -> (LamExpr, LamExpr) -> LamExpr evalChurchEnc expr (f, x) = go expr where go (LamVar y) | y == 0 = x | y == 1 = f | otherwise = error "Invalid input" go (LamAbs y e) = LamAbs y (go e) go (LamApp e1 e2) = go e1 `LamApp` go e2 countReductions :: ArithExpr -> Int countReductions expr = go 0 expr where go :: Int -> ArithExpr -> Int go count expr = case innerArithRedn1 expr of Just expr' -> go (count + 1) expr' Nothing -> count arithEnc :: LamExpr -> Maybe ArithExpr arithEnc (LamVar _) = Nothing arithEnc (LamAbs _ _) = Nothing arithEnc (LamApp (LamAbs _ _) e) = arithEnc e -- reduce the application arithEnc (LamApp e1 e2) = case arithEnc e1 of -- try to convert the first argument to an arithmetic expression Just (ArithNum n) -> case arithEnc e2 of -- try to convert the second argument to an arithmetic expression Just (ArithNum m) -> Just (Add (ArithNum n) (ArithNum m)) -- return the addition of the two numbers _ -> Nothing -- the second argument could not be converted to an arithmetic expression Just (Mul (ArithNum n) e) -> -- the first argument is a Church numeral representing a non-zero number case arithEnc e2 of -- try to convert the second argument to an arithmetic expression Just (ArithNum m) -> Just (Mul (ArithNum n) (ArithNum m)) -- return the multiplication of the two numbers _ -> Nothing -- the second argument could not be converted to an arithmetic expression Just (SecApp (ArithNum 1) e) -> -- the first argument is a Church numeral representing the number 1 case arithEnc e2 of -- try to convert the second argument to an arithmetic expression Just arithExpr -> Just (SecApp (ArithNum 1) arithExpr) -- return the secApp operation applied to the two converted arithmetic expressions _ -> Nothing -- the second argument could not be converted to an arithmetic expression Just (SecApp (ArithNum 0) e) -> -- the first argument is a Church numeral representing the number 0 case arithEnc e2 of -- try to convert the second argument to an arithmetic expression Just arithExpr -> Just (SecApp (ArithNum 0) arithExpr) -- return the secApp operation applied to the two converted arithmetic expressions _ -> Nothing -- the second argument could not be converted to an arithmetic expression _ -> Nothing -- the first argument could not be converted to an arithmetic expression innerArithRedn1 :: ArithExpr -> Maybe ArithExpr innerArithRedn1 expr = case expr of ArithNum _ -> Nothing -- no further reduction is possible for a numeric literal Add (ArithNum n) (ArithNum m) -> Just (ArithNum (n + m)) -- reduce numeric addition Add e1 e2 -> case (e1, e2) of -- try to apply the Add operation (ArithNum n, e2') -> Just (Add (ArithNum n) e2') -- apply Add if the first operand is an ArithNum literal (e1', ArithNum m) -> Just (Add e1' (ArithNum m)) -- apply Add if the second operand is an ArithNum literal _ -> case innerArithRedn1 e1 of -- try to reduce the first operand Just e1' -> Just (Add e1' e2) -- if reduction is possible, apply it Nothing -> case innerArithRedn1 e2 of -- try to reduce the second operand Just e2' -> Just (Add e1 e2') -- if reduction is possible, apply it Nothing -> Nothing -- if no further reduction is possible, return Nothing Mul (ArithNum n) (ArithNum m) -> Just (ArithNum (n * m)) -- reduce numeric multiplication Mul e1 e2 -> case innerArithRedn1 e1 of -- try to reduce the first operand Just e1' -> Just (Mul e1' e2) Nothing -> case innerArithRedn1 e2 of -- try to reduce the second operand Just e2' -> Just (Mul e1 e2') Nothing -> Nothing SecApp (Section op) e1 -> case innerArithRedn1 op of Just op' -> Just (SecApp (Section op') e1) Nothing -> case innerArithRedn1 e1 of Just e1' -> Just (SecApp (Section op) e1') Nothing -> case op of ArithNum n -> Just (ArithNum (n + 1)) _ -> Nothing compareArithLam :: ArithExpr -> (Int, Int) compareArithLam expr = (countArithReductions expr, countLamReductions (churchEnc expr)) where countArithReductions :: ArithExpr -> Int countArithReductions expr = go 0 expr where go :: Int -> ArithExpr -> Int go count expr = case innerArithRedn1 expr of Just expr' -> go (count + 1) expr' Nothing -> count countLamReductions :: LamExpr -> Int countLamReductions expr = go 0 expr where go :: Int -> LamExpr -> Int go count expr = case innerRedn1 expr of Just expr' -> go (count + 1) expr' Nothing -> count countArithReductions :: ArithExpr -> (Int, Int) countArithReductions expr = go 0 expr where go :: Int -> ArithExpr -> (Int, Int) go count expr = case innerArithRedn1 expr of Just expr' -> go (count + 1) expr' Nothing -> (count, calculateValue expr) calculateValue :: ArithExpr -> Int calculateValue (ArithNum n) = n calculateValue (Add e1 e2) = (calculateValue e1) + (calculateValue e2) calculateValue (Mul e1 e2) = (calculateValue e1) * (calculateValue e2) calculateValue (SecApp (Section op) e1) = (calculateValue op) * (calculateValue e1) calculateValue (Section (ArithNum n)) = n WITH MY DEFINITION I GET THE FOLLOWING OUTPUTS FOR THE TEST CASES: compareArithLam (ArithNum 4) = (0,0) compareArithLam (Add (ArithNum 4) (ArithNum 5)) = (1,2) compareArithLam (Mul (Add (ArithNum 4) (ArithNum 5)) (ArithNum 3)) = (2,3) compareArithLam (Mul (SecApp (Section (SecApp (Section (ArithNum 1)) (ArithNum 4))) (ArithNum 5)) (ArithNum 3)) = (3,34) HOWEVER, THE DESIRED ONE RETURN THE FOLLOWING VALUES: compareArithLam (ArithNum 4) = (0,0) compareArithLam (Add (ArithNum 4) (ArithNum 5)) = (1,6) compareArithLam (Mul (Add (ArithNum 4) (ArithNum 5)) (ArithNum 3)) = (2,28) compareArithLam (Mul (SecApp (Section (SecApp (Section (ArithNum 1)) (ArithNum 4))) (ArithNum 5)) (ArithNum 3)) = (3,36)