Using the Haskell programming language, write an applicative order interpreter that yields an answer in Normal Form (i.e., the expression cannot be further reduced).

A lambda expression is of the following form:

data Expr = Var Name --- a variable | App Expr Expr --- function application | Lambda Name Expr --- lambda abstraction deriving (Eq,Show) --- the Expr data type derives from built-in Eq and Show classes, --- thus, we can compare and print expressions type Name = String --- a variable name 

You are required to implement the following functions:

Free variables. As a first step, write the function

freeVars :: Expr -> [Name]

It takes an expression expr and returns the list of variables that are free in expr without repetition. For example freeVars (App (Var "x") (Var "x")) yields ["x"].

Generating new names. Next, generate fresh variables for a list of expressions by making use of the infinite list of positive integers [1..]. Write a function

freshVars :: [Expr] -> [Name]

It takes a list of expressions and generates an (infinite) list of variables that are not free in any of the expressions in the list. For example freshVars [Lambda "1_" (App (Var "x") (App (Var "1_") (Var "2_")))] yields the infinite list [1_,3_,4_,5_,..]. Remember, you will leverage [1..] to implement freshVars.

Substitution. Next, write the substitution function

subst :: (Name,Expr) -> Expr -> Expr

All functions in Haskell are curried: i.e., they take just one argument. The above function takes a variable x and an expression e, and returns a function that takes an expression E and returns E[e/x]. Important: subst must implement the algorithm we gave in class! Specifically, when performing a substitution on a lambda expression y.E1, where yx, subst must always replace parameter ywith the next fresh variable from the list of freshVars, even if y is not free in e and it would have been "safe" to leave it as is. This is necessary for autograding on Submitty.

A single step. Now write a function to do a single step of reduction:

appNF_OneStep :: Expr -> Maybe Expr

where the built-in Maybe type is defined as follows:

data Maybe a = Nothing | Just a 

appNF_OneStep takes an expression e. If there is a redex available in e, it picks the correct applicative order redex and reduces e. (Note that in applicative order we are pursuing the leftmost, innermost strategy as follows. Pick the leftmost redex R; if there are nested (inner) redexes within R, pick the leftmost one, and so on, until we reach a redex without nested ones.) If a reduction was carried out, resulting in a new expression expr', appNF_OneStep returns Just expr', otherwise it returns Nothing.

Repetition. Finally, write a function

appNF_n :: Int -> Expr -> Expr

Given an integer n and an expression e, appNF_n does n reductions (or as many as possible) and returns the resulting expression.