agda - 涉及 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

您可以使用描述的技巧在 _+_ 上通过直接递归(无 subst 或重写)定义 p2 here .看起来像这样:

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 定义的函数更简单 或 _+′_(当然，除非你不想将 _+′_ 强制转换为 _+_) .