(Answered): How do I code this, Must be coded in Haskell. 1. [40%] A well-formed formula (wff) of Propositional ...

1. [40%] A well-formed formula (wff) of Propositional Logic is one of the following: • a propositional variable (with a name of type String), • the negation of a wff (i.e., not), • the conjunction of two wffs (i.e., and), or • the disjunction of two wffs (i.e., or). Except for the above there are no other wffs. (a) [10%] Declare a Haskell algebraic type Formula to represent wffs. (b) [5%] Give a Haskell expression that constructs a Formula representation of the for- mula “-(p1-9)” (c) [5%] Define a function showFormula :: Formula -> String such that (showFormula f) returns a string representation of the formula f. You need this function for debugging the following part. Hint: Your implementation shall be primi- tively recursive. There is no need to do factorization or simplification. Print parentheses to disambiguate syntax. (d) [20%] A wff p is in Negation Normal Form (NNF) if and only if every negation occurring in p is applied to a propositional variable. For example, the following wffs are in NNF (x, y, and z are propositional variables): (2 Ay) V- The following wffs are not in NNF: (2) Any 2A-V-2) It is a well-known fact in Propositional Logic that every wff can be converted to an equivalent wff in NNF. The idea is to apply the following rewriting rules repeatedly, until no more rewriting can be performed: 77p =P -(19) = (p) (9) -(pVq) = (-p) ^(-9) The following wffs are not in NNF: (2) Any A-y V-2) It is a well-known fact in Propositional Logic that every wff can be converted to an equivalent wff in NNF. The idea is to apply the following rewriting rules repeatedly, until no more rewriting can be performed: 77p =P -(19) = (p) (9) -(pVq) = (-p) ^ (9) Develop a Haskell function 1 rewrite :: Formula -> Formula such that (rewrite f) returns a wff f' such that (i) f' is logically equivalent to f, and (ii) f' is in NNF. Hint: The function rewrite requires general recursion. While this assignment does not ask you to devise a termination proof, it is to your best interest to keep such a proof in the back of your mind when you formulate the general recursion. Again, there is no need to submit a termination proof. Any such submission will not be graded. 3. [20%] Use map, filter, and/or foldr/foldr1 to implement the following Haskell func- tions. You shall demonstrate the use of anonymous functions (i.e., lambda abstractions) in the implementation of at least one of following functions. (a) [6%] lastElm :: [a] => a. The function returns the last element of the list argu- ment. (b) [6%] unanimous :: [a->Bool] -> a -> Bool. The function takes a list of pred- icates and an entity as arguments, then applies every predicate to the entity, and finally returns True if and only if every predicate in the list returns True. In the degenerate case, when the list argument is empty, then True is returned. (c) [8%] selectiveMap :: (a->Bool) -> (a->b) => [a] -> [b]. The func- tion takes three arguments: (i) a predicate for type-a values, (ii) a function that trans- forms a type-a value to a type-b value, and (iii) a list of type-a values. The function selectiveMap tests every element of the list argument using the given predicate. Those elements that satisfy the predicate will be transformed by the function argument. The transformed elements are then collected into a list, which is returned as the value of selectiveMap.