import Test.QuickCheck import Data.List (lookup) -- An 'IdExpr' is an expression-tree…
- User
import Test.QuickCheck import Data.List (lookup)
-- | An 'IdExpr' is an expression-tree over integers and string identifiers. data IdExpr = Id String | Leaf Int | Add IdExpr IdExpr | Sub IdExpr IdExpr | Mul IdExpr IdExpr | Uminus IdExpr deriving (Eq, Show)
-- | 'Assoc' is a list of pairs mapping identifier strings to their values v. type Assoc v = [(String, v)]
-- | Returns evaluation of the 'IdExpr' expression-tree given by its first argument, -- looking up the values of ids in the 'Assoc' argument. If an id is not found -- in the 'Assoc' argument, then its value should default to 0.
-- > evalIdExpr (Leaf 42) [] == 42 -- > evalIdExpr (Add (Leaf 33) (Leaf 22)) [] == 55 -- > evalIdExpr (Sub (Leaf 33) (Leaf 22)) [] == 11 -- > evalIdExpr (Mul (Leaf 31) (Leaf 4)) [] == 124 -- > evalIdExpr (Uminus (Leaf 33)) [] == (-33) -- > evalIdExpr (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20))) [] == (-200)
-- > evalIdExpr (Id "a") [("a", 42)] == 42 -- > evalIdExpr (Id "a") [("b", 42)] == 0 -- > evalIdExpr (Add (Id "a") (Id "b")) [("a", 42)] == 42 -- > evalIdExpr (Add (Id "a") (Id "b")) [("a", 42), ("b", 22)] == 64 -- > evalIdExpr (Mul (Id "a") (Sub (Add (Id "b") (Uminus (Id "c"))) (Id "d"))) [("a", 4), ("b", 3), ("c", 33), ("d", 20)] == (-200)
-- > quickCheck \ id1 val1 -> evalIdExpr (Id id1) [(id1, val1)] == val1 -- > quickCheck \ id1 val1 -> evalIdExpr (Id id1) [(id1 ++ "x", val1)] == 0
-- > quickCheck \ e1 e2 -> evalIdExpr (Add (Leaf e1) (Leaf e2)) [] == evalIdExpr (Add (Leaf e2) (Leaf e1)) [] -- > quickCheck \ e1 e2 -> evalIdExpr (Mul (Leaf e1) (Leaf e2)) [] == evalIdExpr (Mul (Leaf e2) (Leaf e1)) [] -- > quickCheck \ e1 e2 e3 -> evalIdExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalIdExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3)))
- Assistant
Given the provided definitions and test cases, we'll first implement the
evalIdExprfunction which evaluates an expression tree (IdExpr), given an association list (Assoc Int) for identifier lookup.-- | Evaluates an expression tree given an association list for identifier lookup. evalIdExpr :: IdExpr -> Assoc Int -> Int evalIdExpr expr assoc = case expr of Id idStr -> maybe 0 id (lookup idStr assoc) Leaf n -> n Add e1 e2 -> evalIdExpr e1 assoc + evalIdExpr e2 assoc Sub e1 e2 -> evalIdExpr e1 assoc - evalIdExpr e2 assoc Mul e1 e2 -> evalIdExpr e1 assoc * evalIdExpr e2 assoc Uminus e -> -evalIdExpr e assocThis function works by recursively evaluating the
IdExprtree. If the current node is anId, it looks up the identifier in the association list; if the identifier is not found, it defaults to0as specified. ForLeaf, it simply returns the embedded integer. For the binary operations (Add,Sub,Mul), it recursively evaluates both operands and applies the appropriate operation to the results. For a unary minus (Uminus), it recursively evaluates the operand and negates the result.With this implementation, the provided test cases from the comment description should pass. These test cases cover:
- Evaluation of simple expressions involving only integers.
- Evaluation using an association list for variable lookup, including cases where variables are and are not present in the list.
- Commutativity of addition and multiplication.
- Associativity of addition.
By running these test cases through
QuickCheck, we can further ensure the correctness of our implementation across a wide range of randomly generated expressions and association lists.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.