|
0
|
1 module nat where
|
|
|
2
|
|
|
3 -- Monad
|
|
|
4 -- Category A
|
|
|
5 -- A = Category
|
|
22
|
6 -- Functor T : A → A
|
|
0
|
7 --T(a) = t(a)
|
|
|
8 --T(f) = tf(f)
|
|
|
9
|
|
2
|
10 open import Category -- https://github.com/konn/category-agda
|
|
0
|
11 open import Level
|
|
|
12 open Functor
|
|
|
13
|
|
1
|
14 --T(g f) = T(g) T(f)
|
|
|
15
|
|
22
|
16 Lemma1 : {c₁ c₂ l : Level} {A : Category c₁ c₂ l} (T : Functor A A) → {a b c : Obj A} {g : Hom A b c} { f : Hom A a b }
|
|
|
17 → A [ ( FMap T (A [ g o f ] )) ≈ (A [ FMap T g o FMap T f ]) ]
|
|
|
18 Lemma1 = \t → IsFunctor.distr ( isFunctor t )
|
|
0
|
19
|
|
|
20 -- F(f)
|
|
22
|
21 -- F(a) ---→ F(b)
|
|
0
|
22 -- | |
|
|
|
23 -- |t(a) |t(b) G(f)t(a) = t(b)F(f)
|
|
|
24 -- | |
|
|
|
25 -- v v
|
|
22
|
26 -- G(a) ---→ G(b)
|
|
0
|
27 -- G(f)
|
|
|
28
|
|
7
|
29 record IsNTrans {c₁ c₂ ℓ c₁′ c₂′ ℓ′ : Level} (D : Category c₁ c₂ ℓ) (C : Category c₁′ c₂′ ℓ′)
|
|
0
|
30 ( F G : Functor D C )
|
|
7
|
31 (Trans : (A : Obj D) → Hom C (FObj F A) (FObj G A))
|
|
0
|
32 : Set (suc (c₁ ⊔ c₂ ⊔ ℓ ⊔ c₁′ ⊔ c₂′ ⊔ ℓ′)) where
|
|
|
33 field
|
|
|
34 naturality : {a b : Obj D} {f : Hom D a b}
|
|
7
|
35 → C [ C [ ( FMap G f ) o ( Trans a ) ] ≈ C [ (Trans b ) o (FMap F f) ] ]
|
|
0
|
36 -- uniqness : {d : Obj D}
|
|
7
|
37 -- → C [ Trans d ≈ Trans d ]
|
|
0
|
38
|
|
|
39
|
|
7
|
40 record NTrans {c₁ c₂ ℓ c₁′ c₂′ ℓ′ : Level} (domain : Category c₁ c₂ ℓ) (codomain : Category c₁′ c₂′ ℓ′) (F G : Functor domain codomain )
|
|
0
|
41 : Set (suc (c₁ ⊔ c₂ ⊔ ℓ ⊔ c₁′ ⊔ c₂′ ⊔ ℓ′)) where
|
|
|
42 field
|
|
7
|
43 Trans : (A : Obj domain) → Hom codomain (FObj F A) (FObj G A)
|
|
|
44 isNTrans : IsNTrans domain codomain F G Trans
|
|
0
|
45
|
|
7
|
46 open NTrans
|
|
1
|
47 Lemma2 : {c₁ c₂ l : Level} {A : Category c₁ c₂ l} {F G : Functor A A}
|
|
22
|
48 → (μ : NTrans A A F G) → {a b : Obj A} { f : Hom A a b }
|
|
|
49 → A [ A [ FMap G f o Trans μ a ] ≈ A [ Trans μ b o FMap F f ] ]
|
|
|
50 Lemma2 = \n → IsNTrans.naturality ( isNTrans n )
|
|
0
|
51
|
|
|
52 open import Category.Cat
|
|
|
53
|
|
22
|
54 -- η : 1_A → T
|
|
|
55 -- μ : TT → T
|
|
0
|
56 -- μ(a)η(T(a)) = a
|
|
|
57 -- μ(a)T(η(a)) = a
|
|
|
58 -- μ(a)(μ(T(a))) = μ(a)T(μ(a))
|
|
|
59
|
|
1
|
60 record IsMonad {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ)
|
|
|
61 ( T : Functor A A )
|
|
7
|
62 ( η : NTrans A A identityFunctor T )
|
|
|
63 ( μ : NTrans A A (T ○ T) T)
|
|
1
|
64 : Set (suc (c₁ ⊔ c₂ ⊔ ℓ )) where
|
|
|
65 field
|
|
22
|
66 assoc : {a : Obj A} → A [ A [ Trans μ a o Trans μ ( FObj T a ) ] ≈ A [ Trans μ a o FMap T (Trans μ a) ] ]
|
|
|
67 unity1 : {a : Obj A} → A [ A [ Trans μ a o Trans η ( FObj T a ) ] ≈ Id {_} {_} {_} {A} (FObj T a) ]
|
|
|
68 unity2 : {a : Obj A} → A [ A [ Trans μ a o (FMap T (Trans η a ))] ≈ Id {_} {_} {_} {A} (FObj T a) ]
|
|
0
|
69
|
|
7
|
70 record Monad {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ) (T : Functor A A) (η : NTrans A A identityFunctor T) (μ : NTrans A A (T ○ T) T)
|
|
1
|
71 : Set (suc (c₁ ⊔ c₂ ⊔ ℓ )) where
|
|
7
|
72 eta : NTrans A A identityFunctor T
|
|
6
|
73 eta = η
|
|
7
|
74 mu : NTrans A A (T ○ T) T
|
|
6
|
75 mu = μ
|
|
1
|
76 field
|
|
|
77 isMonad : IsMonad A T η μ
|
|
0
|
78
|
|
2
|
79 open Monad
|
|
|
80 Lemma3 : {c₁ c₂ ℓ : Level} {A : Category c₁ c₂ ℓ}
|
|
|
81 { T : Functor A A }
|
|
7
|
82 { η : NTrans A A identityFunctor T }
|
|
|
83 { μ : NTrans A A (T ○ T) T }
|
|
22
|
84 { a : Obj A } →
|
|
2
|
85 ( M : Monad A T η μ )
|
|
22
|
86 → A [ A [ Trans μ a o Trans μ ( FObj T a ) ] ≈ A [ Trans μ a o FMap T (Trans μ a) ] ]
|
|
|
87 Lemma3 = \m → IsMonad.assoc ( isMonad m )
|
|
2
|
88
|
|
|
89
|
|
|
90 Lemma4 : {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ) {a b : Obj A } { f : Hom A a b}
|
|
22
|
91 → A [ A [ Id {_} {_} {_} {A} b o f ] ≈ f ]
|
|
|
92 Lemma4 = \a → IsCategory.identityL ( Category.isCategory a )
|
|
0
|
93
|
|
3
|
94 Lemma5 : {c₁ c₂ ℓ : Level} {A : Category c₁ c₂ ℓ}
|
|
|
95 { T : Functor A A }
|
|
7
|
96 { η : NTrans A A identityFunctor T }
|
|
|
97 { μ : NTrans A A (T ○ T) T }
|
|
22
|
98 { a : Obj A } →
|
|
3
|
99 ( M : Monad A T η μ )
|
|
22
|
100 → A [ A [ Trans μ a o Trans η ( FObj T a ) ] ≈ Id {_} {_} {_} {A} (FObj T a) ]
|
|
|
101 Lemma5 = \m → IsMonad.unity1 ( isMonad m )
|
|
3
|
102
|
|
|
103 Lemma6 : {c₁ c₂ ℓ : Level} {A : Category c₁ c₂ ℓ}
|
|
|
104 { T : Functor A A }
|
|
7
|
105 { η : NTrans A A identityFunctor T }
|
|
|
106 { μ : NTrans A A (T ○ T) T }
|
|
22
|
107 { a : Obj A } →
|
|
3
|
108 ( M : Monad A T η μ )
|
|
22
|
109 → A [ A [ Trans μ a o (FMap T (Trans η a )) ] ≈ Id {_} {_} {_} {A} (FObj T a) ]
|
|
|
110 Lemma6 = \m → IsMonad.unity2 ( isMonad m )
|
|
3
|
111
|
|
|
112 -- T = M x A
|
|
0
|
113 -- nat of η
|
|
|
114 -- g ○ f = μ(c) T(g) f
|
|
|
115 -- η(b) ○ f = f
|
|
|
116 -- f ○ η(a) = f
|
|
22
|
117 -- h ○ (g ○ f) = (h ○ g) ○ f
|
|
0
|
118
|
|
4
|
119 record Kleisli { c₁ c₂ ℓ : Level} ( A : Category c₁ c₂ ℓ )
|
|
|
120 ( T : Functor A A )
|
|
7
|
121 ( η : NTrans A A identityFunctor T )
|
|
|
122 ( μ : NTrans A A (T ○ T) T )
|
|
4
|
123 ( M : Monad A T η μ ) : Set (suc (c₁ ⊔ c₂ ⊔ ℓ )) where
|
|
5
|
124 monad : Monad A T η μ
|
|
|
125 monad = M
|
|
22
|
126 -- g ○ f = μ(c) T(g) f
|
|
|
127 join : { a b : Obj A } → ( c : Obj A ) →
|
|
|
128 ( Hom A b ( FObj T c )) → ( Hom A a ( FObj T b)) → Hom A a ( FObj T c )
|
|
7
|
129 join c g f = A [ Trans μ c o A [ FMap T g o f ] ]
|
|
|
130
|
|
10
|
131
|
|
7
|
132
|
|
18
|
133 module ≈-Reasoning {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ) where
|
|
22
|
134 open import Relation.Binary.Core renaming ( Trans to Trasn1 )
|
|
7
|
135
|
|
18
|
136 refl-hom : {a b : Obj A } { x : Hom A a b } →
|
|
|
137 A [ x ≈ x ]
|
|
|
138 refl-hom = IsEquivalence.refl (IsCategory.isEquivalence ( Category.isCategory A ))
|
|
8
|
139
|
|
18
|
140 trans-hom : {a b : Obj A }
|
|
|
141 { x y z : Hom A a b } →
|
|
|
142 A [ x ≈ y ] → A [ y ≈ z ] → A [ x ≈ z ]
|
|
|
143 trans-hom b c = ( IsEquivalence.trans (IsCategory.isEquivalence ( Category.isCategory A ))) b c
|
|
5
|
144
|
|
22
|
145 -- some short cuts
|
|
|
146
|
|
|
147 car-eq : {a b c : Obj A } {x y : Hom A a b } ( f : Hom A c a ) →
|
|
|
148 A [ x ≈ y ] → A [ A [ x o f ] ≈ A [ y o f ] ]
|
|
|
149 car-eq f eq = ( IsCategory.o-resp-≈ ( Category.isCategory A )) ( refl-hom ) eq
|
|
|
150
|
|
|
151 cdr-eq : {a b c : Obj A } {x y : Hom A a b } ( f : Hom A b c ) →
|
|
|
152 A [ x ≈ y ] → A [ A [ f o x ] ≈ A [ f o y ] ]
|
|
|
153 cdr-eq f eq = ( IsCategory.o-resp-≈ ( Category.isCategory A )) eq (refl-hom )
|
|
|
154
|
|
|
155 id : (a : Obj A ) → Hom A a a
|
|
|
156 id a = (Id {_} {_} {_} {A} a)
|
|
|
157
|
|
|
158 idL : {a b : Obj A } { f : Hom A b a } → A [ A [ id a o f ] ≈ f ]
|
|
|
159 idL = IsCategory.identityL (Category.isCategory A)
|
|
|
160
|
|
|
161 idR : {a b : Obj A } { f : Hom A a b } → A [ A [ f o id a ] ≈ f ]
|
|
|
162 idR = IsCategory.identityR (Category.isCategory A)
|
|
|
163
|
|
|
164 assoc : {a b c d : Obj A } {f : Hom A c d} {g : Hom A b c} {h : Hom A a b}
|
|
|
165 → A [ A [ f o A [ g o h ] ] ≈ A [ A [ f o g ] o h ] ]
|
|
|
166 assoc = IsCategory.associative (Category.isCategory A)
|
|
|
167
|
|
|
168 distr : (T : Functor A A) → {a b c : Obj A} {g : Hom A b c} { f : Hom A a b }
|
|
|
169 → A [ ( FMap T (A [ g o f ] )) ≈ (A [ FMap T g o FMap T f ]) ]
|
|
|
170 distr t = IsFunctor.distr ( isFunctor t )
|
|
|
171
|
|
|
172 nat : { c₁′ c₂′ ℓ′ : Level} (D : Category c₁′ c₂′ ℓ′) {a b : Obj D} {f : Hom D a b} {F G : Functor D A }
|
|
|
173 → (η : NTrans D A F G )
|
|
|
174 → A [ A [ ( FMap G f ) o ( Trans η a ) ] ≈ A [ (Trans η b ) o (FMap F f) ] ]
|
|
|
175 nat _ η = IsNTrans.naturality ( isNTrans η )
|
|
|
176
|
|
18
|
177 infixr 2 _∎
|
|
|
178 infixr 2 _≈⟨_⟩_
|
|
|
179 infix 1 begin_
|
|
7
|
180
|
|
12
|
181
|
|
18
|
182 data _IsRelatedTo_ { a b : Obj A } ( x y : Hom A a b ) :
|
|
|
183 Set (suc (c₁ ⊔ c₂ ⊔ ℓ )) where
|
|
|
184 relTo : (x≈y : A [ x ≈ y ] ) → x IsRelatedTo y
|
|
17
|
185
|
|
18
|
186 begin_ : { a b : Obj A } { x y : Hom A a b } →
|
|
|
187 x IsRelatedTo y → A [ x ≈ y ]
|
|
|
188 begin relTo x≈y = x≈y
|
|
17
|
189
|
|
18
|
190 _≈⟨_⟩_ : { a b : Obj A } ( x : Hom A a b ) → { y z : Hom A a b } →
|
|
|
191 A [ x ≈ y ] → y IsRelatedTo z → x IsRelatedTo z
|
|
|
192 _ ≈⟨ x≈y ⟩ relTo y≈z = relTo (trans-hom x≈y y≈z)
|
|
17
|
193
|
|
18
|
194 _∎ : { a b : Obj A } ( x : Hom A a b ) → x IsRelatedTo x
|
|
|
195 _∎ _ = relTo refl-hom
|
|
17
|
196
|
|
22
|
197 lemma12 : {c₁ c₂ ℓ : Level} (L : Category c₁ c₂ ℓ) { a b c : Obj L } →
|
|
|
198 ( x : Hom L c a ) → ( y : Hom L b c ) → L [ L [ x o y ] ≈ L [ x o y ] ]
|
|
18
|
199 lemma12 L x y =
|
|
|
200 let open ≈-Reasoning ( L ) in
|
|
|
201 begin L [ x o y ] ∎
|
|
11
|
202
|
|
22
|
203 Lemma61 : {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ) →
|
|
|
204 { a : Obj A } ( b : Obj A ) →
|
|
17
|
205 ( f : Hom A a b )
|
|
22
|
206 → A [ A [ (Id {_} {_} {_} {A} b) o f ] ≈ f ]
|
|
18
|
207 Lemma61 c b g = -- IsCategory.identityL (Category.isCategory c)
|
|
|
208 let open ≈-Reasoning (c) in
|
|
17
|
209 begin
|
|
18
|
210 c [ Id {_} {_} {_} {c} b o g ]
|
|
|
211 ≈⟨ IsCategory.identityL (Category.isCategory c) ⟩
|
|
17
|
212 g
|
|
|
213 ∎
|
|
11
|
214
|
|
4
|
215 open Kleisli
|
|
22
|
216 -- η(b) ○ f = f
|
|
|
217 Lemma7 : {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ) →
|
|
21
|
218 ( T : Functor A A )
|
|
|
219 ( η : NTrans A A identityFunctor T )
|
|
7
|
220 { μ : NTrans A A (T ○ T) T }
|
|
21
|
221 { a : Obj A } ( b : Obj A )
|
|
|
222 ( f : Hom A a ( FObj T b) )
|
|
22
|
223 ( m : Monad A T η μ )
|
|
|
224 ( k : Kleisli A T η μ m)
|
|
|
225 → A [ join k b (Trans η b) f ≈ f ]
|
|
21
|
226 Lemma7 c T η b f m k =
|
|
|
227 let open ≈-Reasoning (c)
|
|
|
228 μ = mu ( monad k )
|
|
|
229 in
|
|
|
230 begin
|
|
|
231 join k b (Trans η b) f
|
|
|
232 ≈⟨ refl-hom ⟩
|
|
|
233 c [ Trans μ b o c [ FMap T ((Trans η b)) o f ] ]
|
|
|
234 ≈⟨ IsCategory.associative (Category.isCategory c) ⟩
|
|
|
235 c [ c [ Trans μ b o FMap T ((Trans η b)) ] o f ]
|
|
22
|
236 ≈⟨ car-eq f ( IsMonad.unity2 ( isMonad ( monad k )) ) ⟩
|
|
|
237 c [ id (FObj T b) o f ]
|
|
21
|
238 ≈⟨ IsCategory.identityL (Category.isCategory c) ⟩
|
|
|
239 f
|
|
|
240 ∎
|
|
7
|
241
|
|
22
|
242 -- f ○ η(a) = f
|
|
|
243 Lemma8 : {c₁ c₂ ℓ : Level} (A : Category c₁ c₂ ℓ)
|
|
|
244 ( T : Functor A A )
|
|
|
245 ( η : NTrans A A identityFunctor T )
|
|
7
|
246 { μ : NTrans A A (T ○ T) T }
|
|
22
|
247 ( a : Obj A ) ( b : Obj A )
|
|
|
248 ( f : Hom A a ( FObj T b) )
|
|
|
249 ( m : Monad A T η μ )
|
|
|
250 ( k : Kleisli A T η μ m)
|
|
|
251 → A [ join k b f (Trans η a) ≈ f ]
|
|
|
252 Lemma8 c T η a b f m k =
|
|
|
253 begin
|
|
|
254 join k b f (Trans η a)
|
|
|
255 ≈⟨ refl-hom ⟩
|
|
|
256 c [ Trans μ b o c [ FMap T f o (Trans η a) ] ]
|
|
|
257 ≈⟨ cdr-eq (Trans μ b) ( IsNTrans.naturality ( isNTrans η )) ⟩
|
|
|
258 c [ Trans μ b o c [ (Trans η ( FObj T b)) o f ] ]
|
|
|
259 ≈⟨ IsCategory.associative (Category.isCategory c) ⟩
|
|
|
260 c [ c [ Trans μ b o (Trans η ( FObj T b)) ] o f ]
|
|
|
261 ≈⟨ car-eq f ( IsMonad.unity1 ( isMonad ( monad k )) ) ⟩
|
|
|
262 c [ id (FObj T b) o f ]
|
|
|
263 ≈⟨ IsCategory.identityL (Category.isCategory c) ⟩
|
|
|
264 f
|
|
|
265 ∎ where
|
|
|
266 open ≈-Reasoning (c)
|
|
|
267 μ = mu ( monad k )
|
|
5
|
268
|
|
22
|
269 -- h ○ (g ○ f) = (h ○ g) ○ f
|
|
5
|
270 Lemma9 : {c₁ c₂ ℓ : Level} {A : Category c₁ c₂ ℓ}
|
|
|
271 { T : Functor A A }
|
|
7
|
272 { η : NTrans A A identityFunctor T }
|
|
|
273 { μ : NTrans A A (T ○ T) T }
|
|
5
|
274 { a b c d : Obj A }
|
|
|
275 { f : Hom A a ( FObj T b) }
|
|
|
276 { g : Hom A b ( FObj T c) }
|
|
|
277 { h : Hom A c ( FObj T d) }
|
|
22
|
278 { m : Monad A T η μ }
|
|
|
279 ( k : Kleisli A T η μ m)
|
|
|
280 → A [ join k d h (join k c g f) ≈ join k d ( join k d h g) f ]
|
|
6
|
281 Lemma9 k = {!!}
|
|
5
|
282
|
|
4
|
283
|
|
3
|
284
|
|
|
285
|
|
|
286
|
|
|
287 -- Kleisli :
|
|
|
288 -- Kleisli = record { Hom =
|
|
|
289 -- ; Hom = _⟶_
|
|
|
290 -- ; Id = IdProd
|
|
|
291 -- ; _o_ = _∘_
|
|
|
292 -- ; _≈_ = _≈_
|
|
|
293 -- ; isCategory = record { isEquivalence = record { refl = λ {φ} → ≈-refl {φ = φ}
|
|
|
294 -- ; sym = λ {φ ψ} → ≈-symm {φ = φ} {ψ}
|
|
|
295 -- ; trans = λ {φ ψ σ} → ≈-trans {φ = φ} {ψ} {σ}
|
|
|
296 -- }
|
|
|
297 -- ; identityL = identityL
|
|
|
298 -- ; identityR = identityR
|
|
|
299 -- ; o-resp-≈ = o-resp-≈
|
|
|
300 -- ; associative = associative
|
|
|
301 -- }
|
|
|
302 -- }
|
