[Agda] x ∈ (append y xs) → ..

Sergei Meshveliani mechvel at botik.ru
Thu Dec 19 09:56:50 CET 2013


I am sorry for disturbance.

I did another attempt, and it occurs that it has fixed itself!
So that  lemma1  can be written similar as  lemma0.
This effect of auto-fix happens for the second time for the example of
this kind.

Also sometimes expressions like, say,   {xs : List ℕ} → x ∈ (append0 xs)
are not parsed, 
then I re-type the whole line, and they get parsed! 
As if the system plays jokes. 
(Maybe, this is due to details of  emacs  usage?). 

I do not recall all the details. May be this effect with lemma1 is due
to that I often omit the remaining patterns -- for debugging. If it
reports "missing patterns",  then it often occurs that the current
patterns are correct, and then I proceed with the remaining ones. 
May be it is more reliable to provide all patterns for the same purpose,
with setting `postulate' in the remaining ones. 

Thanks,

------
Sergei



On Wed, 2013-12-18 at 18:52 +0100, Andreas Abel wrote:
> As always, self-contained code is appreciated to answer your question. 
> --Andreas
> 
> On 18.12.2013 12:23, Sergei Meshveliani wrote:
> > Can anybody explain, please, why the below  lemma1  is more difficult to
> > prove to Agda than  lemma0
> > ?
> >
> > append0 : List ℕ → List ℕ
> > append0 []       =  0 ∷ []
> > append0 (x ∷ xs) =  x ∷ (append0 xs)
> >
> > append : ℕ → List ℕ → List ℕ
> > append x []       =  x ∷ []
> > append x (y ∷ xs) =  y ∷ (append x xs)
> >
> > open module Mem-ℕ = Membership natSetoid using (_∈_)
> >
> > ---------------------------------------------------------------------
> > lemma0 : (x : ℕ) → (xs : List ℕ) → x ∈ (append0 xs) → x ≡ 0 ⊎ (x ∈ xs)
> >
> > lemma0 _ [] (here x=y) =  inj₁ x=y
> > ...
> > -- skip other patterns
> >
> > --------------------------------------------------------------------
> > lemma1 : (x y : ℕ) → (xs : List ℕ) → x ∈ (append y xs) →
> >                                           x ≡ y ⊎ (x ∈ xs)
> > lemma1 _ _ [] (here x=y) =  inj₁ x=y
> > --------------------------------------------------------------------
> >
> > lemma0  is proved in a natural way, and is type-checked.
> >
> > For  lemma1,
> > I expected of the checker to report of "missing patterns" -- which will
> > mean that the first pattern is all right.
> >
> > And the   development Agda of November ~20 2013
> > reports
> > "
> > I'm not sure if there should be a case for the constructor here,
> > because I get stuck when trying to solve the following unification
> > problems (inferred index ≟ expected index):
> >    x₁ ∷ xs₁ ≟ append y xs
> > when checking the definition of lemma1
> > ".
> >
> > I fix the proof by writing a strange complicated code instead of the
> > first pattern:
> >
> >    lemma1 x y [] x∈app-y-xs =  inj₁ x=y
> >      where
> >      x=y : x ≡ y
> >      x=y  with x∈app-y-xs
> >      ... | here eq = eq
> >      ... | there ()
> >
> > This looks strange: the checker is sure and "is not sure" in a pattern
> > which is actually the same.
> > I guess that for the first pattern, it is not sure that  append y []
> > is non-empty. But it follows only from normalization.
> >
> > Does this present a bug?
> >
> > Thanks,
> >
> > ------
> > Sergei
> >
> >
> > _______________________________________________
> > Agda mailing list
> > Agda at lists.chalmers.se
> > https://lists.chalmers.se/mailman/listinfo/agda
> >
> 
> 




More information about the Agda mailing list