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.PropositionalEquality using (_≗_ ; cong ; subst ; trans) renaming (setoid to PropEq)
  16
  17 open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_)
  18 open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_)
  19
  20 ∷-injective : {A : Set} {n : ℕ} {x y : A} {xs ys : Vec A n} →
  21               (x ∷V xs) ≡ (y ∷V ys) → x ≡ y × xs ≡ ys
  22 ∷-injective refl = refl , refl
  23
  24 just-injective : {A : Set} → {x y : A} → Maybe.just x ≡ Maybe.just y → x ≡ y
  25 just-injective refl = refl
  26
  27 length-replicate : {A : Set} {a : A} → (n : ℕ) → length (replicate n a) ≡ n
  28 length-replicate zero       = refl
  29 length-replicate (suc n) = cong suc (length-replicate n)
  30
  31 map-just-injective : {A : Set} {n : ℕ} {xs ys : Vec A n} →
  32                      map Maybe.just xs ≡ map Maybe.just ys → xs ≡ ys
  33 map-just-injective {xs = []V}      {ys = []V}       p  = refl
  34 map-just-injective {xs = x ∷V xs′} {ys = y ∷V ys′}  p with ∷-injective p
  35 map-just-injective {xs = x ∷V xs′} {ys = .x ∷V ys′} p | refl , p′ = cong (_∷V_ x) (map-just-injective p′)
  36
  37 mapMV : {A B : Set} {n : ℕ} → (A → Maybe B) → Vec A n → Maybe (Vec B n)
  38 mapMV f []V = just []V
  39 mapMV f (x ∷V xs) = (f x) >>= (λ y → (_∷V_ y) <$> (mapMV f xs))
  40
  41 mapMV-cong : {A B : Set} {f g : A → Maybe B} → f ≗ g → {n : ℕ} → mapMV {n = n} f ≗ mapMV g
  42 mapMV-cong f≗g []V = refl
  43 mapMV-cong {f = f} {g = g} f≗g (x ∷V xs) with f x | g x | f≗g x
  44 mapMV-cong f≗g (x ∷V xs) | just y | .(just y) | refl = cong (_<$>_ (_∷V_ y)) (mapMV-cong f≗g xs)
  45 mapMV-cong f≗g (x ∷V xs) | nothing | .nothing | refl = refl
  46
  47 mapMV-purity : {A B : Set} {n : ℕ} → (f : A → B) → (v : Vec A n) → mapMV (just ∘ f) v ≡ just (map f v)
  48 mapMV-purity f []V = refl
  49 mapMV-purity f (x ∷V xs) rewrite mapMV-purity f xs = refl
  50
  51 maybeEq-from-≡ : {A : Set} {a b : Maybe A} → Setoid._≈_ (PropEq (Maybe A)) a b → Setoid._≈_ (MaybeEq (PropEq A)) a b
  52 maybeEq-from-≡ {a = just x}  {b = .(just x)} refl = just refl
  53 maybeEq-from-≡ {a = nothing} {b = .nothing}  refl = nothing
  54
  55 maybeEq-to-≡ : {A : Set} {a b : Maybe A} → Setoid._≈_ (MaybeEq (PropEq A)) a b → Setoid._≈_ (PropEq (Maybe A)) a b
  56 maybeEq-to-≡ (just refl) = refl
  57 maybeEq-to-≡ 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 vecIsSetoid : Setoid ℓ₀ ℓ₀ → ℕ → Setoid ℓ₀ ℓ₀
  80 vecIsSetoid S n = record
  81   { Carrier       = Vec S.Carrier n
  82   ; _≈_           = λ x y → VecEq._≈_ S {n} x {n} y
  83   ; isEquivalence = record
  84     { refl = VecEq.refl S _
  85     ; sym = VecEq.sym S
  86     ; trans = VecEq.trans S }
  87   }
  88   where
  89   module S = Setoid S