testowanie Równość bez wyraźnego dowodu, że konstruktorzy dane są injective

Question

Czy możliwe jest zdefiniowanie prostego składniowej pojęcia równości (podobny do tego, co GHC może automatycznie czerpać jako przykład Eq dla typu Haskell 98), bez jawnie dowodzi, że każdy konstruktor danych jest iniekcyjny lub robi coś analogicznego, na przykład definiowanie wycofania każdego konstruktora i używanie cong?

Innymi słowy, czy możliwe jest bardziej bezpośrednie wykorzystanie wtrysku konstruktorów danych, zamiast konieczności wprowadzania jednej funkcji pomocniczej na konstruktora?

Następujący używa liczb naturalnych jako przykładu.

module Eq where 

    open import Function 
    open import Relation.Binary 
    open import Relation.Binary.PropositionalEquality 
    open import Relation.Nullary 

    data ℕ : Set where 
     zero : ℕ 
     suc : ℕ → ℕ 

    -- How to eliminate these injectivity proofs? 
    suc-injective : ∀ {n m} → suc n ≡ suc m → n ≡ m 
    suc-injective refl = refl 

    _≟_ : Decidable {A = ℕ} _≡_ 
    zero ≟ suc _ = no (λ()) 
    suc _ ≟ zero = no (λ()) 
    zero ≟ zero = yes refl 
    suc n ≟ suc m with n ≟ m 
    suc n ≟ suc .n | yes refl = yes refl 
    ... | no n≢m = no (n≢m ∘ suc-injective) 

Jeden mógłby zastąpić suc-injective przez cong (λ { zero → zero ; (suc x) → x }), czyli o definiowanie funkcji która odwraca suc, ale nadal wymaga boilerplate jednej funkcji pomocniczej za konstruktora, a takie funkcje są nieco brzydki do zdefiniowania ze względu na konieczność bycia całkowity .

(zwykli ostrzeżenia ponownie. Brakuje coś oczywistego zastosowania.)

Answer 1

Ulf Norell na prelude for Agda zawiera mechanizm automatycznego wyznaczania rozstrzygalne równość dla danego typu danych. Kod jest oparty na mechanizmie odbicia Agdy i automatycznie generuje rozszerzone lambdy dla udowodnienia iniekcyjności konstruktorów. Polecam rzucić okiem na kod, nawet jeśli nie zawsze jest to tak proste, jak mogłoby być.