[Agda] irrelevancy annotation

mechvel at scico.botik.ru mechvel at scico.botik.ru
Tue Dec 22 17:08:03 CET 2020


On 2020-12-22 01:04, Carette, Jacques wrote:
> Don't use double-negation.  Instead of Null, use an HasElement 
> data-structure.
> data HasElement : List A → Set α  where
>   has-elem : (x : A) {xs List A} -> HasElement (x ∷ xs)
> 
> Then you need to match on both the list and has-elem enough to reveal
> the actual head.


Thank you. I am going to try the approach.


> I don't know why you want this to be irrelevant though.

Because if it is defined
   head : (xs : List A) → ¬ Null xs → A

then `refl' is not a proof for  head xs nn ≡ head xs nn'.
Many functions start to depend on the witness for a list non-emptiness.
For example, I represent a polynomial in  x  mainly as a list of 
monomials,
with adding certain conditions for ordering and for the coefficients 
being nonzero.
For example,  a*x^3 + b  is represented as
                                    pol ((a , 3) :: (b , 0) :: []) _ _,
where  a, b /= 0#.
Zero polynomial contains [] in its bag.
So the degree function  deg  for a polynomial needs to be   proj₂ ∘ head 
∘ Pol.monomials.
But it is defined only for a nonzero polynomial.
So,  deg  depends on the witness for  ¬ Null monomials.
In algebra, we take it for granted that equal nonzero polynomials have 
equal degree.
Bun with Agda, one needs to explicitly prove and apply the lemma of that
deg (`head') is irrelevant on the non-emptiness witness.


> Are you sure you don't want a Vec instead of a List?  Lists are best 
> understood as
> vectors that have forgotten their length.

?
Never thought of this.
Rather I thought reversely: List looks more basic than Vector.
So, I use my home-made Vector:

   module OfVector {α} (A : Set α) (n : ℕ)
     where
     data Vector : Set α  where
                          vec : (xs : List A) → length xs ≡ n → Vector

Having a bag of (vec xs _), it is possible to use all rich Standard 
library
functionality for  xs : List A.  And conversion to List is in one step.
And there is no need to add a huge functionality for Vector that would
(I expect) actually copy the List functionality.
?

--
SM


More information about the Agda mailing list