-- Lambda calculus interpreter example.

import qualified Data.Map.Lazy as Map

data Val = Num Integer | Fun (Val -> Val) | Wrong
data Term = Cons Integer | Var String | Lam String Term | App Term Term | Add Term Term
type Env = Map.Map String Val

add :: Val -> Val -> Val
add (Num x) (Num y) = Num (x+y)
add _ _ = Wrong

apply :: Val -> Val -> Val
apply (Fun f) v = f v
apply _ _ = Wrong

instance Show Val where
  show (Num x) = show x
  show (Fun f) = "function"
  show Wrong = "Wrong"

interp :: Term -> Env -> Val
interp (Cons x) e = Num x
interp (Var s) e = Map.findWithDefault Wrong s e -- Equivalent to:
-- interp (Var s) e = maybe Wrong id (Map.lookup s e)
interp (Lam s t) e = Fun (\v -> interp t (Map.insert s v e))
interp (App f t) e = apply (interp f e) (interp t e)
interp (Add a b) e = add (interp a e) (interp b e)

expr = App (Lam "x" (Add (Var "x") (Var "x"))) (Add (Cons 10) (Cons 11))
res = interp expr Map.empty

main = putStrLn (show res)