[Agda] elem x (filter xs)
Sergei Meshveliani
mechvel at botik.ru
Wed Aug 14 13:51:26 CEST 2013
Can you, please, help with the following example with a filtered list?
-----------------------------------------------------------------------
open import Level using (Level) renaming (zero to 0L)
open import Function using (case_of_)
open import Relation.Nullary using (Dec; yes; no)
open import Relation.Binary.Core using (_≡_; refl)
open import Data.Empty using (⊥-elim)
open import Data.Nat using (ℕ; _≟_)
open import Data.List using (List; []; _∷_)
open import Data.List.Any using (Any; module Any)
postulate member : ℕ → Set
postulate member? : (x : ℕ) → Dec (member x)
filterMem : List ℕ → List ℕ
filterMem [] = []
filterMem (x ∷ xs) with member? x
... | yes _ = x ∷ (filterMem xs)
... | _ = filterMem xs
open Any
lemma1 : (x : ℕ) → member x → Any (_≡_ x) (filterMem (x ∷ []))
lemma1 x mem-x with member? x | filterMem (x ∷ [])
... | (yes _) | .(x ∷ []) = here {x} {[]} refl
-----------------------------------------------------------------------
This is an attempt to prove this trivial statement:
if x is in a subset S then x is in filterMem (x :: []),
where filterMem filters my membership to S.
To be more explicit, I replace x \in ys with Any (_≡_ x) ys.
The Agda-2.3.2.1 (lib-0.7) report is
------
Failed to infer the value of dotted pattern
when checking that the pattern .(x ∷ []) has type List ℕ
------
1. Having mem-x : member x, why does not it accept .(x ∷ [])
for filterMem (x ∷ []) ?
2. Then, I change the last line to
... | (yes _) | (_ ∷ _) = here {x} {[]} refl
And it reports
-------
ℕ !=< Level of type Set
when checking that the expression x has type Level
-------
This is on the {x} occurrence in the last line.
Why x needs to be of Level ?
`here' has not Level among its argument types.
3. Having mem-x and normalization by filterMem,
I expected that a simple `` = here refl''
would do the implementation. But it does not.
4. Changing to
... | (yes _) | y :: ys = here {x} {_} x=y
where
x=y = x ≡ y
x=y = ?
we need to prove x ≡ y, which is not simpler than the initial goal.
5. How to prove the goal?
Thank you in advance for explanation,
------
Sergei
More information about the Agda
mailing list