[Agda] constructor injectiveness
Ulf Norell
ulf.norell at gmail.com
Fri May 26 16:40:29 CEST 2017
On Fri, May 26, 2017 at 3:23 PM, Andreas Abel <abela at chalmers.se> wrote:
> > Is there possible a simpler expression for _≟d_ ?
>
> I don't think so.
>
> > Probably injectiveness of constructors like `con' needs to be somehow in
> > Standard, similarly as PE.cong is in standard (?)
>
> These injectivity proofs are necessary boilerplate, but could maybe be
> programmed generically using reflection.
See for instance
https://github.com/UlfNorell/agda-prelude/blob/master/src/Tactic/Deriving/Eq.agda
/ Ulf
> On 26.05.2017 13:49, Sergei Meshveliani wrote:
>
>> People,
>>
>> I need to program _≟d_ below,
>> and do this by introducing con-injective and +injective.
>> Is there possible a simpler expression for _≟d_ ?
>> Probably injectiveness of constructors like `con' needs to be somehow in
>> Standard, similarly as PE.cong is in standard (?)
>>
>> Thanks,
>>
>> ------
>> Sergei
>>
>>
>> -----------------------------------------------------------------------
>> open import Function using (_∘_; case_of_)
>> open import Relation.Nullary using (yes; no)
>> open import Relation.Binary using () renaming (Decidable to Decidable₂)
>> open import Relation.Binary.PropositionalEquality as PE using (_≡_)
>> open import Data.Product using (_×_; _,_; proj₁; proj₂)
>> open import Data.Nat using (ℕ; _≟_)
>>
>> data D : Set where con : ℕ → D
>> _+_ : D → D → D
>>
>> con-injective : ∀ {e e'} → con e ≡ con e' → e ≡ e'
>> con-injective PE.refl = PE.refl
>>
>> +injective : ∀ {x y z u} → (x + y) ≡ (z + u) → x ≡ z × y ≡ u
>> +injective {x} {y} {.x} {.y} PE.refl = (PE.refl , PE.refl)
>>
>> _≟d_ : Decidable₂ (_≡_ {A = D})
>>
>> (con _) ≟d (_ + _) = no λ()
>> (_ + _) ≟d (con _) = no λ()
>> (con i) ≟d (con j) = case i ≟ j
>> of \
>> { (yes i≡j) → yes (PE.cong con i≡j)
>> ; (no i≢j) → no (i≢j ∘ con-injective)
>> }
>> (x + y) ≟d (z + u) =
>> case (x ≟d z , y ≟d u)
>> of \
>> { (yes x≡z , yes y≡u) → yes (PE.cong₂ _+_ x≡z y≡u)
>> ; (no x≢z , _ ) → no (x≢z ∘ proj₁ ∘ +injective)
>> ; (_ , no y≢u ) → no (y≢u ∘ proj₂ ∘ +injective)
>> }
>>
>>
>> _______________________________________________
>> Agda mailing list
>> Agda at lists.chalmers.se
>> https://lists.chalmers.se/mailman/listinfo/agda
>>
>>
>
> --
> Andreas Abel <>< Du bist der geliebte Mensch.
>
> Department of Computer Science and Engineering
> Chalmers and Gothenburg University, Sweden
>
> andreas.abel at gu.se
> http://www.cse.chalmers.se/~abela/
>
> _______________________________________________
> Agda mailing list
> Agda at lists.chalmers.se
> https://lists.chalmers.se/mailman/listinfo/agda
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.chalmers.se/pipermail/agda/attachments/20170526/97621b16/attachment-0001.html>
More information about the Agda
mailing list