subst :: forall m a b . MonadSubst a b m => AST a -> AST b -> forall c . AST c -> c -> m c
subst = go
  where
    go :: AST a -> AST b -> AST c -> c -> m c
    go VarA VarA VarA v                  = lookupSubst VarA v VarA (return v)

    go VarA ExpA ExpA e@(VarE v)         = lookupSubst VarA v ExpA (return e)

    go VarA w ExpA (LetE v tau occ e1 e2) = do  e1' <- go VarA w ExpA e1
                                                bind VarA w v $ \v'-> do
                                                LetE v' tau occ  e1' <$> go VarA w ExpA e2

    go VarA w ExpA (LamE vtaus e)         = do  let (vs, taus) = unzip vtaus
                                                binds VarA w vs $ \vs' -> do
                                                LamE (vs' `zip` taus) <$> go VarA w ExpA e

    go VarA w ExpA (BindE v tau p1 p2)    = do  p1' <- go VarA w ExpA p1
                                                bind VarA w v $ \v' -> do
                                                BindE v' tau p1' <$> go VarA w ExpA p2

    go VarA w ExpA (ForE floop loopvs p)  = do  es' <- traverse (go VarA w ExpA) es
                                                binds VarA w vs $ \vs' -> do
                                                ForE floop (vs' `zip` es') <$> go VarA w ExpA p
      where
        (vs, es) = unzip loopvs

    go w1 w2 w a = traverseFam (go w1 w2) w a

-- The StateL monad
subst :: forall m a b . MonadSubst a b m => AST a -> AST b -> forall c . AST c -> c -> m c
subst = go
  where
    go :: AST a -> AST b -> AST c -> c -> m c
    go VarA VarA VarA v                  = lookupSubst VarA v VarA (return v)

    go VarA ExpA ExpA e@(VarE v)         = lookupSubst VarA v ExpA (return e)

    go VarA w ExpA (LetE v tau occ e1 e2) = do  e1' <- go VarA w ExpA e1
                                                bind VarA w v $ \v'-> do
                                                LetE v' tau occ  e1' <$> go VarA w ExpA e2

    go VarA w ExpA (LamE vtaus e)         = do  let (vs, taus) = unzip vtaus
                                                binds VarA w vs $ \vs' -> do
                                                LamE (vs' `zip` taus) <$> go VarA w ExpA e

    go VarA w ExpA (BindE v tau p1 p2)    = do  p1' <- go VarA w ExpA p1
                                                bind VarA w v $ \v' -> do
                                                BindE v' tau p1' <$> go VarA w ExpA p2

    go VarA w ExpA (ForE floop loopvs p)  = do  es' <- traverse (go VarA w ExpA) es
                                                binds VarA w vs $ \vs' -> do
                                                ForE floop (vs' `zip` es') <$> go VarA w ExpA p
      where
        (vs, es) = unzip loopvs

    go w1 w2 w a = traverseFam (go w1 w2) w a

-- The StateL monad
subst = go
  where
    go :: AST a -> AST b -> AST c -> c -> m c
    go VarA VarA VarA v                  = lookupSubst VarA v VarA (return v)

    go VarA ExpA ExpA e@(VarE v)         = lookupSubst VarA v ExpA (return e)

    go VarA w ExpA (LetE v tau occ e1 e2) = do  e1' <- go VarA w ExpA e1
                                                bind VarA w v $ \v'-> do
                                                LetE v' tau occ  e1' <$> go VarA w ExpA e2

    go VarA w ExpA (LamE vtaus e)         = do  let (vs, taus) = unzip vtaus
                                                binds VarA w vs $ \vs' -> do
                                                LamE (vs' `zip` taus) <$> go VarA w ExpA e

    go VarA w ExpA (BindE v tau p1 p2)    = do  p1' <- go VarA w ExpA p1
                                                bind VarA w v $ \v' -> do
                                                BindE v' tau p1' <$> go VarA w ExpA p2

    go VarA w ExpA (ForE floop loopvs p)  = do  es' <- traverse (go VarA w ExpA) es
                                                binds VarA w vs $ \vs' -> do
                                                ForE floop (vs' `zip` es') <$> go VarA w ExpA p
      where
        (vs, es) = unzip loopvs

    go w1 w2 w a = traverseFam (go w1 w2) w a

-- The StateL monad