show that Vec is an indexed Setoid
[~helmut/bidiragda.git] / Generic.agda
1 module Generic where
2
3 import Category.Functor
4 import Category.Monad
5 open import Data.List using (List ; length ; replicate) renaming ([] to []L ; _∷_ to _∷L_)
6 open import Data.Maybe using (Maybe ; just ; nothing) renaming (setoid to MaybeEq)
7 open import Data.Nat using (ℕ ; zero ; suc)
8 open import Data.Product using (_×_ ; _,_)
9 open import Data.Vec using (Vec ; toList ; fromList ; map) renaming ([] to []V ; _∷_ to _∷V_)
10 open import Data.Vec.Equality using () renaming (module Equality to VecEq)
11 open import Function using (_∘_)
12 open import Level using () renaming (zero to â„“â‚€)
13 open import Relation.Binary using (Setoid ; module Setoid)
14 open import Relation.Binary.Core using (_≡_ ; refl)
15 open import Relation.Binary.Indexed using (_at_) renaming (Setoid to ISetoid)
16 open import Relation.Binary.PropositionalEquality using (_≗_ ; cong ; subst ; trans) renaming (setoid to PropEq)
17
18 open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_)
19 open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_)
20
21 ∷-injective : {A : Set} {n : â„•} {x y : A} {xs ys : Vec A n} â†’
22               (x âˆ·V xs) â‰¡ (y âˆ·V ys) â†’ x â‰¡ y Ã— xs â‰¡ ys
23 ∷-injective refl = refl , refl
24
25 just-injective : {A : Set} â†’ {x y : A} â†’ Maybe.just x â‰¡ Maybe.just y â†’ x â‰¡ y
26 just-injective refl = refl
27
28 length-replicate : {A : Set} {a : A} â†’ (n : â„•) â†’ length (replicate n a) â‰¡ n
29 length-replicate zero       = refl
30 length-replicate (suc n) = cong suc (length-replicate n)
31
32 map-just-injective : {A : Set} {n : â„•} {xs ys : Vec A n} â†’
33                      map Maybe.just xs â‰¡ map Maybe.just ys â†’ xs â‰¡ ys
34 map-just-injective {xs = []V}      {ys = []V}       p  = refl
35 map-just-injective {xs = x âˆ·V xs′} {ys = y âˆ·V ys′}  p with âˆ·-injective p
36 map-just-injective {xs = x âˆ·V xs′} {ys = .x âˆ·V ys′} p | refl , p′ = cong (_∷V_ x) (map-just-injective p′)
37
38 mapMV : {A B : Set} {n : â„•} â†’ (A â†’ Maybe B) â†’ Vec A n â†’ Maybe (Vec B n)
39 mapMV f []V = just []V
40 mapMV f (x âˆ·V xs) = (f x) >>= (λ y â†’ (_∷V_ y) <$> (mapMV f xs))
41
42 mapMV-cong : {A B : Set} {f g : A â†’ Maybe B} â†’ f â‰— g â†’ {n : â„•} â†’ mapMV {n = n} f â‰— mapMV g
43 mapMV-cong f≗g []V = refl
44 mapMV-cong {f = f} {g = g} f≗g (x âˆ·V xs) with f x | g x | f≗g x
45 mapMV-cong f≗g (x âˆ·V xs) | just y | .(just y) | refl = cong (_<$>_ (_∷V_ y)) (mapMV-cong f≗g xs)
46 mapMV-cong f≗g (x âˆ·V xs) | nothing | .nothing | refl = refl
47
48 mapMV-purity : {A B : Set} {n : â„•} â†’ (f : A â†’ B) â†’ (v : Vec A n) â†’ mapMV (just âˆ˜ f) v â‰¡ just (map f v)
49 mapMV-purity f []V = refl
50 mapMV-purity f (x âˆ·V xs) rewrite mapMV-purity f xs = refl
51
52 maybeEq-from-≡ : {A : Set} {a b : Maybe A} â†’ Setoid._≈_ (PropEq (Maybe A)) a b â†’ Setoid._≈_ (MaybeEq (PropEq A)) a b
53 maybeEq-from-≡ {a = just x}  {b = .(just x)} refl = just refl
54 maybeEq-from-≡ {a = nothing} {b = .nothing}  refl = nothing
55
56 maybeEq-to-≡ : {A : Set} {a b : Maybe A} â†’ Setoid._≈_ (MaybeEq (PropEq A)) a b â†’ Setoid._≈_ (PropEq (Maybe A)) a b
57 maybeEq-to-≡ (just refl) = refl
58 maybeEq-to-≡ nothing     = refl
59
60 subst-cong : {A : Set} â†’ (T : A â†’ Set) â†’ {g : A â†’ A} â†’ {a b : A} â†’ (f : {c : A} â†’ T c â†’ T (g c)) â†’ (p : a â‰¡ b) â†’
61              f âˆ˜ subst T p â‰— subst T (cong g p) âˆ˜ f
62 subst-cong T f refl _ = refl
63
64 subst-fromList : {A : Set} {x y : List A} â†’ (p : y â‰¡ x) â†’
65                  subst (Vec A) (cong length p) (fromList y) â‰¡ fromList x
66 subst-fromList refl = refl
67
68 subst-subst : {A : Set} (T : A â†’ Set) {a b c : A} â†’ (p : a â‰¡ b) â†’ (p′ : b â‰¡ c) â†’ (x : T a) â†’
69               subst T p′ (subst T p x) â‰¡ subst T (trans p p′) x
70 subst-subst T refl p′ x = refl
71
72 toList-fromList : {A : Set} â†’ (l : List A) â†’ toList (fromList l) â‰¡ l
73 toList-fromList []L       = refl
74 toList-fromList (x âˆ·L xs) = cong (_∷L_ x) (toList-fromList xs)
75
76 toList-subst : {A : Set} â†’ {n m : â„•} (v : Vec A n) â†’ (p : n â‰¡ m) â†’
77                toList (subst (Vec A) p v) â‰¡ toList v
78 toList-subst v refl = refl
79
80 vecIsISetoid : Setoid â„“â‚€ â„“â‚€ â†’ ISetoid â„• â„“â‚€ â„“â‚€
81 vecIsISetoid S = record
82   { Carrier = Vec (Setoid.Carrier S)
83   ; _≈_ = Î» x â†’ S VecEq.≈ x
84   ; isEquivalence = record
85     { refl = VecEq.refl S _
86     ; sym = VecEq.sym S
87     ; trans = VecEq.trans S }
88   }
89
90
91 vecIsSetoid : Setoid â„“â‚€ â„“â‚€ â†’ â„• â†’ Setoid â„“â‚€ â„“â‚€
92 vecIsSetoid S n = (vecIsISetoid S) at n