涉及 nat 添加的依赖类型

Question

我需要定义一个操作的两个版本，定义略有不同。这是一系列涉及Nat指数的作品。

open import Data.Nat

data Hom : ℕ → ℕ → Set where
  id    : (m : ℕ) → Hom m m
  _∘_   : ∀ {m n k} → Hom n k → Hom m n → Hom m k
  p     : (n : ℕ) → Hom (suc n) n

p1 : (m n : ℕ) → Hom (m + n) n
p1 zero n    = id n
p1 (suc m) n = p1 m n ∘ p (m + n)

p2 : (m n : ℕ) → Hom (m + n) n
p2 zero n    = id n
p2 (suc m) n = {!!} -- p n ∘ p2 m (1 + n)

-- Goal: Hom (suc (m + n)) n
-- Have: Hom (m + suc n) n

我想同时定义 p1 和 p2 并且能够互换使用它们。这可行吗？

Answer 1

好吧，你提供的值的类型等于洞的类型，但 Agda 看不到这个事实。更正式地说，这两种类型在命题上是平等的，但在判断上是不平等的。问题是由索引 m + suc n 引起的，由于加法的定义方式，它在命题上但在判断上不等于 suc m + n。解决你的问题的一种方法是手动向 Agda 解释这两种类型是相等的：

open import Data.Nat
open import Data.Nat.Properties
open import Relation.Binary.PropositionalEquality

data Hom : ℕ → ℕ → Set where
  id    : (m : ℕ) → Hom m m
  _∘_   : ∀ {m n k} → Hom n k → Hom m n → Hom m k
  p     : (n : ℕ) → Hom (suc n) n

p1 : (m n : ℕ) → Hom (m + n) n
p1 zero n    = id n
p1 (suc m) n = p1 m n ∘ p (m + n)

p2 : (m n : ℕ) → Hom (m + n) n
p2 zero n    = id n
p2 (suc m) n = subst (λ k → Hom k n) (+-suc m n) (p n ∘ p2 m (suc n))

但是，这种方法并非没有缺点，因为 p2 (suc m) n 现在在判断上不等于您的预期定义，而是上面涉及 subst.

的表达式

这个问题似乎本质上与您正在尝试做的事情有关：IIUC、p1 和 p2 实际上可以证明是相等的，但使用不同的递归结构定义。这很好，但是你的结果类型的索引应该遵循相同的递归结构，即你应该使用不同版本的 + 定义 p2，它以 p2 的适当方式递归：

_+′_ : ℕ → ℕ → ℕ
zero +′ n = n
suc m +′ n = m +′ suc n

p2′ : (m n : ℕ) → Hom (m +′ n) n
p2′ zero n = id n
p2′ (suc m) n = p n ∘ p2′ m (suc n)

然而，这还有另一个缺点，即 p1 和 p2′ 的类型在判断上不再相等（但在命题上仍然相等）。

您可以尝试的另一件事是使用 Agda 的重写规则来满足 _+_ 额外的判断等式，但这很危险，因为它可能会破坏 Agda 的一些理想品质作为逻辑。在这种情况下，我怀疑它没问题，但我必须检查一下。

总而言之，您可以尝试多种方法，但 none 没有缺点。哪个是您的最佳选择取决于您尝试将其用于什么目的。

Answer 2

您可以使用中描述的技巧在 _+_ 上通过直接递归（没有 subst 或重写）来定义 p2。看起来像这样：

record Homable (H : ℕ → ℕ → Set) : Set where
  field
    id-able  : (m : ℕ) → H m m
    _∘-able_ : ∀ {m n k} → H n k → H m n → H m k
    p-able   : (n : ℕ) → H (suc n) n

suc-homable : ∀ {H} → Homable H → Homable (λ m n -> H (suc m) (suc n))
suc-homable homable = record
  { id-able  = λ m → id-able (suc m)
  ; _∘-able_ = _∘-able_
  ; p-able   = λ m → p-able (suc m)
  } where open Homable homable

p2-go : ∀ {H} → Homable H → (m : ℕ) → H m 0
p2-go homable  zero   = id-able 0 where
  open Homable homable
p2-go homable (suc m) = p-able 0 ∘-able p2-go (suc-homable homable) m where
  open Homable homable

plus-homable-hom : ∀ k → Homable (λ m n → Hom (m + k) (n + k))
plus-homable-hom k = record
  { id-able  = λ n → id (n + k)
  ; _∘-able_ = _∘_
  ; p-able   = λ n → p (n + k)
  }

p2 : (m n : ℕ) → Hom (m + n) n
p2 m n = p2-go (plus-homable-hom n) m

成本是您需要维护那些 Homable 记录，这有点乏味，但根据我的经验，证明以这种方式定义的函数的事情比证明根据 subst 定义的函数更简单或超过 _+′_（当然，除非你永远不想将 _+′_ 强制为 _+_）。

涉及 nat 添加的依赖类型

Dependent type involving nat addition

agda

dependent-type