[Agda] map⊆

Sergei Meshveliani mechvel at botik.ru
Fri Oct 10 17:44:34 CEST 2014


People,
I program mapping the _⊆_ relation on lists:

  ...

  map⊆ : (f : C → C') → (f Preserves _≈_ ⟶ _≈'_) → {xs ys : List C} →
                                          xs ⊆ ys → map f xs ⊆' map f ys

  map⊆ f fCong {xs} {ys} xs⊆ys {z} z∈f-xs =
       let
         (x , x∈≡xs , fx≈z) = counter-map f xs z z∈f-xs
         x∈xs    = ∈≡→∈ x∈≡xs
         x∈ys    = xs⊆ys x∈xs
         fx∈f-ys = map∈ f fCong x∈ys
       in
       cong₁∈' fx≈z fx∈f-ys

Here _≈_ and _≈'_ are of the two corresponding setoids.
This implementation uses 

 map∈ : (f : C → C')  → (f Preserves _≈_ ⟶ _≈'_) → {x : C} →
        {xs : List C} → x ∈ xs                   → f x ∈' map f xs 
 ,
 counter-map : (f : C → C') → (xs : List C) → (y : C') → y ∈' map f xs →
                                               ∃ \x → x ∈≡ xs × f x ≈' y
 ,
 cong₁∈' : {zs : List C'} → (\x → x ∈' zs) Respects _≈'_

-- which I implement in their turn.


And I wonder of whether all this is inventing a bicycle.
Can  map⊆  be expressed in a simpler way?
What Standard library has for all this?

Thanks,

------
Sergei



More information about the Agda mailing list