Skip to content
The Chat Archive
gpt-4-0125-preview· OpenAI WildChat-4.8M (AI2)

module EvalIdExpr ( evalIdExpr, testEvalIdExpr ) where import Test.QuickCheck import…

  1. User

    module EvalIdExpr ( evalIdExpr, testEvalIdExpr ) where

    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) ]

    evalIdExpr returns evaluation of the IdExpr expression-tree given by its first argument, looking up the values of id's in the Assoc argument. If an id is not found in the Assoc argument, then its value should default to 0. Hint: use Data.List.lookup imported above. evalIdExpr :: IdExpr -> Assoc Int -> Int evalIdExpr _ = error "TODO"

    testEvalIdExpr = do print "*** test evalIdExpr" -- unit tests quickCheck counterexample"Leaf"counterexample "Leaf" evalIdExpr (Leaf 42) [] == 42 quickCheck counterexample"Add"counterexample "Add" evalIdExpr (Add (Leaf 33) (Leaf 22)) [] == 55 quickCheck counterexample"Sub"counterexample "Sub" evalIdExpr (Sub (Leaf 33) (Leaf 22)) [] == 11 quickCheck counterexample"Mul"counterexample "Mul" evalIdExpr (Mul (Leaf 31) (Leaf 4)) [] == 124 quickCheck counterexample"Uminus"counterexample "Uminus" evalIdExpr (Uminus (Leaf 33)) [] == (-33) quickCheck counterexample"Complex"counterexample "Complex" evalIdExpr (Mul (Leaf 4) (Sub (Add (Leaf 3) (Uminus (Leaf 33))) (Leaf 20))) [] == (-200)

    -- id unit tests quickCheck counterexample"okidlookup"counterexample "ok id lookup" evalIdExpr (Id "a") [("a", 42)] == 42 quickCheck counterexample"failidlookup"counterexample "fail id lookup" evalIdExpr (Id "a") [("b", 42)] == 0 quickCheck counterexample"idlookup:a:ok,b:fail"counterexample "id lookup: a: ok, b: fail" evalIdExpr (Add (Id "a") (Id "b")) [("a", 42)] == 42 quickCheck counterexample"idlookup:a:ok,b:ok"counterexample "id lookup: a: ok, b: ok" evalIdExpr (Add (Id "a") (Id "b")) [("a", 42), ("b", 22)] == 64 quickCheck counterexample"complexidlookup"counterexample "complex id lookup" evalIdExpr (Mul (Id "a") (Sub (Add (Id "b") (Uminus (Id "c"))) (Id "d"))) [("a", 4), ("b", 3), ("c", 33), ("d", 20)] == (-200)

    -- property-based tests -- id lookup quickCheck counterexample"randomidlookupok"counterexample "random id lookup ok" (\ id1 val1 -> evalIdExpr (Id id1) [(id1, val1)] == val1) quickCheck counterexample"randomidlookupfail"counterexample "random id lookup fail" (\ id1 val1 -> evalIdExpr (Id id1) [(id1 ++ "x", val1)] == 0)

    -- property-based tests -- commutativity quickCheck counterexample"e1+e2==e2+e1"counterexample "e1 + e2 == e2 + e1" (\ e1 e2 -> evalIdExpr (Add (Leaf e1) (Leaf e2)) [] == evalIdExpr (Add (Leaf e2) (Leaf e1)) []) quickCheck counterexample"e1∗e2==e2∗e1"counterexample "e1 * e2 == e2 * e1" (\ e1 e2 -> evalIdExpr (Mul (Leaf e1) (Leaf e2)) [] == evalIdExpr (Mul (Leaf e2) (Leaf e1)) []) -- associativity quickCheck counterexample"(e1+e2)+e3==e1+(e2+e3)"counterexample "(e1 + e2) + e3 == e1 + (e2 + e3)" (\ e1 e2 e3 -> evalIdExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalIdExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3))) []) quickCheck counterexample"(e1∗e2)∗e3==e1∗(e2∗e3)"counterexample "(e1 * e2) * e3 == e1 * (e2 * e3)" (\ e1 e2 e3 -> evalIdExpr (Mul (Mul (Leaf e1) (Leaf e2)) (Leaf e3)) [] == evalIdExpr (Mul (Leaf e1) (Mul (Leaf e2) (Leaf e3))) [])

    -- subtraction quickCheck counterexample"e1−e2=−1∗(e2−e1)"counterexample "e1 - e2 = -1*(e2 - e1)" (\ e1 e2 -> evalIdExpr (Sub (Leaf e1) (Leaf e2)) [] == evalIdExpr (Mul (Leaf (-1)) (Sub (Leaf e2) (Leaf e1))) [])

    -- distributivity quickCheck counterexample"e1∗(e2+e3)==e1∗e2+e1∗e3"counterexample "e1 * (e2 + e3) == e1*e2 + e1*e3" (\ e1 e2 e3 -> evalIdExpr (Mul (Leaf e1) (Add (Leaf e2) (Leaf e3))) [] == evalIdExpr (Add (Mul (Leaf e1) (Leaf e2)) (Mul (Leaf e1) (Leaf e3))) []) quickCheck counterexample"e1∗(e2−e3)==e1∗e2−e1∗e3"counterexample "e1 * (e2 - e3) == e1*e2 - e1*e3" (\ e1 e2 e3 -> evalIdExpr (Mul (Leaf e1) (Sub (Leaf e2) (Leaf e3))) [] == evalIdExpr (Sub (Mul (Leaf e1) (Leaf e2))
    (Mul (Leaf e1) (Leaf e3))) [])

  2. Assistant

    Based on the given instructions and hints, I will implement the evalIdExpr function. This function evaluates an expression tree (IdExpr) by looking up the values of identifiers in an association list (Assoc). If an identifier is not found, its value defaults to 0.

    module EvalIdExpr ( evalIdExpr, testEvalIdExpr ) where
    
    import Test.QuickCheck
    import Data.List (lookup)
    
    data IdExpr =
      Id String |
      Leaf Int |
      Add IdExpr IdExpr |
      Sub IdExpr IdExpr |
      Mul IdExpr IdExpr |
      Uminus IdExpr
      deriving (Eq, Show)
    
    type Assoc v = [ (String, v) ]
    
    evalIdExpr :: IdExpr -> Assoc Int -> Int
    evalIdExpr (Leaf n) _ = n
    evalIdExpr (Id s) assoc = maybe 0 id (lookup s assoc)
    evalIdExpr (Add e1 e2) assoc = (evalIdExpr e1 assoc) + (evalIdExpr e2 assoc)
    evalIdExpr (Sub e1 e2) assoc = (evalIdExpr e1 assoc) - (evalIdExpr e2 assoc)
    evalIdExpr (Mul e1 e2) assoc = (evalIdExpr e1 assoc) * (evalIdExpr e2 assoc)
    evalIdExpr (Uminus e) assoc = -(evalIdExpr e assoc)
    
    testEvalIdExpr :: IO ()
    testEvalIdExpr = do
      print "*** test evalIdExpr"
      quickCheck $ counterexample "Leaf" $ evalIdExpr (Leaf 42) [] == 42
      quickCheck $ counterexample "Add" $
        evalIdExpr (Add (Leaf 33) (Leaf 22)) [] == 55
      quickCheck $ counterexample "Sub" $
        evalIdExpr (Sub (Leaf 33) (Leaf 22)) [] == 11
      quickCheck $ counterexample "Mul" $
        evalIdExpr (Mul (Leaf 31) (Leaf 4)) [] == 124
      quickCheck $ counterexample "Uminus" $
        evalIdExpr (Uminus (Leaf 33)) [] == (-33)
      quickCheck $ counterexample "Complex" $
        evalIdExpr (Mul (Leaf 4)
                     (Sub (Add (Leaf 3) (Uminus (Leaf 33)))
                       (Leaf 20))) [] == (-200)
    
      quickCheck $ counterexample "ok id lookup" $
        evalIdExpr (Id "a") [("a", 42)] == 42
      quickCheck $ counterexample "fail id lookup" $
        evalIdExpr (Id "a") [("b", 42)] == 0
      quickCheck $ counterexample "id lookup: a: ok, b: fail" $
        evalIdExpr (Add (Id "a") (Id "b")) [("a", 42)] == 42
      quickCheck $ counterexample "id lookup: a: ok, b: ok" $
        evalIdExpr (Add (Id "a") (Id "b")) [("a", 42), ("b", 22)] == 64
      quickCheck $ counterexample "complex id lookup" $
        evalIdExpr (Mul (Id "a")
                     (Sub (Add (Id "b") (Uminus (Id "c")))
                       (Id "d")))
                   [("a", 4), ("b", 3), ("c", 33), ("d", 20)] == (-200)
    
      quickCheck $ counterexample "random id lookup ok" $
        (\id1 val1 -> evalIdExpr (Id id1) [(id1, val1)] == val1)
      quickCheck $ counterexample "random id lookup fail" $
        (\id1 val1 -> evalIdExpr (Id id1) [(id1 ++ "x", val1)] == 0)
      
      quickCheck $ counterexample "e1 + e2 == e2 + e1" $
        (\e1 e2 -> 
            evalIdExpr (Add (Leaf e1) (Leaf e2)) [] ==
            evalIdExpr (Add (Leaf e2) (Leaf e1)) [])
      quickCheck $ counterexample "e1 * e2 == e2 * e1" $
        (\e1 e2 -> 
            evalIdExpr (Mul (Leaf e1) (Leaf e2)) [] ==
            evalIdExpr (Mul (Leaf e2) (Leaf e1)) [])
      quickCheck $ counterexample "(e1 + e2) + e3 == e1 + (e2 + e3)" $
        (\e1 e2 e3 -> 
            evalIdExpr (Add (Add (Leaf e1) (Leaf e2)) (Leaf e3)) [] ==
            evalIdExpr (Add (Leaf e1) (Add (Leaf e2) (Leaf e3))) [])
      quickCheck $ counterexample "(e1 * e2) * e3 == e1 * (e2 * e3)" $
        (\e1 e2 e3 ->
            evalIdExpr (Mul (Mul (Leaf e1) (Leaf e2)) (Leaf e3)) [] ==
            evalIdExpr (Mul (Leaf e1) (Mul (Leaf e2) (Leaf e3))) [])
    
      quickCheck $ counterexample "e1 - e2 = -1*(e2 - e1)" $
        (\e1 e2 ->
            evalIdExpr (Sub (Leaf e1) (Leaf e2)) [] ==
            evalIdExpr (Mul (Leaf (-1)) (Sub (Leaf e2) (Leaf e1))) [])
      quickCheck $ counterexample "e1 * (e2 + e3) == e1*e2 + e1*e3" $
        (\e1 e2 e3 -> 
            evalIdExpr (Mul (Leaf e1) (Add (Leaf e2) (Leaf e3))) [] ==
            evalIdExpr (Add (Mul (Leaf e1) (Leaf e2)) 
                         (Mul (Leaf e1) (Leaf e3))) [])
      quickCheck $ counterexample "e1 * (e2 - e3) == e1*e2 - e1*e3" $
        (\e1 e2 e3 -> 
            evalIdExpr (Mul (Leaf e1) (Sub (Leaf e2) (Leaf e3))) [] ==
            evalIdExpr (Sub (Mul (Leaf e1) (Leaf e2))  
                          (Mul (Leaf e1) (Leaf e3))) [])
    

    This code defines the IdExpr data structure and implements the evalIdExpr function according to the specified rules, including handling of unary negation and defaulting to zero when an identifier is not found in the association list. The testEvalIdExpr function includes quickCheck tests for verifying correctness of the implementation.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.