[Agda] proof for insertion to a list
Sergei Meshveliani
mechvel at botik.ru
Mon Feb 13 18:21:09 CET 2017
Who can tell, please:
why the following proof for add-comm is rejected by Agda 2.5.2 ?
(see the attached .agda file, it is about 30 nonempty lines).
It is about certain insertion add of a pair to a pair list,
with add-comm meaning
add (a , e) ∘ add (b , e') ≗ add (b , e') ∘ add (a , e).
And it is only for the case of e > e' > e₁,
with other cases postulated in the code by `anything'.
I expect that for the last PE.refl, normalization of LHS and RHS
yields the same term
(a , e) ∷ (b , e') ∷ (c , e₁) ∷ mons.
But Agda reports
e != e' of type ℕ
when checking that the expression PE.refl has type
add (a , e) (add (b , e') ((c , e₁) ∷ mons) | tri> .¬a₁ .¬b₁ e'>e₁)
≡ add (b , e') (add (a , e) ((c , e₁) ∷ mons) | tri> .¬a .¬b e>e₁)
Thanks,
------
Sergei
-------------- next part --------------
{-
Can anybody, please, fix the proof for lemma2
in the attached code (about 140 lines) ?
It is about a certain insertion of a natural into a decreasingly ordered
list of naturals. Such a list is called Pol.
Insertion of e into es is according to _>_, and it is without copying,
that is when es contains any e' ≡ e, the result is es.
Insertion is called mon+.
lemma1 and lemma2 are certain two very simple statements about insertion
of e into (e' ∷ es) for e < e'.
lemma1 is for the case of es = []. And it is proved trivially.
But a similar proof for lemma2 is not type-checked (in Agda 2.5.2).
Moreover, I do not find any proof to satisfy Agda.
Maybe, this is a bug in Agda?
Thanks,
------
Sergei
-}
open import Function using (_∘_; case_of_)
open import Algebra.FunctionProperties using (Op₂)
open import Relation.Binary using (Rel; Tri; DecTotalOrder; StrictTotalOrder)
open import Relation.Binary.PropositionalEquality as PE using (_≡_)
open import Data.Empty using (⊥-elim)
open import Data.Sum using (_⊎_)
open import Data.Product using (_×_; _,_; proj₁; proj₂; ∃)
open import Data.List using (List; []; _∷_)
open import Data.List.All as AllM using (All)
open import Data.Nat as Nat using (ℕ; suc; _≤_; _<_; _>_)
open import Data.Nat.Properties as NatProp using ()
--****************************************************************************
postulate anything : ∀ {a} {A : Set a} → A -- for debug
natSTO = NatProp.strictTotalOrder
open StrictTotalOrder natSTO using (compare)
------------------------------------------------------------------------------
data DecrOrdered : List ℕ → Set
where
nil : DecrOrdered []
single : (x : ℕ) → DecrOrdered (x ∷ [])
prep2 : (x y : ℕ) → (xs : List ℕ) → x > y → DecrOrdered (y ∷ xs) →
DecrOrdered (x ∷ y ∷ xs)
tailDecrOrdered : ∀ {x xs} → DecrOrdered (x ∷ xs) → DecrOrdered xs
tailDecrOrdered (single _) = nil
tailDecrOrdered (prep2 x y xs _ ord-y:xs) = ord-y:xs
------------------------------------------------------------------------------
E : Set
E = ℕ
record Pol : Set where
constructor pol′
field exps : List E
ordered : DecrOrdered exps -- e1 > ... > en
monPol : E → Pol
monPol e = pol′ (e ∷ []) (DecrOrdered.single e)
hdExp' : List E → ℕ
hdExp' [] = 0
hdExp' (e ∷ _) = suc e
deg' : Pol → ℕ
deg' = hdExp' ∘ Pol.exps
------------------------------------------------------------------------------
open Tri
------------------------------------------------------------------------------
insert : E → List E → List E
insert e [] = e ∷ []
insert e (e' ∷ es) with compare e e'
...
| tri> _ _ e>e' = e ∷ e' ∷ es
... | tri≈ _ e≡e' _ = e ∷ es
... | tri< e<e' _ _ = e' ∷ (insert e es)
insert-preserves-DecrOrdered : ∀ e → (insert e) Preserves DecrOrdered
insert-preserves-DecrOrdered e {[]} _ = DecrOrdered.single e
insert-preserves-DecrOrdered e {e' ∷ es} ord-e'es with compare e e'
...
| tri> _ _ e>e' = decrOrdered-cons e>e'es ord-e'es
where
...
... | tri≈ _ e≡e' = ord-e'es with compare e e'
... | tri< _ _ =
where
ord-es = ..
es' = insert e
{-
------------------------------------------------------------------------------
mon+ : E → Pol → Pol
mon+ e = proj₁ ∘ extMon+ e
------------------------------------------------------------------------------
lemma1 : ∀ e e' → e < e' → Pol.exps (mon+ e (monPol e')) ≡ e' ∷ e ∷ []
lemma1 e e' e<e' with compare e e'
... | tri< _ _ _ = PE.refl
... | tri> e≮e' _ _ = ⊥-elim (e≮e' e<e')
... | tri≈ e≮e' _ _ = ⊥-elim (e≮e' e<e')
-- Problem
lemma2 : ∀ e e' es → (ord-e'es : DecrOrdered (e' ∷ es)) → e < e' →
let
f = pol′ (e' ∷ es) ord-e'es
ord-es : DecrOrdered es
ord-es = tailDecrOrdered ord-e'es
f' = pol′ es ord-es
in
Pol.exps (mon+ e f) ≡ e' ∷ (Pol.exps (mon+ e f'))
lemma2 e e' es ord-e'es e<e' with compare e e'
... | tri< _ _ _ = PE.refl
-- anything
... | _ = anything
-}
More information about the Agda
mailing list