evaluators

evaluators.hs

-- named & hashmap; O(log n) update/access
data Exp
  = Lam Int Expr
  | Var Int
  | App Exp Exp

eval :: Map Int Expr -> Expr -> Expr
eval env = \case
  App (Lam i b) e ->
    let !e' = eval e
     in eval (M.insert i e') b
  Var i -> M.lookup i env

-- deBruijn & stack; O(1) update, O(n) access
data Exp
  = Lam Expr
  | Var Int
  | App Exp Exp

eval :: [Expr] -> Expr -> Expr
eval stack = \case
  App (Lam b) e = eval (b:stack) e
  Var i -> npop stack i

-- deBruijn & stack mutable; O(1) update/access
data Exp
  = Lam Expr
  | Var Int
  | App Exp Exp

eval :: StackIO Expr -> Expr -> IO Expr
eval stack = \case
  App (Lam b) e = do pushIO stack e; eval stack e
  Var i -> npopIO stack i

-- tuples; O(wat) update/access
data Exp env t where
  B :: Bool -> Exp env Bool
  V :: Var env t -> Exp env t
  L :: Exp (a, env) b -> Exp env (a -> b)
  A :: Exp env (a -> b) -> Exp env a -> Exp env b

data Var env t where
  VZ :: Var (t, env) t
  VS :: Var env t -> Var (a, env) t

eval :: env -> Exp env t -> t
eval env (V v) = lookp v env
eval _nv (B b) = b
eval env (L e) = \x -> eval (x, env) e
eval env (A e1 e2) = (eval env e1) (eval env e2)

lookp :: Var env t -> env -> t
lookp VZ (x, _) = x
lookp (VS v) (_ , env) = lookp v env