[Agda] " | condition " in report
Sergei Meshveliani
mechvel at botik.ru
Thu Dec 19 19:22:21 CET 2013
Please,
what is wrong in the below program?
------------------------------------------------------------------------
open import Relation.Nullary using (yes; no)
open import Relation.Binary using
(module Setoid; module DecSetoid; module DecTotalOrder)
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.Sum using (_⊎_; inj₁; inj₂)
open import Data.Product using (_×_; _,_; proj₁)
open import Data.Nat as Nat using (ℕ)
open import Data.List using (List; []; _∷_; map)
open import Data.List.Any using (Any; module Any; module Membership)
open Any
natDecSetoid = DecTotalOrder.Eq.decSetoid Nat.decTotalOrder
_≟_ = DecSetoid._≟_ natDecSetoid
natSetoid = DecSetoid.setoid natDecSetoid
open module Mem-ℕ = Membership natSetoid using (_∈_)
------------------------------------------------------------------------
getKeys : List (ℕ × ℕ) → List ℕ
getKeys = map proj₁
insert : ℕ → ℕ → List (ℕ × ℕ) → List (ℕ × ℕ)
insert k v [] = (k , v) ∷ []
insert k v ((k' , v') ∷ ps) with k ≟ k'
... | yes _ = (k' , v) ∷ ps
... | no _ = (k' , v') ∷ (insert k v ps)
lemma : (k v : ℕ) → (ps : List (ℕ × ℕ)) → let keys = getKeys ps
ps' = insert k v ps
in
k ∈ keys → getKeys ps' ≡ keys
lemma _ _ [] ()
lemma k _ ((k' , _) ∷ ps) (here k=k') with k ≟ k'
... | yes _ = PE.refl
... | no k≉k' = ⊥-elim (k≉k' k=k')
lemma k v ((k' , v') ∷ ps) (there k∈ks) with k ≟ k'
... |
yes k=k' = PE.refl
... | no k≢k' = goal
where
ps' = (k' , v') ∷ ps
ins-ps' = insert k v ps'
ks = getKeys ps
ins-ps = insert k v ps
keys-ins-ps'=k':keys-ins-ps :
getKeys ins-ps' ≡ k' ∷ (getKeys ins-ps)
keys-ins-ps'=k':keys-ins-ps with k ≟ k'
... | no _ = PE.refl
... | yes k=k' = ⊥-elim (k≢k' k=k')
goal : getKeys ins-ps' ≡ k' ∷ ks
-- (map proj₁ (insert k v ((k' , v') ∷ ps)) ≡ k' ∷ ks)
goal =
≡begin
getKeys ins-ps' ≡[ keys-ins-ps'=k':keys-ins-ps ]
k' ∷ (getKeys ins-ps) ≡[ PE.cong (_∷_ k')
(lemma k v ps k∈ks) ]
k' ∷ ks
≡end
---------------------------------------------------------------------------
Development Agda of November ~20 2013 MAlonzo
finds that everything is correct -- except that the last branch of
... | no k≢k' =
must have the goal type different to getKeys ins-ps' ≡ k' ∷ ks
It reports
"
map (λ r → proj₁ r) (insert k v ((k' , v') ∷ ps) | k Nat.≟ k') !=
k' ∷ map (λ r → proj₁ r) (insert k v ps) of type List ℕ
when checking that the expression goal has type
map (λ r → proj₁ r) (insert k v ((k' , v') ∷ ps) | no k≢k') ≡
k' ∷ map (λ r → proj₁ r) ps
"
Normalizing the last type expression in the report gives
{-
map proj₁ (insert k v ((k' , v') ∷ ps) | no k≢k') ≡
k' ∷ map proj₁ ps
-->
getKeys (insert k v ps' | no k≢k') ≡ k' ∷ getKeys ps
-->
getKeys (ins-ps' | no k≢k') ≡ k' ∷ ks
-}
It differs from the `goal' type only in adding "| no k≢k' ".
1) I do not see what is wrong in my program.
2) How to fix?
Thank you in advance for explanation,
------
Sergei
More information about the Agda
mailing list