功能推理

Question

一些导入和定义。

open import Level hiding (suc)
open import Relation.Binary.PropositionalEquality
open import Data.Nat
open import Algebra
open import Data.Nat.Properties
open CommutativeSemiring commutativeSemiring hiding (_+_; _*_; sym)

data Even : ℕ -> Set where
  ezero : Even 0
  esuc  : {n : ℕ} -> Even n -> Even (suc (suc n))

_^2 : ℕ -> ℕ
n ^2 = n * n

unEsuc : {n : ℕ} -> Even (suc (suc n)) -> Even n
unEsuc (esuc e) = e

remove-*2 : (n : ℕ) -> {m : ℕ} -> Even (n + n + m) -> Even m
remove-*2  0          e = e
remove-*2 (suc n) {m} e
    with subst (λ n' -> Even (suc (n' + m))) (+-comm n (suc n)) e
... | esuc e1 = remove-*2 n e1

现在我想用一种很好的方式来证明{n : ℕ} -> Even (n ^2) -> Even n，类似于≡推理。我已经结束了

infix 4 ∈_

data ∈Wrap {α : Level} {A : Set α} : A -> Set α where
  ∈_ : (x : A) -> ∈Wrap x

infix 3 #⟨_⟩_
infixl 2 _$⟨_⟩'_ _$⟨_⟩_

#⟨_⟩_ : {α : Level} {A : Set α} -> A -> ∈Wrap A -> A
#⟨ x ⟩ _ = x

_$⟨_⟩'_ : {α β : Level} {A : Set α} {B : A -> Set β}
        -> (x : A) -> (f : (x : A) -> B x) -> ∈Wrap (B x) -> B x
x $⟨ f ⟩' _ = f x

_$⟨_⟩_ : {α β : Level} {A : Set α} {B : Set β}
       -> A -> (A -> B) -> ∈Wrap B -> B
_$⟨_⟩_ = _$⟨_⟩'_

even-sqrt : {n : ℕ} -> Even (n ^2) -> Even n
even-sqrt {0}            ezero   = ezero
even-sqrt {1}            ()
even-sqrt {suc (suc n)} (esuc e) =
    #⟨ e ⟩ ∈
  Even (n + suc (suc (n + n * suc (suc n))))
    $⟨ subst Even (+-comm n (suc (suc (n + n * suc (suc n))))) ⟩ ∈
  Even (suc (suc (n + n * suc (suc n) + n)))
    $⟨ unEsuc ⟩ ∈
  Even (n + n * suc (suc n) + n)
    $⟨ subst (λ n' -> Even (n' + n)) (+-comm n (n * suc (suc n))) ⟩ ∈
  Even (n * suc (suc n) + n + n)
    $⟨ subst (λ n' -> Even (n' + n + n)) (*-comm n (suc (suc n))) ⟩ ∈
  Even (n + (n + n * n) + n + n)
    $⟨ subst (λ n' -> Even (n' + n + n)) (sym (+-assoc n n (n * n))) ⟩ ∈
  Even (n + n + n * n + n + n)
    $⟨ subst Even (+-assoc (n + n + n * n) n n) ⟩ ∈
  Even (n + n + n * n + (n + n))
    $⟨ subst Even (+-assoc (n + n) (n * n) (n + n)) ⟩ ∈
  Even (n + n + (n * n + (n + n)))
    $⟨ remove-*2 n ⟩ ∈
  Even (n * n + (n + n))
    $⟨ subst Even (+-comm (n * n) (n + n)) ⟩ ∈
  Even (n + n + n * n)
    $⟨ remove-*2 n ⟩ ∈
  Even (n * n)
    $⟨ even-sqrt ⟩ ∈
  Even n
    $⟨ esuc ⟩ ∈
  Even (suc (suc n))

是否有任何这样的标准推理？

Answer 1

我不知道在Agda的标准库中有什么东西，但是它提供了您在Function模块中几乎需要的东西。没有∈Wrap你也能做到。让我提出一个小的语法糖：

infix 4 _⟧
infixr 3 _─_⟶_
infix 2 _⟦_

_⟧ : ∀ {α} → (A : Set α) → A → A
_⟧ _ = id

_⟦_ : ∀ {α β} {A : Set α} → (a : A) → {B : A → Set β} → ((x : A) → B x) → B a
a ⟦ f = f a

_─_⟶_ : ∀ {α β γ} (A : Set α) → {B : A → Set β} → (f : (a : A) → B a) →
        {C : {a : A} → (b : B a) → Set γ} → (∀ {a} → (b : B a) → C b) →
        (a : A) → C (f a)
A ─ f ⟶ g = g ∘ f

然后你可以把你的证明写成：

...
even-sqrt {suc (suc n)} (esuc e) = e ⟦
  Even (n + suc (suc (n + n * suc (suc n))))
    ─ subst Even (+-comm n (suc (suc (n + n * suc (suc n))))) ⟶
...
    ─ remove-*2 n ⟶
  Even (n * n)
    ─ even-sqrt2 {n} ⟶
  Even n
    ─ esuc ⟶
  Even (suc (suc n)) ⟧

这一变式的主要好处是：

• 没有包装器类型。你只是在处理函数。
• 筑巢的方法是正确的。使用问题中提出的方法，您不能用_$⟨_⟩_在末尾细化一个洞，所以总是在最后一个洞之外编辑代码。

最好在标准库中有这个功能，目前的方法是在github上打开一个问题或请求。你能做到吗？