在应用程序中使用 subst 会搞砸结果的类型

Question

我有以下类型的定义：

insert : ∀ {n} → (i : Fin (suc n)) → ∀ t → Env n → Env (suc n)
weaken : ∀ {t t₀ n} {Γ : Env n} → (i : Fin (suc n)) → (e : Γ ⊢ t₀) → (insert i t Γ) ⊢ t₀

给定两个环境Γ : Env n和Γ′ : Env n′，以及指向第二个i : Fin (suc n)中的位置的指针，我想削弱e : (Γ′ ++ Γ) ⊢ t₀。

理论上，使用类似

的东西应该很容易

let i′ = raise n′ i
weaken {t} i′ e : insert i′ t (Γ′ ++ Γ) ⊢ t₀

然而，实际上它并没有那么好地工作，因为类型检查器不相信 raise n′ i 具有类型 Fin (suc _)（weaken 要求）：

(n′ + suc n) != (suc (_n_550 i e)) of type ℕ when checking that the expression i′ has type Fin (suc (_n_550 i e))

我的问题是，我可以使用 +-suc : ∀ n′ n → n′ + suc n ≡ suc (n′ + n) 之类的东西来 substitute i′ 的类型，但是 weaken i′ e 的结果类型将没有表格 insert i′ t (Γ′ ++ Γ) ⊢ t₀.

Answer 1

Given two environments Γ : Env n and Γ′ : Env n′

这些是上下文。

应该可以将 insert 的类型更改为

data Bound : ℕ -> Set where
  zero : ∀ {n} -> Bound n
  suc  : ∀ {n} -> Bound n -> Bound (suc n)

insert : ∀ {n} → (i : Bound n) → ∀ t → Env n → Env (suc n)

不改变函数体。

你可以写一个 raise 的版本，在 suc 下引发：

raise′ : ∀ {m} n → Fin (suc m) → Fin (suc (n + m))
raise′ zero    i = i
raise′ (suc n) i = suc (raise′ n i)

但实际的解决方案是使用以下任一函数重命名术语：

Ren : Con -> Con -> Set
Ren Γ Δ = ∀ {σ} -> σ ∈ Γ -> σ ∈ Δ

keepʳ : ∀ {Γ Δ σ} -> Ren Γ Δ -> Ren (Γ ▻ σ) (Δ ▻ σ)
keepʳ r  vz    = vz
keepʳ r (vs v) = vs (r v)

ren : ∀ {Γ Δ σ} -> Ren Γ Δ -> Γ ⊢ σ -> Δ ⊢ σ
ren r (var v) = var (r v)
ren r (ƛ b  ) = ƛ (ren (keepʳ r) b)
ren r (f · x) = ren r f · ren r x

或order preserving embeddings.

在应用程序中使用 subst 会搞砸结果的类型

Using subst in an application would screw up type of the result

agda