Lambda calculus evaluator extended with some primitive values and operations. Recursion is achieved in the language using the y combinator.

lambda.hs

import Debug.Trace
type Var = String
type Env = [(Var, Expr)]
data Expr = Var Var
          | BoolConst Bool
          | IntConst Int
          | Mult Expr Expr
          | Minus Expr Expr
          | Equality Expr Expr
          | Cond Expr Expr Expr
          | Lambda Var Expr
          | Apply Expr Expr
          | Closure Env Var Expr
            deriving(Show)

varLookup ((v,e):env) var = if var == v then
                              e
                            else (varLookup env var)

extend env v e = ((v,e):env)

eval env (Var v) = varLookup env v
eval env (IntConst i) = IntConst i
eval env (BoolConst b) = BoolConst b
eval env (Mult e0 e1) = IntConst (i0 * i1)
  where (IntConst i0, IntConst i1) = (eval env e0, eval env e1)
eval env (Minus e0 e1) = IntConst (i0 - i1)
  where (IntConst i0, IntConst i1) = (eval env e0, eval env e1)
eval env (Equality e0 e1) = BoolConst (i0 == i1)
  where (IntConst i0, IntConst i1) = (eval env e0, eval env e1)
eval env (Lambda v e) = Closure env v e
eval env (Apply e0 e1) = apply (eval env e0) (eval env e1)
eval env (Cond e0 e1 e2) =
  if b then
    eval env e1
  else
    eval env e2
  where BoolConst b = eval env e0

apply (Closure env v e0) e1 = eval (extend env v e1) e0

-- y combinator
yComb = (Lambda "t" (Apply
                     (Lambda "x"
                      (Apply (Var "t") (Apply (Var "x") (Var "x"))))
                     (Lambda "x"
                      (Apply (Var "t") (Apply (Var "x") (Var "x"))))))

-- factorial
factBody = (Cond (Equality (Var "n") (IntConst 1))
            (IntConst 1)
            (Mult (Var "n") (Apply (Var "f") (Minus (Var "n") (IntConst 1)))))
fact = (Lambda "f" (Lambda "n" (factBody)))

fact10 = eval [] (Apply (Apply yComb fact) (IntConst 10))