Main.hs

import           Control.Monad.Trans.Reader

data Expr a
    = Var Int
    | App (Expr a) (Expr a)
    | Lam (Expr a)
    | Lit a
    | Let String (Expr a) (Expr a)
    deriving (Show)

newtype Env a = Env { vars :: [a] }
  deriving (Show)

newtype Eval a = Eval { runEval :: Reader (Env a) a }

push :: a -> Env a -> Env a
push v (Env vars) = Env (v:vars)

eval :: Show a => Expr a -> Eval a
eval expr = case expr of
    Var i -> Eval $ do
        vars <- vars <$> ask
        pure $ vars !! i
    App f x -> Eval $ do
        x' <- runEval $ eval x
        local (push x') (runEval (eval f))
    Lam f -> eval f
    Lit a -> Eval $ pure a
    Let n v e -> Eval $ do
        v' <- runEval $ eval v
        local (push v') (runEval (eval e))

e = App (App (Lam (Lam (Var 1))) (Lit 5)) (Lit 7)
l = Let "x" (Lit 1) (Let "x" (Lit 2) (Var 0))

main = do
  print $ runReader (runEval (eval l)) (Env [])
  print $ runReader (runEval (eval e)) (Env [])