Merge branch feature-partial-getlen into master
[~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 ; flip)
12 open import Function.Equality using (_⟢_)
13 open import Level using () renaming (zero to β„“β‚€)
14 open import Relation.Binary using (Setoid ; module Setoid)
15 open import Relation.Binary.Core using (_≑_ ; refl)
16 open import Relation.Binary.Indexed using (_at_) renaming (Setoid to ISetoid)
17 open import Relation.Binary.PropositionalEquality using (_β‰—_ ; cong ; subst ; trans ; congβ‚‚) renaming (setoid to EqSetoid)
18
19 open Setoid using () renaming (_β‰ˆ_ to _βˆ‹_β‰ˆ_)
20 open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_)
21 open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_)
22
23 ≑-to-Ξ  : {A B : Set} β†’ (A β†’ B) β†’ EqSetoid A βŸΆ EqSetoid B
24 ≑-to-Ξ  f = record { _⟨$⟩_ = f; cong = cong f }
25
26 just-injective : {A : Set} β†’ {x y : A} β†’ Maybe.just x β‰‘ Maybe.just y β†’ x β‰‘ y
27 just-injective refl = refl
28
29 length-replicate : {A : Set} {a : A} β†’ (n : β„•) β†’ length (replicate n a) β‰‘ n
30 length-replicate zero    = refl
31 length-replicate (suc n) = cong suc (length-replicate n)
32
33 mapMV : {A B : Set} {n : β„•} β†’ (A β†’ Maybe B) β†’ Vec A n β†’ Maybe (Vec B n)
34 mapMV f []V = just []V
35 mapMV f (x βˆ·V xs) = (f x) >>= (Ξ» y β†’ (_∷V_ y) <$> (mapMV f xs))
36
37 mapMV-cong : {A B : Set} {f g : A β†’ Maybe B} β†’ f β‰— g β†’ {n : β„•} β†’ mapMV {n = n} f β‰— mapMV g
38 mapMV-cong fβ‰—g []V       = refl
39 mapMV-cong fβ‰—g (x βˆ·V xs) = congβ‚‚ _>>=_ (fβ‰—g x) (cong (flip (_<$>_ βˆ˜ _∷V_)) (mapMV-cong fβ‰—g xs))
40
41 mapMV-purity : {A B : Set} {n : β„•} β†’ (f : A β†’ B) β†’ (v : Vec A n) β†’ mapMV (Maybe.just βˆ˜ f) v β‰‘ just (map f v)
42 mapMV-purity f []V       = refl
43 mapMV-purity f (x βˆ·V xs) = cong (_<$>_ (_∷V_ (f x))) (mapMV-purity f xs)
44
45 maybeEq-from-≑ : {A : Set} {a b : Maybe A} β†’ a β‰‘ b β†’ MaybeEq (EqSetoid A) βˆ‹ a β‰ˆ b
46 maybeEq-from-≑ {a = just x}  {b = .(just x)} refl = just refl
47 maybeEq-from-≑ {a = nothing} {b = .nothing}  refl = nothing
48
49 maybeEq-to-≑ : {A : Set} {a b : Maybe A} β†’ MaybeEq (EqSetoid A) βˆ‹ a β‰ˆ b β†’ a β‰‘ b
50 maybeEq-to-≑ (just refl) = refl
51 maybeEq-to-≑ nothing     = refl
52
53 sequenceV : {A : Set} {n : β„•} β†’ Vec (Maybe A) n β†’ Maybe (Vec A n)
54 sequenceV = mapMV id
55
56 sequence-map : {A B : Set} {n : β„•} β†’ (f : A β†’ Maybe B) β†’ sequenceV {n = n} βˆ˜ map f β‰— mapMV f
57 sequence-map f []V = refl
58 sequence-map f (x βˆ·V xs) with f x
59 sequence-map f (x βˆ·V xs) | just y = cong (_<$>_ (_∷V_ y)) (sequence-map f xs)
60 sequence-map f (x βˆ·V xs) | nothing = refl
61
62 subst-cong : {A : Set} β†’ (T : A β†’ Set) β†’ {g : A β†’ A} β†’ {a b : A} β†’ (f : {c : A} β†’ T c β†’ T (g c)) β†’ (p : a β‰‘ b) β†’
63              f βˆ˜ subst T p β‰— subst T (cong g p) βˆ˜ f
64 subst-cong T f refl _ = refl
65
66 subst-fromList : {A : Set} {x y : List A} β†’ (p : y β‰‘ x) β†’
67                  subst (Vec A) (cong length p) (fromList y) β‰‘ fromList x
68 subst-fromList refl = refl
69
70 subst-subst : {A : Set} (T : A β†’ Set) {a b c : A} β†’ (p : a β‰‘ b) β†’ (pβ€² : b β‰‘ c) β†’ (x : T a) β†’
71               subst T pβ€² (subst T p x) β‰‘ subst T (trans p pβ€²) x
72 subst-subst T refl pβ€² x = refl
73
74 toList-fromList : {A : Set} β†’ (l : List A) β†’ toList (fromList l) β‰‘ l
75 toList-fromList []L       = refl
76 toList-fromList (x βˆ·L xs) = cong (_∷L_ x) (toList-fromList xs)
77
78 toList-subst : {A : Set} β†’ {n m : β„•} (v : Vec A n) β†’ (p : n β‰‘ m) β†’
79                toList (subst (Vec A) p v) β‰‘ toList v
80 toList-subst v refl = refl
81
82 VecISetoid : Setoid β„“β‚€ β„“β‚€ β†’ ISetoid β„• β„“β‚€ β„“β‚€
83 VecISetoid S = record
84   { Carrier = Vec (Setoid.Carrier S)
85   ; _β‰ˆ_ = Ξ» x β†’ VecEq._β‰ˆ_ S x
86   ; isEquivalence = record
87     { refl = VecEq.refl S _
88     ; sym = VecEq.sym S
89     ; trans = VecEq.trans S }
90   }