type expr = Int of int | Add of expr * expr | Mul of expr * expr
          | Lam of (expr -> expr) | App of expr * expr

let rec eval : expr -> int = function
    | Int x -> x
    | Add (x,y) -> ((eval x) + (eval y))
    | Mul (x,y) -> ((eval x) * (eval y))
    | Lam _ -> failwith "that is not an integer"
    | App (f,x) -> (match f with
        | Lam g -> eval (g x)
        | _ -> failwith "trying to apply a non-function" )
;;

let test1 = Add( Int 1, Mul(Int 2, Int 3)) (* 1 + (2*3) *)
let test2 = App ((Lam (fun x -> x)),test1)
let test3 = Lam (fun x -> Add(x, Int 1))
let test4 = App (test3, test1)
let test5 = App (Int 1, Int 2)

let res1 = eval test1
let res2 = eval test2
(* let res3 = eval test3 *)
let res4 = eval test4
;;

let getint = function
    | Int x -> x
    | Add _ | Mul _ | App _ | Lam _ -> failwith "hey, I didn't get an integer?!?!"

let getfun = function
    | Lam f -> f
    | Add _ | Mul _ | App _ | Int _ -> failwith "applying a non-function"

let rec eval2 : expr -> expr = function
    | Int x -> Int x
    | Add (x,y) -> 
        let xx = getint (eval2 x) and yy = getint (eval2 y) in Int (xx + yy)
    | Mul (x,y) ->
        let xx = getint (eval2 x) and yy = getint (eval2 y) in Int (xx * yy)
    | App (f, x) ->
        let g = getfun (eval2 f) and y = eval2 x in eval2 (g y)
    | Lam f -> Lam f

let res2 = eval2 test1
let res4 = eval2 test4
;;