type unop =
  | Negate
;;

type binop =
  | Plus
  | Minus
  | Times
  | Equals
  | LessThan
;;

type expr =
  | Var of varid                         (* variables *)
  | Num of int                           (* integers *)
  | Bool of bool                         (* booleans *)
  | Unop of unop * expr                  (* unary operators *)
  | Binop of binop * expr * expr         (* binary operators *)
  | Conditional of expr * expr * expr    (* if then else *)
  | Fun of varid * expr                  (* function definitions *)
  | Let of varid * expr * expr           (* local naming *)
  | Letrec of varid * expr * expr        (* recursive local naming *)
  | Raise                                (* exceptions *)
  | Unassigned                           (* (temporarily) unassigned *)
  | App of expr * expr                   (* function applications *)
 and varid = string ;;

module SS = Set.Make (struct
                       type t = varid
                       let compare = String.compare
                     end ) ;;

type varidset = SS.t ;;

let same_vars = SS.equal;;

let vars_of_list = SS.of_list ;;

let rec free_vars (exp : expr) : varidset =
  match exp with
  | Num _ | Bool _ | Raise | Unassigned -> SS.empty
  | Var v -> SS.singleton v
  | Unop (_, e) -> free_vars e
  | Binop (_, e1, e2) | App (e1, e2) ->
      SS.union (free_vars e1) (free_vars e2)
  | Conditional (e1, e2, e3) ->
      let u1 = SS.union (free_vars e1) (free_vars e2) in
      SS.union u1 (free_vars e3)
  | Fun (v, e) -> SS.remove v (free_vars e)
  | Let (v, e1, e2) ->
      let u1 = SS.union (free_vars e2) (free_vars e1) in
      SS.remove v u1
  | Letrec (v, e1, e2) -> SS.empty ;;

assert (free_vars (Num(3)) = SS.empty) ;;
assert (not (SS.equal (free_vars (Fun(x, y))) (free_vars (Fun(x, x))))) ;;