You need to enable JavaScript to run this app. Agda使用实例参数模拟Acc归纳隐藏证明冗余的相关问题
优惠活动
大模型
产品
解决方案
定价
更多

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元编程来达成该目标?


解答

问题核心原因

上述实例搜索失败的核心原因有三点:

  1. 实例搜索不支持自动等式推理:Agda的实例解析器只会严格匹配类型的语法结构,不会自动应用size-U-iso-V这类等式证明做重写,导致Acc _<_ (size-U (iso-V v₁))和Acc _<_ (size-V v₁)被识别为不同的类型,无法匹配到预定义的实例。
  2. 实例存在歧义:同时注册m≤m⊔n'和n≤m⊔n'两个泛化的≤实例,当目标约束为?x < suc (?a ⊔ ?b)时,解析器无法判断应该匹配哪条引理,直接抛出歧义错误。
  3. 泛化递归实例的终止性风险:泛化定义的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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.10.09 18:48:03