-- definition of expression data Exp = Var String -- variable | App Exp Exp -- application | Lam String Exp -- abstraction | N Int -- integer | Op String Exp Exp -- operator (a special form of function that takes two params) deriving (Eq, Show) -- value definition data Val = VN Int -- integer | VLam String Exp [(String, Val)] -- abstraction deriving (Eq, Show) -- top level evaluation eval :: Exp -> Maybe Val eval exp = ev [] exp -- utility to deal with Maybe bind :: Maybe a -> (a -> Maybe b) -> Maybe b bind Nothing f = Nothing bind (Just v) f = f v -- inner level eval ev :: [(String, Val)] -> Exp -> Maybe Val -- variables ev [] (Var x) = Nothing ev ((x',v):env) (Var x) = if x == x' then Just v else ev env (Var x) -- number ev env (N x) = Just (VN x) -- abstraction ev env (Lam x body) = Just (VLam x body env) -- operator ev env (Op op x y) = bind (ev env x) $ \vx -> bind (ev env y) $ \vy -> applyOp op vx vy -- application ev env (App f arg) = bind (ev env f) $ \vf -> bind (ev env arg) $ \varg -> applyLam vf varg -- operation application applyOp :: String -> Val -> Val -> Maybe Val applyOp "+" (VN x) (VN y) = Just (VN (x + y)) applyOp "-" (VN x) (VN y) = Just (VN (x - y)) -- function application applyLam :: Val -> Val -> Maybe Val applyLam (VLam x body env) arg = ev ((x,arg):env) body -- introduce a symbol for application infixl 1 |> (|>) = App -- test programs in our own language test1 = Op "-" (N 3) (N 4) test2 = (Lam "x" (Lam "y" (Op "-" (Var "y") (Var "x")))) |> N 3 |> N 4 test3 = (Lam "x" (Op "+" (N 3) (Var "x"))) |> test1 main = do print $ eval test1 print $ eval test2 print $ eval test3