diff options
| -rw-r--r-- | BFF.agda | 19 | ||||
| -rw-r--r-- | Bidir.agda | 31 | ||||
| -rw-r--r-- | Precond.agda | 11 |
3 files changed, 35 insertions, 26 deletions
@@ -2,7 +2,12 @@ module BFF where open import Data.Nat using (ℕ) open import Data.Fin using (Fin) +import Level +import Category.Monad +import Category.Functor open import Data.Maybe using (Maybe ; just ; nothing ; maybe′) +open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_) +open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_) open import Data.List using (List ; [] ; _∷_ ; map ; length) open import Data.Vec using (Vec ; toList ; fromList ; tabulate ; allFin) renaming (lookup to lookupV ; map to mapV ; [] to []V ; _∷_ to _∷V_) open import Function using (id ; _∘_ ; flip) @@ -12,12 +17,6 @@ open import FinMap import CheckInsert import FreeTheorems -_>>=_ : {A B : Set} → Maybe A → (A → Maybe B) → Maybe B -_>>=_ = flip (flip maybe′ nothing) - -fmap : {A B : Set} → (A → B) → Maybe A → Maybe B -fmap f = maybe′ (λ a → just (f a)) nothing - module ListBFF (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where open FreeTheorems.ListList public using (get-type) open CheckInsert Carrier deq @@ -37,8 +36,8 @@ module ListBFF (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where bff get s v = let s′ = enumerate s g = fromFunc (denumerate s) h = assoc (get s′) v - h′ = fmap (flip union g) h - in fmap (flip map s′ ∘ flip lookup) h′ + h′ = (flip union g) <$> h + in (flip map s′ ∘ flip lookup) <$> h′ module VecBFF (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where open FreeTheorems.VecVec public using (get-type) @@ -58,5 +57,5 @@ module VecBFF (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where bff get s v = let s′ = enumerate s g = fromFunc (denumerate s) h = assoc (get s′) v - h′ = fmap (flip union g) h - in fmap (flip mapV s′ ∘ flip lookupV) h′ + h′ = (flip union g) <$> h + in (flip mapV s′ ∘ flip lookupV) <$> h′ @@ -4,7 +4,12 @@ module Bidir (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where open import Data.Nat using (ℕ) open import Data.Fin using (Fin) +import Level +import Category.Monad +import Category.Functor open import Data.Maybe using (Maybe ; nothing ; just ; maybe′) +open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_) +open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_) open import Data.List using (List) open import Data.List.All using (All) open import Data.Vec using (Vec ; [] ; _∷_ ; toList ; map ; tabulate) renaming (lookup to lookupVec) @@ -20,13 +25,13 @@ open FreeTheorems.VecVec using (get-type ; free-theorem) open import FinMap import CheckInsert open CheckInsert Carrier deq -open import BFF using (_>>=_ ; fmap) +import BFF open BFF.VecBFF Carrier deq using (assoc ; enumerate ; denumerate ; bff) lemma-1 : {m n : ℕ} → (f : Fin n → Carrier) → (is : Vec (Fin n) m) → assoc is (map f is) ≡ just (restrict f (toList is)) lemma-1 f [] = refl lemma-1 f (i ∷ is′) = begin - assoc is′ (map f is′) >>= checkInsert i (f i) + (assoc is′ (map f is′) >>= checkInsert i (f i)) ≡⟨ cong (λ m → m >>= checkInsert i (f i)) (lemma-1 f is′) ⟩ checkInsert i (f i) (restrict f (toList is′)) ≡⟨ lemma-checkInsert-restrict f i (toList is′) ⟩ @@ -116,12 +121,12 @@ theorem-1 get s = begin just (map (denumerate s) (enumerate s)) ≡⟨ cong just (lemma-map-denumerate-enumerate s) ⟩ just s ∎ - where h↦h′ = fmap (flip union (fromFunc (denumerate s))) - h′↦r = fmap (flip map (enumerate s) ∘ flip lookupVec) + where h↦h′ = _<$>_ (flip union (fromFunc (denumerate s))) + h′↦r = _<$>_ (flip map (enumerate s) ∘ flip lookupVec) -lemma-fmap-just : {A B : Set} {f : A → B} {b : B} {ma : Maybe A} → fmap f ma ≡ just b → ∃ λ a → ma ≡ just a -lemma-fmap-just {ma = just x} fmap-f-ma≡just-b = x , refl -lemma-fmap-just {ma = nothing} () +lemma-<$>-just : {A B : Set} {f : A → B} {b : B} {ma : Maybe A} → f <$> ma ≡ just b → ∃ λ a → ma ≡ just a +lemma-<$>-just {ma = just x} f<$>ma≡just-b = x , refl +lemma-<$>-just {ma = nothing} () ∷-injective : {A : Set} {n : ℕ} {x y : A} {xs ys : Vec A n} → (x ∷ xs) ≡ (y ∷ ys) → x ≡ y × xs ≡ ys ∷-injective refl = refl , refl @@ -144,15 +149,15 @@ lemma-union-not-used h h' (i ∷ is') (All._∷_ (x , px) p') = cong₂ _∷_ (b (lemma-union-not-used h h' is' p') theorem-2 : {getlen : ℕ → ℕ} (get : get-type getlen) → {m : ℕ} → (v : Vec Carrier (getlen m)) → (s u : Vec Carrier m) → bff get s v ≡ just u → get u ≡ v -theorem-2 get v s u p with lemma-fmap-just (proj₂ (lemma-fmap-just p)) +theorem-2 get v s u p with lemma-<$>-just (proj₂ (lemma-<$>-just p)) theorem-2 get v s u p | h , ph = begin get u ≡⟨ just-injective (begin - fmap get (just u) - ≡⟨ cong (fmap get) (sym p) ⟩ - fmap get (bff get s v) - ≡⟨ cong (fmap get ∘ fmap h′↦r ∘ fmap h↦h′) ph ⟩ - fmap get (fmap h′↦r (fmap h↦h′ (just h))) ∎) ⟩ + get <$> (just u) + ≡⟨ cong (_<$>_ get) (sym p) ⟩ + get <$> (bff get s v) + ≡⟨ cong (_<$>_ get ∘ _<$>_ h′↦r ∘ _<$>_ h↦h′) ph ⟩ + get <$> (h′↦r <$> (h↦h′ <$> just h)) ∎) ⟩ get (map (flip lookup (h↦h′ h)) s′) ≡⟨ free-theorem get (flip lookup (h↦h′ h)) s′ ⟩ map (flip lookup (h↦h′ h)) (get s′) diff --git a/Precond.agda b/Precond.agda index f1b5e82..e4699dc 100644 --- a/Precond.agda +++ b/Precond.agda @@ -5,7 +5,12 @@ module Precond (Carrier : Set) (deq : Decidable {A = Carrier} _≡_) where open import Data.Nat using (ℕ) open import Data.Fin using (Fin) open import Data.List using (List ; [] ; _∷_) +import Level +import Category.Monad +import Category.Functor open import Data.Maybe using (nothing ; just) +open Category.Monad.RawMonad {Level.zero} Data.Maybe.monad using (_>>=_) +open Category.Functor.RawFunctor {Level.zero} Data.Maybe.functor using (_<$>_) open import Data.Vec using (Vec ; [] ; _∷_ ; map ; lookup ; toList) open import Data.List.Any using (here ; there) open Data.List.Any.Membership-≡ using (_∉_) @@ -18,13 +23,13 @@ open Relation.Binary.PropositionalEquality.≡-Reasoning using (begin_ ; _≡⟨ open import FinMap using (FinMap ; FinMapMaybe ; lookupM ; union ; fromFunc ; empty ; insert ; lemma-lookupM-empty) import CheckInsert open CheckInsert Carrier deq using (checkInsert ; lemma-checkInsert-new ; lemma-lookupM-checkInsert-other) -open import BFF using (fmap ; _>>=_) +import BFF import Bidir open BFF.VecBFF Carrier deq using (get-type ; assoc ; enumerate ; denumerate ; bff) assoc-enough : {getlen : ℕ → ℕ} (get : get-type getlen) → {m : ℕ} → (s : Vec Carrier m) → (v : Vec Carrier (getlen m)) → ∃ (λ h → assoc (get (enumerate s)) v ≡ just h) → ∃ λ u → bff get s v ≡ just u -assoc-enough get s v (h , p) = u , cong (fmap (flip map s′ ∘ flip lookup) ∘ (fmap (flip union g))) p +assoc-enough get s v (h , p) = u , cong (_<$>_ (flip map s′ ∘ flip lookup) ∘ (_<$>_ (flip union g))) p where s′ = enumerate s g = fromFunc (denumerate s) u = map (flip lookup (union h g)) s′ @@ -50,7 +55,7 @@ different-assoc (u ∷ us) (v ∷ vs) (different-∷ u∉us diff-us) with differ different-assoc (u ∷ us) (v ∷ vs) (different-∷ u∉us diff-us) | h , p' = insert u v h , (begin assoc (u ∷ us) (v ∷ vs) ≡⟨ refl ⟩ - assoc us vs >>= checkInsert u v + (assoc us vs >>= checkInsert u v) ≡⟨ cong (flip _>>=_ (checkInsert u v)) p' ⟩ checkInsert u v h ≡⟨ lemma-checkInsert-new u v h (lemma-∉-lookupM-assoc u us vs h p' u∉us) ⟩ |