Agda使用实例参数模拟Acc归纳隐藏证明冗余的相关问题
我正在尝试证明一组互递归引理,但这类引理不满足结构递归要求,因此必须使用Data.Nat.Induction.Acc实现良基归纳,导致代码中近一半内容都是显式书写m ≤ m ⊔ n这类事实的证明。我希望尽可能隐藏这些技术细节,初步判断实例参数是比全量元编程/反射更轻量的实现方案,但目前在该路径上遇到了阻碍。
示例定义
互递归树结构
open import Data.Nat.Base open import Data.Nat.Properties open import Relation.Binary.PropositionalEquality using (_≡_; refl; subst; sym) mutual data U : Set where U-only : U U-with-Vs : (v₁ v₂ : V) → U data V : Set where V-only : V V-with-Us : (u₁ u₂ : U) -> V
转换函数
转换函数输出在直观的尺寸定义下更小,但不满足结构更小的要求:
mutual iso-U : U → V iso-U U-only = V-only iso-U (U-with-Vs v₁ v₂) = V-with-Us (iso-V v₁) (iso-V v₂) iso-V : V → U iso-V V-only = U-only iso-V (V-with-Us u₁ u₂) = U-with-Vs (iso-U u₁) (iso-U u₂)
尺寸度量与尺寸不变性证明
mutual size-U : U → ℕ size-U U-only = zero size-U (U-with-Vs v₁ v₂) = suc (size-V v₁ ⊔ size-V v₂) size-V : V → ℕ size-V V-only = zero size-V (V-with-Us u₁ u₂) = suc (size-U u₁ ⊔ size-U u₂) mutual size-U-iso-V : ∀ v → size-U (iso-V v) ≡ size-V v size-U-iso-V V-only = refl size-U-iso-V (V-with-Us u₁ u₂) rewrite size-V-iso-U u₁ | size-V-iso-U u₂ = refl size-V-iso-U : ∀ u → size-V (iso-U u) ≡ size-U u size-V-iso-U U-only = refl size-V-iso-U (U-with-Vs v₁ v₂) rewrite size-U-iso-V v₁ | size-U-iso-V v₂ = refl
显式证明的良基递归实现
open import Data.Nat.Induction module Explicit where mutual count-U : (u : U) → Acc _<_ (size-U u) → ℕ count-U U-only _ = zero count-U (U-with-Vs v₁ v₂) (acc rec) = let ineq = m≤m⊔n (size-V v₁) (size-V v₂) ineq' = subst (_≤ size-V v₁ ⊔ size-V v₂) (sym (size-U-iso-V v₁)) ineq r₁ = rec _ (s≤s ineq') r₂ = rec _ (s≤s (n≤m⊔n _ _)) in suc (count-U (iso-V v₁) r₁ + count-V v₂ r₂) count-V : (v : V) → Acc _<_ (size-V v) → ℕ count-V V-only _ = zero count-V (V-with-Us u₁ u₂) (acc rec) = let r₁ = rec _ (s≤s (m≤m⊔n _ _)) r₂ = rec _ (s≤s (n≤m⊔n _ _)) in suc (count-U u₁ r₁ + count-U u₂ r₂)
这段代码可以正常通过类型检查,但其中所有的r₁、r₂及支撑它们的证明逻辑和函数的核心业务逻辑完全无关,我希望移除这些冗余内容。
尝试的实例参数实现
module Instance where instance m≤m⊔n' : ∀ {m n} → m ≤ m ⊔ n m≤m⊔n' {m} {n} = m≤m⊔n m n n≤m⊔n' : ∀ {m n} → n ≤ m ⊔ n n≤m⊔n' {m} {n} = n≤m⊔n m n acc-rec : ∀ {a z} → ⦃ Acc _<_ z ⦄ → ⦃ a < z ⦄ → Acc _<_ a acc-rec ⦃ acc rec ⦄ ⦃ a<z ⦄ = rec _ a<z mutual count-U : (u : U) → ⦃ Acc _<_ (size-U u) ⦄ → ℕ count-U U-only = zero count-U (U-with-Vs v₁ v₂) = suc ({! !} + count-V v₂) count-V : (v : V) → ⦃ Acc _<_ (size-V v) ⦄ → ℕ count-V V-only = zero count-V (V-with-Us u₁ u₂) = {! !}
报错信息
Agda无法通过该段代码的检查,表面原因是实例解析过程将count-U的实例参数纳入候选,且无法确定应当使用哪一条关于⊔的引理,报错信息如下:
Failed to solve the following constraints: Resolve instance argument _124 : (v₃ v₄ : V) ⦃ z : Acc _<_ (size-U (U-with-Vs v₃ v₄)) ⦄ → size-V v₄ < _z_122 (v₁ = v₃) (v₂ = v₄) Candidates λ {m} {n} → m≤m⊔n m n : ({m n : ℕ} → m ≤ m ⊔ n) λ {m} {n} → n≤m⊔n m n : ({m n : ℕ} → n ≤ m ⊔ n) Resolve instance argument _123 : (v₃ v₄ : V) ⦃ z : Acc _<_ (size-U (U-with-Vs v₃ v₄)) ⦄ → Acc _<_ (_z_122 (v₁ = v₃) (v₂ = v₄)) Candidates _ : Acc _<_ (size-U (U-with-Vs v₁ v₂)) acc-rec : ({a z : ℕ} ⦃ _ : Acc _<_ z ⦄ ⦃ _ : a < z ⦄ → Acc _<_ a)
即使仅保留一个形状完全匹配的顶层实例:
acc-rec : ∀ {m n} → ⦃ Acc _<_ (suc (m ⊔ n)) ⦄ → Acc _<_ n acc-rec ⦃ acc rec ⦄ = rec _ (s≤s (n≤m⊔n _ _))
Agda仍然会抛出报错。
我多次查阅Agda官方文档中关于实例解析的章节,但仍无法理解上述行为的原因。请问我的实现哪里存在问题?我能否通过实例参数实现隐藏证明冗余的需求?还是需要学习Agda元编程来达成该目标?
问题核心原因
上述实例搜索失败的核心原因有三点:
- 实例搜索不支持自动等式推理:Agda的实例解析器只会严格匹配类型的语法结构,不会自动应用
size-U-iso-V这类等式证明做重写,导致Acc _<_ (size-U (iso-V v₁))和Acc _<_ (size-V v₁)被识别为不同的类型,无法匹配到预定义的实例。 - 实例存在歧义:同时注册
m≤m⊔n'和n≤m⊔n'两个泛化的≤实例,当目标约束为?x < suc (?a ⊔ ?b)时,解析器无法判断应该匹配哪条引理,直接抛出歧义错误。 - 泛化递归实例的终止性风险:泛化定义的
acc-rec实例会让实例搜索可能进入无限递归,Agda的实例终止性检查会拒绝这类定义,即使手动关闭检查也无法解决前两个问题。
可行实现方案
无需使用元编程,两种更轻量的方案即可实现隐藏证明的需求:
方案1:用良基递归封装Acc参数
直接用标准库的wfRec把所有Acc参数和大小证明封装在函数内部,对外暴露的业务接口完全不带证明参数:
open import Induction.WellFounded using (wfRec) open import Data.Nat.Induction using (<-wellFounded) mutual count-U : U → ℕ count-U u = wfRec <-wellFounded (λ u → ℕ) go u where go : (u : U) → (∀ u' → size-U u' < size-U u → ℕ) → ℕ go U-only _ = zero go (U-with-Vs v₁ v₂) rec = let ineq = m≤m⊔n (size-V v₁) (size-V v₂) ineq' = subst (_≤ size-V v₁ ⊔ size-V v₂) (sym (size-U-iso-V v₁)) ineq r₁ = rec (iso-V v₁) (s≤s ineq') r₂ = rec (iso-V v₂) (s≤s (n≤m⊔n (size-V v₁) (size-V v₂))) in suc (r₁ + r₂) count-V : V → ℕ count-V v = wfRec <-wellFounded (λ v → ℕ) go v where go : (v : V) → (∀ v' → size-V v' < size-V v → ℕ) → ℕ go V-only _ = zero go (V-with-Us u₁ u₂) rec = let r₁ = rec (iso-U u₁) (s≤s (m≤m⊔n (size-U u₁) (size-U u₂))) r₂ = rec (iso-U u₂) (s≤s (n≤m⊔n (size-U u₁) (size-U u₂))) in suc (r₁ + r₂)
所有证明逻辑都被隐藏在go函数内部,外部调用count-U/count-V时完全不需要传入任何证明参数,仅需传入业务数据即可。
方案2:使用Sized Types自动校验终止性
如果允许启用语言扩展,开启--sized-types后可以直接给互递归树添加大小标注,Agda会自动完成终止性检查,不需要手动定义尺寸函数、写大小证明或用Acc:
{-# OPTIONS --sized-types #-} open import Size mutual data U (i : Size) : Set where U-only : U i U-with-Vs : ∀ {j : Size< i} → (v₁ v₂ : V j) → U i data V (i : Size) : Set where V-only : V i V-with-Us : ∀ {j : Size< i} → (u₁ u₂ : U j) → V i mutual iso-U : ∀ {i} → U i → V i iso-U U-only = V-only iso-U (U-with-Vs v₁ v₂) = V-with-Us (iso-V v₁) (iso-V v₂) iso-V : ∀ {i} → V i → U i iso-V V-only = U-only iso-V (V-with-Us u₁ u₂) = U-with-Vs (iso-U u₁) (iso-U u₂) mutual count-U : ∀ {i} → U i → ℕ count-U U-only = zero count-U (U-with-Vs v₁ v₂) = suc (count-U (iso-V v₁) + count-V v₂) count-V : ∀ {i} → V i → ℕ count-V V-only = zero count-V (V-with-Us u₁ u₂) = suc (count-U u₁ + count-U u₂)
该方案完全消除了证明冗余,代码仅保留核心业务逻辑。
实例参数方案的局限性
理论上可以通过给不同的≤实例加标记、将等式重写封装为实例的方式实现需求,但实现成本远高于上述两种方案,还会引入额外的类型复杂度,没有必要使用。
内容的提问来源于stack exchange,提问作者0xd34df00d

