[Agda] more about insertion to a list
Sergei Meshveliani
mechvel at botik.ru
Sat Feb 18 19:21:21 CET 2017
Who can tell, please,
why the attached code (about 30 nonempty lines) is not type-checked
in Agda 2.6.0-e384ae7
?
Namely, PE.refl is reported in the end as having a wrong type.
The code is about the lemma comm below:
----------------------------
Mon = ℕ × ℕ
add : Mon → List Mon → List Mon
add (a , e) [] = (a , e) ∷ []
add (a , e) ((b , e') ∷ mons) with compare e e'
...
| tri> _ _ _ = (a , e ) ∷ (b , e') ∷ mons
... | tri< _ _ _ = (b , e') ∷ (add (a , e) mons)
... | tri≈ _ _ _ = (a + b , e) ∷ mons
comm : ∀ a e b e' mons → add (a , e ) (add (b , e') mons) ≡
add (b , e') (add (a , e ) mons)
----------------------------
The question is about
comm a e b e' ((c , e₁) ∷ mons),
and only for the branch of e > e'; e > e₁; e' > e₁; e' < e.
The branches are represented by cascading with the construct of
with compare x y | PE.inspect (compare x) y
and by using `rewrite'.
In the considered brach, LHS and and RHS must normalize to the same
term:
LHS = add (a , e) (add (b , e') ((c , e₁) ∷ mons)) ≡[ e'>e₁ ]
add (a , e) ((b , e') ∷ (c , e₁) ∷ mons) ≡[ e>e' ]
(a , e) ∷ (b , e') ∷ (c , e₁) ∷ mons
RHS = add (b , e') (add (a , e) ((c , e₁) ∷ mons)) ≡[ e>e₁ ]
add (b , e') ((a , e) ∷ (c , e₁) ∷ mons) ≡[ e'<e ]
(a , e) ∷ (add (b , e') ((c , e₁) ∷ mons)) ≡[ e'>e₁ ]
(a , e) ∷ (b , e') ∷ (c , e₁) ∷ mons
But Agda does not agree with this.
Am I missing something? May be I misuse `inspect' and `rewrite' ?
Can anybody fix the proof?
Thanks,
------
Sergei
-------------- next part --------------
open import Relation.Binary using (Tri; StrictTotalOrder)
open import Relation.Binary.PropositionalEquality as PE using (_≡_; _≢_)
open PE.≡-Reasoning renaming (_≡⟨_⟩_ to _≡[_]_; begin_ to ≡begin_;
_∎ to _≡end)
open import Data.Empty using (⊥-elim)
open import Data.Product using (_×_; _,_)
open import Data.List using (List; []; _∷_)
open import Data.Nat using (ℕ; _+_; _<_)
open import Data.Nat.Properties using (strictTotalOrder)
------------------------------------------------------------------------------
postulate anything : ∀ {a} {A : Set a} → A -- for debug
open StrictTotalOrder strictTotalOrder using (compare)
Mon : Set
Mon = ℕ × ℕ
open Tri
add : Mon → List Mon → List Mon
add (a , e) [] = (a , e) ∷ []
add (a , e) ((b , e') ∷ mons) with compare e e'
...
| tri> _ _ _ = (a , e ) ∷ (b , e') ∷ mons
... | tri< _ _ _ = (b , e') ∷ (add (a , e) mons)
... | tri≈ _ _ _ = (a + b , e) ∷ mons
------------------------------------------------------------------------------
comm : ∀ a e b e' mons → add (a , e ) (add (b , e') mons) ≡
add (b , e') (add (a , e ) mons)
comm _ _ _ _ [] = anything
comm a e b e' ((c , e₁) ∷ mons) with compare e e' | PE.inspect (compare e) e'
comm a e b e' ((c , e₁) ∷ mons)
| tri> e>e' _ _ | PE.[ eq-e>e' ] rewrite eq-e>e'
with compare e e₁ | PE.inspect (compare e) e₁
comm a e b e' ((c , e₁) ∷ mons)
| tri> e>e' _ _ | _ | tri> _ _ e>e₁ | PE.[ eq-e>e₁ ] rewrite eq-e>e₁
with compare e' e₁ | PE.inspect (compare e') e₁
comm a e b e' ((c , e₁) ∷ mons)
| tri> e>e' _ _ | _ | tri> _ _ e>e₁ | _ | tri> _ _ e'>e₁ |
PE.[ eq-e'>e₁ ] rewrite eq-e'>e₁
with compare e' e | PE.inspect (compare e') e
comm a e b e' ((c , e₁) ∷ mons)
| tri> e>e' _ _ | _ | tri> _ _ e>e₁ | _ | tri> _ _ e'>e₁ | _ | tri< e'<e _ _
| PE.[ eq-e'<e ] rewrite eq-e'<e =
PE.refl
comm a e b e' ((c , e₁) ∷ mons) | _ | _ = anything
{- ----------------
LHS = add (a , e) (add (b , e') ((c , e₁) ∷ mons)) ≡[ e'>e₁ ]
add (a , e) ((b , e') ∷ (c , e₁) ∷ mons) ≡[ e>e' ]
(a , e) ∷ (b , e') ∷ (c , e₁) ∷ mons
RHS = add (b , e') (add (a , e) ((c , e₁) ∷ mons)) ≡[ e>e₁ ]
add (b , e') ((a , e) ∷ (c , e₁) ∷ mons) ≡[ e'<e ]
(a , e) ∷ (add (b , e') ((c , e₁) ∷ mons)) ≡[ e'>e₁ ]
(a , e) ∷ (b , e') ∷ (c , e₁) ∷ mons
-----------------
-}
More information about the Agda
mailing list