— Assignment 3
— Due: Thursday Oct 6 23:59
— Submission instructions
Copyright By PowCoder代写 加微信 powcoder
— 1. Add your code to this file and submit just this file.
— 2. You can define the functions any way you want, as long as you
— don’t change their names or types or use prohibited items
— 3. Prohibitions: no list comprehension; no imports of Haskell librariesx
import Prelude hiding (lookup)
— Here is A data type representing simple expressions of the kind found
— in boolean algebra or basic arithmetic.
Const String — constants like 0, 17, true
| App1 String E — one-argument operators like – (negation) and ~ (not)
| App2 String E E — two-argument operators like +, *, &
| Var String — represents variables, like x and y in x+y+3
deriving Show
— Some handy expression builders.
zero = Const “0”
one = Const “1”
neg e = App1 “-” e
add e1 e2 = App2 “+” e1 e2
mult e1 e2 = App2 “*” e1 e2
btrue = Const “true”
bfalse = Const “false”
band e1 e2 = App2 “&” e1 e2
bor e1 e2 = App2 “|” e1 e2
bnot e = App1 “~” e
— e represents the expression x*(y+1)
— If you evaluate e in ghci, you get
— App2 “*” (Var “x”) (App2 “+” (Var “y”) (Const “1”))
e = mult (Var “x”) (add (Var “y”) one)
— Question 1
— The type Env below represents what we’ll call environements, which
— are just data structures for recording the values of variables. It’s
— like the databases of assignment 2, with variables (string) in place
— of student ids, and values instead of scores.
— Write a function lookup which gets the value associated with the
— given variable name.
data Env a = EmptyEnv | EnvAdd String a (Env a)
lookup :: String -> Env a -> Maybe a — Don’t change the type.
lookup = undefined — Change what you like on this linei
— except for the name of the function
— Question 2
— Write a function hasValue which says if a varivble has a value in
— the environment.
hasValue :: String -> Env a -> Bool
hasValue = undefined
— Question 3
— Write a function hasVar that determines if an expression has a variable in it.
hasVar :: E -> Bool
hasVar = undefined
— Question 4
— Write a function evalArithE0 that gives the value of an arithmetic expression
— that has no variables in it..
— An arithmetic expression is one that can be built using just zero, one, add,
— neg and mult defined above, and variables.
evalArith0 :: E -> Int
evalArith0 = undefined
— Question 5
— Write a function evalArithE that gives the value of an arithmetic expression,
— using an environment for the values of the variables in the expression. You
— can assume that the environment has an entry for every variable in the expression.
evalArith :: Env Int -> E -> Int
evalArith = undefined
— Question 6 BONUS QUESTION
— Note: bonus questions need to be substantially correct to get any points.
— Write a function that takes a boolean expression and determines if it’s
— satisfiable, i.e. if there is some choice of values for the variables that
— makes the expression true. Return the satisfying assignment as an environment.
— A boolean expression is one that can be built using bfalse, btrue, bnot,
— band, bor and variables.
sat :: E ->
sat = undefined
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com