module Interpreter where
import Control.Exception
import Debug.Trace
import Data.List
import Text.Read
import Data.Set (toList, fromList, difference)

--interpret(x) = x
--interpret(λx.E1) = let f = interpret(E1)
-- in case f of
-- λx.E3 -> interpret(E3[a/x])
-- - -> λx.E1
--interpret(E1 E2) = let f = interpret(E1)
-- a = interpret(E2)
-- in case f of
-- λx.E3 -> interpret(E3[a/x])
-- - -> f a

---- Data types ----
type Name = String

data Expr =
  Var Name
  | Lambda Name Expr
  | App Expr Expr
  deriving
    (Eq,Show)

---- Functions ----

--functions to help with debugging
toStrang (Var a) = "(Var " ++ a ++ ")"
toStrang (App a b) = "(App " ++ (toStrang a) ++ " " ++ (toStrang b) ++ ")"
toStrang (Lambda a b) = "(Lambda " ++ a ++ (toStrang b) ++ ")"
subst_print x m e1 = "replacing " ++ x ++ " with " ++ (toStrang m) ++ " in all instances of:     " ++ (toStrang e1)

freeVars::Expr -> [Name]
---- YOUR CODE HERE
freeVars (Var e1) = [e1]
freeVars (App e1 e2) = toList $ fromList ((freeVars e1) ++ (freeVars e2))
freeVars (Lambda binds e1) = filter (/= binds) (freeVars e1)


freshVars::[Expr]->[Name]
---- YOUR CODE HERE
-- List of all possible variable names before parsing expression
all_numbers = 1 : map (+1) all_numbers
str_numbers = map (++ "_") (map show all_numbers)
-- get a list of all of our free vars
freeVarslst exp = toList $ fromList (foldl (++) [] (map freeVars exp))
-- now remove all free vars from our list of vars
freshVars exp = filter  (\x -> notElem x (freeVarslst exp)) str_numbers



subst::(Name,Expr) -> Expr -> Expr
-- ---- YOUR CODE HERE
-- returns E[e/x]
-- replacing all instances of x in (Var y) with m
subst (x, m) (Var y) =
    if (x == y) then m
    else (Var y)

subst (x, m) (App e1 e2) = App (subst (x,m) e1) (subst (x,m) e2)

subst (x, m) (Lambda y e1) =
    if (x == y) then (Lambda y e1)
    else
        let zip = head (freshVars [e1, m, Var x])
        in (Lambda zip (subst (x,m) (subst (y, Var zip) e1)))


appNF_OneStep::Expr -> Maybe Expr
---- YOUR CODE HERE

appNF_OneStep (Var x) = --(traceShow (toStrang (Var x)))
    Nothing
appNF_OneStep (Lambda x y) = --(traceShow (toStrang (Lambda x y)))
    let z = appNF_OneStep y in
        case z of
            Just z -> Just (Lambda x z)
            Nothing -> Nothing

appNF_OneStep (App e1 e2) =  --(traceShow (toStrang (App e1 e2)))
    let
      f = appNF_OneStep e1
      a = appNF_OneStep e2
      c = trySubst e1 e2
    in
        case f of
            Just f -> Just (App f e2)
            Nothing -> case a of
                       Just a -> Just (App e1 a)
                       Nothing -> case c of
                                  Just c -> Just c
                                  Nothing -> Nothing


trySubst:: Expr -> Expr -> Maybe Expr
trySubst e1 e2 =
    case e1 of
        Lambda x m -> Just (subst (x, e2) m)
        Var _ -> Nothing
        App _ _ -> Nothing


appNF_n::Int -> Expr -> Expr
---- YOUR CODE HERE
appNF_n n e1 =
    if (n <= 0) then e1
    else let e2 = (appNF_OneStep e1) in
        case e2 of
            Just e2 -> appNF_n (subtract 1 n) e2
            Nothing -> e1