-- eval.hs
--
-- Much of the code is from one of Milewski's tutorials.
-- https://www.fpcomplete.com/school/starting-with-haskell/basics-of-haskell/9_Evaluator
--
-- Goal is to learn how to use the Data.Map object to map symbol
-- names to values.   For this example, the symbols are variables 
-- and they are being assigned integer values.
--
-- usage example:
--      ghci eval.hs
--      Prelude> :l eval.hs
--      *Main> print symTab
--      *Main> print tree1
--      *Main> print tree2
--      *Main> evaluate tree1 symTab
--      *Main> evaluate tree2 symTab
--      *Main> let (_,symTab2) = evaluate tree1 symTab
--      *Main> evaluate tree2 symTab2
--
-- MMS, 4/1/15

import qualified Data.Map as M

type SymTab = M.Map String Double

-- Express tree data structure
data Operator = Plus | Minus | Times | Div
  deriving Show

data Tree = BinOpNode Operator Tree Tree
          | AssignNode String Tree
          | NumNode Double
          | VarNode String
  deriving Show

-- Function that looks up variable values in the symbol table.
lookUp :: String -> SymTab -> (Double, SymTab)
lookUp str symTab = 
    case M.lookup str symTab of
      Just v -> (v, symTab)
      Nothing -> error $ "Undefined variable " ++ str

-- Add a variable,value binding to the symbol table.
addSymbol :: String -> Double -> SymTab -> SymTab
addSymbol str val symTab = 
    M.insert str val symTab

-- A function that evaluates an expression tree given a
-- symbol table and then returns the value of the expression
-- tree along with a possibly modified symbol table.
evaluate :: Tree -> SymTab -> (Double, SymTab)

evaluate (BinOpNode op left right) symTab = 
    let (lft, symTab')  = evaluate left symTab
        (rgt, symTab'') = evaluate right symTab'
    in
        case op of
          Plus  -> (lft + rgt, symTab'')
          Minus -> (lft - rgt, symTab'')
          Times -> (lft * rgt, symTab'')
          Div   -> (lft / rgt, symTab'')

evaluate (VarNode str) symTab = lookUp str symTab

evaluate (AssignNode str tree) symTab = 
    let (v, symTab')  = evaluate tree symTab
        symTab'' = addSymbol str v symTab'
    in (v, symTab'')

evaluate (NumNode v) symTab = (v, symTab)


----------------------------------------------------------
-- An initial symbol table.
symTab = M.fromList [("pi", pi), ("e", exp 1)]

-- Some example expression trees.
tree1 = AssignNode "a" (NumNode 4.2)
tree2 = BinOpNode Plus (VarNode "a") 
                       (BinOpNode Times (VarNode "pi") (NumNode 1))