[Agda] forced arguments in EqReasoning

mechvel at scico.botik.ru mechvel at scico.botik.ru
Sat Nov 28 13:04:52 CET 2020


On 2020-11-28 02:19, guillaume allais wrote:
> Hi Sergei,
> 
> Is your notion of equivalence by any change defined by recursion on its 
> inputs?
> That would explain why you're getting really bad inference despite the
> equational
> reasoning combinators being designed to make inference as strong as 
> possible.
> 

In the last example, there is recursion in _=ₚ_.
The simplest ready example does not apply recursion for equality.
Probably the matter is in a nontrivial equality on records expressed in
the record fields.
May be you mean a composition of equality definitions?
Consider this:

module Fraction.I {α α=} (R : GCDDomain α α=)
   where
   open GCDDomain R
        using (_≈_; _≟_; _≉_; ≈refl; ≈sym; ≈trans; ≉respˡ; ...)
        renaming (Carrier to C)
   ...
   record Fraction : Set (α ⊔ α=) where
     constructor frᶜ
     field  num     : C
            denom   : C
            denom≉0 : denom ≉ 0#
            coprime : Coprime num denom

   open Fraction

   _=fr_ :  Rel Fraction α=
   f =fr g =  (num f * denom g) ≈ (num g * denom f)
   ...

   _*fr_ : Op₂ Fraction
   (frᶜ n₁  d₁ d₁≉0 co-n₁d₁) *fr (frᶜ n₂ d₂ d₂≉0 co-n₂d₂) =
                               frᶜ n₁'n₂' d₁'d₂' d₁'d₂'≉0 
coprime-n₁'n₂'-d₁'d₂'
     where
     n₁' = ...
     ...
     -- There is not any recursion here, only several arithmetic 
operations in R,
     -- and non-recursive proofs with _≈_ in R.

   *fr-cong : Congruent₂ _=fr_ _*fr_
   *fr-cong {f} {f'} {g} {g'} f=fr=f' g=fr=g' =
     begin
       f *fr g     ≈⟨ *fr≗*₁ f g ⟩
       f *₁ g      ≈⟨ *₁cong {f} {f'} {g} {g'} f=fr=f' g=fr=g' ⟩
       f' *₁ g'    ≈⟨ =fr-sym {f' *fr g'} {f' *₁ g'} (*fr≗*₁ f' g') ⟩
       f' *fr g'
     ∎
     where open Fr-Reasoning  -- equational reasoning of lib-1.4 for 
fractionSetoid
------------------------------------------------

Consider this _sym_ (=fr-sym)  in the last step.
Agda 2.6.1 does not allow to skip any implicit argument in it.
But their terms are exactly neighbors in the left hand column.
Can  EqReasoning  observe the left hand columns, compare the terms and
substitute them automatically as needed?

Further, this proof uses *fr≗*₁ and *₁cong.
This uses a certain pair of maps  Fraction R  <-->  Prefraction R.
The  Prefraction  record is similar to Fraction, but the _coprime_
condition is skipped.
And the proofs for Prefraction arithmetic do not suffer of this problem
of forced implicit arguments in EqReasoning.

So: there are records over R:  Prefraction  and  Fraction.
Arithmetic and equality on Fraction uses the ones of Prefraction,
(do you consider this as recursion in equality?).
Prefraction does not force writing unneeded implicits in EqReasoning,
and Fraction does force such.

So, there are equality _=1_ and EqReasoning of record (I)
which call for equality _=2_ and EqReasoning of record (II).
I do not know, may be, the effect is due to this composition.

And with polynomial, the equality on the record of Pol
calls for the equality on the record on Mon,
the equality on the record on Mon calls for basic _≈_ on R and for _≡_ 
on Nat,
also here is the pointwise equality on lists.

Regards,

--
SM






More information about the Agda mailing list