[Agda] x \in (gfilter _ ys)

Sergei Meshveliani mechvel at botik.ru
Sun Aug 18 14:02:57 CEST 2013


People,                                                                                 
I have the next round in my battle with a filtered list proofs.
I need to proof that 
                     x ∈  gfilter (toMaybe' P?) ys 
if                   x ∈  ys              
                     and  P Respects _≈_,  and (P x).

This needs to be by the function  in-gfiltered-id  below:

-----------------------------------------------------------------
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.Unary   using (Decidable)
open import Relation.Binary  using (Rel; Setoid; module Setoid;
                                    DecSetoid; module DecSetoid)
open import Relation.Binary.Core using (_Respects_; IsEquivalence;
                                        module IsEquivalence)
open import Data.Empty    using (⊥-elim)
open import Data.Maybe    using (Maybe; just; nothing)
open import Data.Product  using (_×_; _,_)
open import Data.List     using (List; []; _∷_; map; gfilter)
open import Data.List.Any using (Any; module Any; module Membership)

       
toMaybe' : ∀ {p} {C : Set} {P : C → Set p} → Decidable P → C → Maybe C
toMaybe' P? x  with P? x
...                     | yes _ =  just x
...                     | _     =  nothing


postulate anything : ∀ {a} {A : Set a} → A       -- for debug  

in-gfiltered-id : ∀ {l p} (A : Setoid 0L l) →    -- case f = id  
  let
     open Setoid A using (_≈_) renaming (Carrier to C)
     _∈_ = Membership._∈_ A
  in
  (P : C → Set p) → (P? : Decidable P) → P Respects _≈_ → (x : C) → 
  P x → (ys : List C) → x ∈ ys →
                        x ∈ (gfilter (toMaybe' P?) ys)

open Any

in-gfiltered-id {l} {p} A P P? pCong x Px (y ∷ ys) (here x=y) =

  (let triple : Dec (P y) × Maybe C × List C
       triple = (P? y , toMb y , filterMb (y ∷ ys))
   in
   case triple of \
   { (no ¬Py , _ ,      _  ) → let Py = pCong x=y Px in  ⊥-elim (¬Py Py)
   ; (yes Py , just y , z ∷ zs) →
               let 
                  y=z : y ≈ z
                  y=z = _ -- ? refl                          
                  x=z : x ≈ z
                  x=z = anything -- ? trans x=y y=z

                  p : Any {0L} {_} (_≈_ x) (z ∷ zs)
                  p = here x=z                      -- ?
                  -- here {0L} {_} {C} (_≈_ x) (z ∷ zs) {z} {zs} x=z    
                  -- here {A = C} (_≈_ x) (z ∷ zs) {z} {zs} x=z  
               in p

   ; (yes Py , just y ,  []) → _  -- ?
   ; (yes Py , nothing , _ ) → _  -- ?
   }
  )
  where
  open Setoid A using (_≈_) renaming (Carrier to C)
  open IsEquivalence (Setoid.isEquivalence A) using (refl; sym; trans)
  toMb     = toMaybe' P?
  filterMb = gfilter toMb

in-gfiltered-id A P P? pCong x Px (y ∷ ys) (there x∈ys) = _

            -- after failing with `here', I have not hope with `there'

----------------------------------------------------------------------

1. How to prove  in-gfiltered-id ?

2. A note:  instead of  let triple : ...
                            triple = ( ... )
                        in   
                        case triple of ...

above it is natural to write
      
            case (P? y , toMb y , filterMb (y ∷ ys)) of ...,

but this latter is not type-checked (in Agda-2.3.2.1).

3. The report is 
-------------
Cannot instantiate the metavariable _84 to solution 
Any (_≈_ x) (z ∷ zs) since it contains the variable z which is not in
scope of the metavariable or irrelevant in the metavariable but relevant
in the solution when checking that the expression p has type
_B_84 A P P? pCong x Px y ys x=y
-------------

What is wrong with  z  ? 

4. I tried to write  `here' in full:
                        
           p = here {0L} {_} {C} (_≈_ x) (z ∷ zs) {z} {zs} x=z
 
And it reports
-------------------
Any (_P_100 A P P? pCong x Px y ys x=y Py y z zs)
(_x_101 A P P? pCong x Px y ys x=y Py y z zs ∷
 _xs_102 A P P? pCong x Px y ys x=y Py y z zs)
should be a function type, but it isn't
when checking that 
                          (z ∷ zs) {z} {zs} x=z 

are valid arguments to a function of type
Any (_P_100 A P P? pCong x Px y ys x=y Py y z zs)
(_x_101 A P P? pCong x Px y ys x=y Py y z zs ∷
 _xs_102 A P P? pCong x Px y ys x=y Py y z zs)
---------------------
   
Thank you in advance for explanation,

------
Sergei








More information about the Agda mailing list