[Agda] divmod-unique of Agda prelude
Sergei Meshveliani
mechvel at botik.ru
Fri Jul 28 12:13:47 CEST 2017
People,
I try to accompany divmod-unique of Agda prelude with a certain
congruence:
DivMod-cong : ∀ {a a' b b'} → a ≡ a' → b ≡ b' → (d : DivMod a b ) →
(d' : DivMod a' b') →
quot d ≡ quot d' × rem d ≡ rem d'
1) Has Agda prelude something close to it?
2) I wonder: how to fix the below implementation?
Agda reports that eq is not of the declared type
(and I think that it is).
Regards,
------
Sergei
--------------------------------------------------------------------
open import Function using (_$_)
open import Relation.Binary.PropositionalEquality as PE using
(_≡_; _≢_)
open import Data.Product using (_×_)
open import Data.Nat using (ℕ; suc; _+_ ; _*_)
open PE.≡-Reasoning renaming (_≡⟨_⟩_ to _≡[_]_; begin_ to ≡begin_;
_∎ to _≡end)
open import Prelude using (NonZero) renaming (_<_ to _<'_)
open import Numeric.Nat.DivMod using (DivMod; quot; rem; rem-less;
quot-rem-sound; divmod-unique)
open DivMod
DivMod-cong : ∀ {a a' b b'} → a ≡ a' → b ≡ b' → (d : DivMod a b ) →
(d' : DivMod a' b') →
quot d ≡ quot d' × rem d ≡ rem d'
DivMod-cong {a} {a'} {b} {b'} a≡a' b≡b' d d' = eq
where
q' = quot d'; r' = rem d'
r'<'b' = rem-less d'; q'b'+r'≡a' = quot-rem-sound d'
r'<'b : r' <' b
r'<'b = PE.subst (r' <'_) (PE.sym b≡b') r'<'b'
q'b+r'≡a : q' * b + r' ≡ a
q'b+r'≡a =
≡begin q' * b + r' ≡[ PE.cong (\x → q' * x + r') b≡b' ]
q' * b' + r' ≡[ q'b'+r'≡a' ]
a' ≡[ PE.sym a≡a' ]
a
≡end
d'' : DivMod a b
d'' = qr q' r' r'<'b q'b+r'≡a
eq : quot d ≡ quot d'' × rem d ≡ rem d''
eq = divmod-unique {a} {b} d d''
---------------------------------------------------------------------
More information about the Agda
mailing list