[Agda] irrelevant arg example

Sergei Meshveliani mechvel at botik.ru
Thu Aug 21 18:04:46 CEST 2014


On Wed, 2014-08-20 at 17:56 +0200, Ulf Norell wrote:
> I'm not sure what the different behaviour you are getting is (can you
> elaborate?), but f can be implemented as follows:
> 
> 
> ⊥-elim-irr : .⊥ → ∀ {a} {A : Set a} → A
> ⊥-elim-irr ()
> 
> 
> f : (x : ℕ) → .(nz : x ≢ 0) → x ≢ 0
> 
> f x nz z = ⊥-elim-irr (nz z)
> 
> 
> Under normal circumstances irrelevant things cannot be used in
> relevant contexts, but one exception is that you are allowed absurd
> elimination of irrelevant empty types into relevant types.
> 

Consider the example:

  record Foo (b : ℕ) (nzb : b ≢ 0) : Set where
                                         field foo : ℕ
  g : (x : ℕ) → .(nz : x ≢ 0) → ℕ
  g x _ = x + x

  f : (x : ℕ) → .(nz : x ≢ 0) → Foo x nz
  f x nz =  record { foo = g x nz }

In what contexts  "Foo x nz"  and  "g x nz"  are using  nz, 
in relevant contexts?

Agda of  August 19 2014  reports of an irrelevant  nz  wrongly used in
Foo x nz.
(Foo x _)  is said an "unsolved metas".
Is this possible to fix the implementation for  f  without changing the
above signatures? 

Agda-2.4.0.2  treated such examples in a different way. It type-checked
them, may be, after changing some occurrences of  nz  to  _. 

I suspect that I am forced to add a dot to  Foo :

  record Foo (b : ℕ) .(nzb : b ≢ 0)  ...

Which Agda is more correct at this point?


General consideration
--------------------- 
(1) In classical algorithmic mathematics, the conditions like the above 
x ≢ 0  need in most cases to be irrelevant: the result of the client
function does not depend on the way in which the condition is verified.

(2) On the other hand, Agda has proofs as data, and claims that it is
often nice to process a proof data to evaluate the value of a function.
For example, this is natural to process proofs in a provable function
for sorting a list (can this be implemented in other way?).

These two lines contradict each other. So that  
a) I doubt about using irrelevant patterns, 
b) on the other hand, not using them is likely to cause many additional
lengthy proofs about independence of the result on the condition
witness.

Meanwhile, I try this approach: 
to use irrelevant arguments everywhere where the type checker rejects
the proof due to seeing two witnesses in the scope for the condition. 
I doubt where this will lead me.
Also there is a question about Standard library.

Regards,

------
Sergei




More information about the Agda mailing list