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" $ 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)

  -- id unit tests
  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)

  -- property-based tests
  -- id lookup
  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)
  
  -- property-based tests
  -- commutativity
  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)) [])
  -- associativity
  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))) [])

  -- subtraction
  quickCheck $ 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" $
    (\ 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))) [])