[Agda] multiple instance resolution and negation

Marcus Christian Lehmann lehmann at tet.tu-berlin.de
Fri Aug 28 17:32:38 CEST 2020


Dear Agda community,

Is there a possibility to make instances like

   i1 : {{ a : A }} → ⊥
   i2 : {{ b : B }} → ⊥
   i3 : {{ c : C }} → ⊥

unambiguous in an instance resolution?

CONTEXT:

I am investigating on the usefulness of instance arguments for partial 
functions such as the positive square root function.

In this particular example, the square root function takes as an 
additional argument a proof that the argument is nonnegative:

   sqrt : (x : X) → {{p : (0ˣ ≤ x)}} → X

When _≤_ is defined in terms of _<_ and ⊥ as

   _≤_ : X → X → Set ℓ'
   a ≤ b = (b < a) → ⊥

then Agda complains that

   "Instance arguments with explicit arguments are never considered by"
   "instance search, so having an instance argument ⦃ p : 0ˣ ≤ x ⦄ has"
   "no effect."
   "when checking that the expression ⦃ p : 0ˣ ≤ x ⦄ → X is a type"

I came up with a different definition

   _≤ᵢ_ : X → X → Set ℓ'
   a ≤ᵢ b = {{p : b < a}} → ⊥

that works on

   sqrt : (x : X) → {{p : (0ˣ ≤ᵢ x)}} → X

when used like so:

   inst-¬ : ∀{ℓ} {A : Set ℓ} → (A → ⊥) → {{a : A}} → ⊥
   inst-¬ f {{a}} = f a

   test1 : (x : X) → (0ˣ ≤ x) → X
   test1 x 0≤x = let instance _ = inst-¬ 0≤x
                 in sqrt x -- works!

but when multiple instances are in scope

   test2 : (x y z : X) → (0ˣ ≤ x) → (0ˣ ≤ y) → (0ˣ ≤ z) → X
   test2 x y z 0≤x 0≤y 0≤z =
     let instance 0≤xᵢ : 0ˣ ≤ᵢ x
                  0≤xᵢ = inst-¬ 0≤x
                  0≤yᵢ : 0ˣ ≤ᵢ y
                  0≤yᵢ = inst-¬ 0≤y
                  0≤zᵢ : 0ˣ ≤ᵢ z
                  0≤zᵢ = inst-¬ 0≤z
     -- Goal: X
     -- Have: ⦃ p : 0ˣ ≤ᵢ x ⦄ → X
     in sqrt y -- error!

then Agda complains:

   _p_51 : 0ˣ ≤ᵢ y
   errorFailed to solve the following constraints:
     Resolve instance argument
       _p_51
         : {ℓ = ℓ₁ : Agda.Primitive.Level} {ℓ' = ℓ'' : Agda.Primitive.Level}
           (X₁ : Set ℓ₁) (0ˣ₁ : X₁) (_<₁_ : X₁ → X₁ → Set ℓ'') (x₁ y₁ z₁ 
: X₁)
           (0≤x₁ : 0ˣ₁ ≤ x₁) (0≤y₁ : 0ˣ₁ ≤ y₁) (0≤z₁ : 0ˣ₁ ≤ z₁) →
           0ˣ₁ ≤ᵢ y₁
     Candidates
       λ ⦃ a ⦄ → z a : ⦃ p : 0ˣ _<_ X ⦄ → ⊥
       λ ⦃ a ⦄ → 0≤x a : ⦃ p : 0ˣ x X ⦄ → ⊥
       λ ⦃ a ⦄ → 0≤y a : ⦃ p : 0ˣ y X ⦄ → ⊥

apart from the quirky candidate display (which does not make sense to me);

shouldn't it be possible for Agda to distinguish these three candidates 
and pick the right one?

kind regards,
Christian


PS: This issue arises. I guess, because Agda can look into the 
definition of _≤_ since everything works out, when hiding the definition 
as in

   _≤'_ : X → X → Set ℓ'
   abstracta ≤' b = (b < a) → ⊥

e.g.

   test3 : (x y z : X) → (0ˣ ≤' x) → (0ˣ ≤' y) → (0ˣ ≤' z) → X
   test3 x y z 0≤x 0≤y 0≤z =
     let instance _ = 0≤x ; _ = 0≤y ; _ = 0≤z
     in sqrt' y -- works!

I would also be happy with a different approach.

PPS: the closest item on this mailing list was an email of Apostolis 
Xekoukoulotakis from 03.11.17, 11:52 but it does not address this issue




More information about the Agda mailing list