there is no need to work with IsPreorder
[~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 (_āˆ˜_ ; id)
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 just-injective : {A : Set} ā†’ {x y : A} ā†’ Maybe.just x ā‰” Maybe.just y ā†’ x ā‰” y
22 just-injective refl = refl
23
24 length-replicate : {A : Set} {a : A} ā†’ (n : ā„•) ā†’ length (replicate n a) ā‰” n
25 length-replicate zero    = refl
26 length-replicate (suc n) = cong suc (length-replicate n)
27
28 mapMV : {A B : Set} {n : ā„•} ā†’ (A ā†’ Maybe B) ā†’ Vec A n ā†’ Maybe (Vec B n)
29 mapMV f []V = just []V
30 mapMV f (x āˆ·V xs) = (f x) >>= (Ī» y ā†’ (_āˆ·V_ y) <$> (mapMV f xs))
31
32 mapMV-cong : {A B : Set} {f g : A ā†’ Maybe B} ā†’ f ā‰— g ā†’ {n : ā„•} ā†’ mapMV {n = n} f ā‰— mapMV g
33 mapMV-cong fā‰—g []V = refl
34 mapMV-cong {f = f} {g = g} fā‰—g (x āˆ·V xs) with f x | g x | fā‰—g x
35 mapMV-cong fā‰—g (x āˆ·V xs) | just y | .(just y) | refl = cong (_<$>_ (_āˆ·V_ y)) (mapMV-cong fā‰—g xs)
36 mapMV-cong fā‰—g (x āˆ·V xs) | nothing | .nothing | refl = refl
37
38 mapMV-purity : {A B : Set} {n : ā„•} ā†’ (f : A ā†’ B) ā†’ (v : Vec A n) ā†’ mapMV (just āˆ˜ f) v ā‰” just (map f v)
39 mapMV-purity f []V = refl
40 mapMV-purity f (x āˆ·V xs) rewrite mapMV-purity f xs = refl
41
42 maybeEq-from-ā‰” : {A : Set} {a b : Maybe A} ā†’ Setoid._ā‰ˆ_ (PropEq (Maybe A)) a b ā†’ Setoid._ā‰ˆ_ (MaybeEq (PropEq A)) a b
43 maybeEq-from-ā‰” {a = just x}  {b = .(just x)} refl = just refl
44 maybeEq-from-ā‰” {a = nothing} {b = .nothing}  refl = nothing
45
46 maybeEq-to-ā‰” : {A : Set} {a b : Maybe A} ā†’ Setoid._ā‰ˆ_ (MaybeEq (PropEq A)) a b ā†’ Setoid._ā‰ˆ_ (PropEq (Maybe A)) a b
47 maybeEq-to-ā‰” (just refl) = refl
48 maybeEq-to-ā‰” nothing     = refl
49
50 sequenceV : {A : Set} {n : ā„•} ā†’ Vec (Maybe A) n ā†’ Maybe (Vec A n)
51 sequenceV = mapMV id
52
53 sequence-map : {A B : Set} {n : ā„•} ā†’ (f : A ā†’ Maybe B) ā†’ sequenceV {n = n} āˆ˜ map f ā‰— mapMV f
54 sequence-map f []V = refl
55 sequence-map f (x āˆ·V xs) with f x
56 sequence-map f (x āˆ·V xs) | just y = cong (_<$>_ (_āˆ·V_ y)) (sequence-map f xs)
57 sequence-map f (x āˆ·V xs) | nothing = refl
58
59 subst-cong : {A : Set} ā†’ (T : A ā†’ Set) ā†’ {g : A ā†’ A} ā†’ {a b : A} ā†’ (f : {c : A} ā†’ T c ā†’ T (g c)) ā†’ (p : a ā‰” b) ā†’
60              f āˆ˜ subst T p ā‰— subst T (cong g p) āˆ˜ f
61 subst-cong T f refl _ = refl
62
63 subst-fromList : {A : Set} {x y : List A} ā†’ (p : y ā‰” x) ā†’
64                  subst (Vec A) (cong length p) (fromList y) ā‰” fromList x
65 subst-fromList refl = refl
66
67 subst-subst : {A : Set} (T : A ā†’ Set) {a b c : A} ā†’ (p : a ā‰” b) ā†’ (pā€² : b ā‰” c) ā†’ (x : T a) ā†’
68               subst T pā€² (subst T p x) ā‰” subst T (trans p pā€²) x
69 subst-subst T refl pā€² x = refl
70
71 toList-fromList : {A : Set} ā†’ (l : List A) ā†’ toList (fromList l) ā‰” l
72 toList-fromList []L       = refl
73 toList-fromList (x āˆ·L xs) = cong (_āˆ·L_ x) (toList-fromList xs)
74
75 toList-subst : {A : Set} ā†’ {n m : ā„•} (v : Vec A n) ā†’ (p : n ā‰” m) ā†’
76                toList (subst (Vec A) p v) ā‰” toList v
77 toList-subst v refl = refl
78
79 VecISetoid : Setoid ā„“ā‚€ ā„“ā‚€ ā†’ ISetoid ā„• ā„“ā‚€ ā„“ā‚€
80 VecISetoid S = record
81   { Carrier = Vec (Setoid.Carrier S)
82   ; _ā‰ˆ_ = Ī» x ā†’ S VecEq.ā‰ˆ x
83   ; isEquivalence = record
84     { refl = VecEq.refl S _
85     ; sym = VecEq.sym S
86     ; trans = VecEq.trans S }
87   }