import _>>=_ and fmap from Data.Maybe
authorHelmut Grohne <helmut@subdivi.de>
Sun, 21 Jul 2013 18:46:18 +0000 (20:46 +0200)
committerHelmut Grohne <helmut@subdivi.de>
Sun, 21 Jul 2013 18:46:18 +0000 (20:46 +0200)
Also rename fmap to _<$>_ to match Agda naming conventions. The imported
_>>=_ appears to have different binding, so some braces were necessary.

BFF.agda
Bidir.agda
Precond.agda

index 2888a3d..cbb36d3 100644 (file)
--- a/BFF.agda
+++ b/BFF.agda
@@ -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′
index f9ac91f..e4a615a 100644 (file)
@@ -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′)
index f1b5e82..e4699dc 100644 (file)
@@ -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) ⟩