### comparison agda/deltaM/monad.agda @ 115:e6bcc7467335

Temporary commit : Proving association-law ...
author Yasutaka Higa Sun, 01 Feb 2015 17:06:55 +0900 08403eb8db8b f02c5ad4a327
comparison
equal inserted replaced
114:08403eb8db8b 115:e6bcc7467335
34 fmap-tailDeltaM-with-deltaM-eta {n = S n} d = refl 34 fmap-tailDeltaM-with-deltaM-eta {n = S n} d = refl
35 35
36 36
37 -- main proofs 37 -- main proofs
38 38
39 deltaM-eta-is-nt : {l : Level} {A B : Set l} {n : Nat} 39 postulate deltaM-eta-is-nt : {l : Level} {A B : Set l} {n : Nat}
40 {M : Set l -> Set l} {functorM : Functor M} {monadM : Monad M functorM} 40 {M : Set l -> Set l} {functorM : Functor M} {monadM : Monad M functorM}
41 (f : A -> B) -> (x : A) -> 41 (f : A -> B) -> (x : A) ->
42 ((deltaM-eta {l} {B} {n} {M} {functorM} {monadM} )∙ f) x ≡ deltaM-fmap f (deltaM-eta x) 42 ((deltaM-eta {l} {B} {n} {M} {functorM} {monadM} )∙ f) x ≡ deltaM-fmap f (deltaM-eta x)
43 {-
43 deltaM-eta-is-nt {l} {A} {B} {O} {M} {fm} {mm} f x = begin 44 deltaM-eta-is-nt {l} {A} {B} {O} {M} {fm} {mm} f x = begin
44 deltaM-eta {n = O} (f x) ≡⟨ refl ⟩ 45 deltaM-eta {n = O} (f x) ≡⟨ refl ⟩
45 deltaM (mono (eta mm (f x))) ≡⟨ cong (\de -> deltaM (mono de)) (eta-is-nt mm f x) ⟩ 46 deltaM (mono (eta mm (f x))) ≡⟨ cong (\de -> deltaM (mono de)) (eta-is-nt mm f x) ⟩
46 deltaM (mono (fmap fm f (eta mm x))) ≡⟨ refl ⟩ 47 deltaM (mono (fmap fm f (eta mm x))) ≡⟨ refl ⟩
47 deltaM-fmap f (deltaM-eta {n = O} x) ∎ 48 deltaM-fmap f (deltaM-eta {n = O} x) ∎
54 ≡⟨ cong (\de -> deltaM (delta (fmap fm f (eta mm x)) de)) (eta-is-nt delta-is-monad (fmap fm f) (eta mm x)) ⟩ 55 ≡⟨ cong (\de -> deltaM (delta (fmap fm f (eta mm x)) de)) (eta-is-nt delta-is-monad (fmap fm f) (eta mm x)) ⟩
55 deltaM (delta (fmap fm f (eta mm x)) (delta-fmap (fmap fm f) (delta-eta (eta mm x)))) 56 deltaM (delta (fmap fm f (eta mm x)) (delta-fmap (fmap fm f) (delta-eta (eta mm x))))
56 ≡⟨ refl ⟩ 57 ≡⟨ refl ⟩
57 deltaM-fmap f (deltaM-eta {n = S n} x) 58 deltaM-fmap f (deltaM-eta {n = S n} x)
58 59
60 -}
59 61
60 postulate deltaM-right-unity-law : {l : Level} {A : Set l} 62 postulate deltaM-right-unity-law : {l : Level} {A : Set l}
61 {M : Set l -> Set l} {functorM : Functor M} {monadM : Monad M functorM} {n : Nat} 63 {M : Set l -> Set l} {functorM : Functor M} {monadM : Monad M functorM} {n : Nat}
62 (d : DeltaM M {functorM} {monadM} A (S n)) -> (deltaM-mu ∙ deltaM-eta) d ≡ id d 64 (d : DeltaM M {functorM} {monadM} A (S n)) -> (deltaM-mu ∙ deltaM-eta) d ≡ id d
63 {- 65 {-
166 168
167 169
168 -} 170 -}
169 171
170 172
173 fmap-headDeltaM-with-deltaM-mu : {l : Level} {A : Set l} {n : Nat}
174 {M : Set l -> Set l} {fm : Functor M} {mm : Monad M fm}
175 (x : M (DeltaM M {fm} {mm} (DeltaM M {fm} {mm} A (S n)) (S n))) ->
176 -- (fmap fm headDeltaM (fmap fm deltaM-mu x)) ≡ (fmap fm headDeltaM (mu mm (fmap fm headDeltaM x)))
177 -- fmap fm (headDeltaM ∙ deltaM-mu) x ≡ fmap fm (fmap fm ((mu mm) ∙ (fmap fm headDeltaM))) x
178 headDeltaM (deltaM-fmap deltaM-mu (deltaM (mono x))) ≡ deltaM (mono (mu mm (fmap fm headDeltaM x)))
179 fmap-headDeltaM-with-deltaM-mu {l} {A} {O} {M} {fm} {mm} x = {!!}
180 fmap-headDeltaM-with-deltaM-mu {n = S n} x = {!!}
181
182 deltaM-mono : {l : Level} {A : Set l}
183 {M : Set l -> Set l} {fm : Functor M} {mm : Monad M fm}
184 (d : M A) -> DeltaM M {fm} {mm} A (S O)
185 deltaM-mono x = deltaM (mono x)
186
187 fmap-headDeltaM-with-deltaM-mono : {l : Level} {A : Set l}
188 {M : Set l -> Set l} {fm : Functor M} {mm : Monad M fm}
189 (x : M (M A)) ->
190 fmap fm ((headDeltaM {l} {A} {O} {M} {fm} {mm}) ∙ deltaM-mono) x ≡ x
191 fmap-headDeltaM-with-deltaM-mono {fm = fm} x = preserve-id fm x
192
193
194
195
196 deltaM-association-law : {l : Level} {A : Set l} {n : Nat}
197 (M : Set l -> Set l) (fm : Functor M) (mm : Monad M fm)
198 (d : DeltaM M {fm} {mm} (DeltaM M {fm} {mm} (DeltaM M {fm} {mm} A (S n)) (S n)) (S n)) ->
199 deltaM-mu (deltaM-fmap deltaM-mu d) ≡ deltaM-mu (deltaM-mu d)
200 deltaM-association-law {l} {A} {O} M fm mm (deltaM (mono x)) = begin
201 deltaM-mu (deltaM-fmap deltaM-mu (deltaM (mono x))) ≡⟨ refl ⟩
202 deltaM-mu (deltaM (mono (fmap fm deltaM-mu x))) ≡⟨ refl ⟩
203 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm deltaM-mu x)))) ≡⟨ refl ⟩
204 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm (\x -> (deltaM (mono (mu mm (fmap fm headDeltaM (headDeltaM x)))))) x)))) ≡⟨ refl ⟩
205
206 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm (\x -> (deltaM-mono (mu mm (fmap fm headDeltaM (headDeltaM x))))) x)))) ≡⟨ refl ⟩
207 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm (deltaM-mono ∙ (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x))))) x)))) ≡⟨ refl ⟩
208 deltaM (mono (mu mm (fmap fm headDeltaM (((fmap fm (deltaM-mono)) ∙ (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))))) x)))) ≡⟨ refl ⟩
209 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm deltaM-mono (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x)))))
210 ≡⟨ cong (\de -> deltaM (mono (mu mm de))) (sym (covariant fm deltaM-mu headDeltaM x )) ⟩
211
212 deltaM (mono (mu mm (fmap fm (headDeltaM ∙ deltaM-mono) ((fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x))))) x))))
213 ≡⟨ cong (\de -> deltaM (mono (mu mm de))) (fmap-headDeltaM-with-deltaM-mono ((fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x))))) x)) ⟩
214
215 deltaM (mono (mu mm (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x))) ≡⟨ refl ⟩
216
217
218
219 {-
220 {!!}
221
222
223
224 deltaM (mono (mu mm (fmap fm (headDeltaM) (fmap fm
225 (\x -> ((deltaM (mono (mu mm (fmap fm (headDeltaM {l} {A} {O} {M} {fm} {mm} )(headDeltaM {l} {DeltaM M {fm} {mm} A (S O)} {O} {M} {fm} {mm} x))))))) x)))) ≡⟨ refl ⟩
226 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm (\x -> ((deltaM-mono (mu mm (fmap fm headDeltaM (headDeltaM x)))))) x)))) ≡⟨ refl ⟩
227
228 deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm (deltaM-mono ∙ (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x))))) x)))) ≡⟨ refl ⟩
229 deltaM (mono (mu mm (fmap fm headDeltaM (((fmap fm deltaM-mono) ∙ (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))))) x)))) ≡⟨ refl ⟩
230 deltaM (mono (mu mm (fmap fm headDeltaM (((fmap fm deltaM-mono (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x))))))) ≡⟨ refl ⟩
231 deltaM (mono (mu mm (fmap fm (headDeltaM ∙ deltaM-mono) (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x))))
232 ≡⟨ {!!} ⟩
233 -- ≡⟨ cong (\de -> deltaM (mono (mu mm de))) (fmap-headDeltaM-with-deltaM-eta (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x)) ⟩
234 -}
235 deltaM (mono (mu mm (fmap fm (\x -> (mu mm (fmap fm headDeltaM (headDeltaM x)))) x))) ≡⟨ refl ⟩
236 deltaM (mono (mu mm (fmap fm ((mu mm) ∙ (\x -> (fmap fm headDeltaM (headDeltaM x)))) x))) ≡⟨ refl ⟩
237 deltaM (mono (mu mm (fmap fm ((mu mm) ∙ ((fmap fm headDeltaM) ∙ headDeltaM)) x)))
238 ≡⟨ cong (\de -> deltaM (mono (mu mm de))) (covariant fm ((fmap fm headDeltaM) ∙ headDeltaM) (mu mm) x) ⟩
239 deltaM (mono (mu mm (((fmap fm (mu mm)) ∙ (fmap fm ((fmap fm headDeltaM) ∙ headDeltaM))) x)))
240 ≡⟨ refl ⟩
241 deltaM (mono (mu mm (fmap fm (mu mm) ((fmap fm ((fmap fm headDeltaM) ∙ headDeltaM) x))) ))
242 ≡⟨ cong (\de -> deltaM (mono (mu mm (fmap fm (mu mm) de)))) (covariant fm headDeltaM (fmap fm headDeltaM) x) ⟩
243 deltaM (mono (mu mm (fmap fm (mu mm) (fmap fm (fmap fm headDeltaM) (fmap fm headDeltaM x)))))
244 ≡⟨ cong (\de -> deltaM (mono de)) (association-law mm (fmap fm (fmap fm headDeltaM) (fmap fm headDeltaM x))) ⟩
245 deltaM (mono (mu mm (mu mm (fmap fm (fmap fm headDeltaM) (fmap fm headDeltaM x)))))
246 ≡⟨ cong (\de -> deltaM (mono (mu mm de))) (mu-is-nt mm headDeltaM (fmap fm headDeltaM x)) ⟩
247 deltaM (mono (mu mm (fmap fm headDeltaM (mu mm (fmap fm headDeltaM x))))) ≡⟨ refl ⟩
248 deltaM-mu (deltaM (mono (mu mm (fmap fm headDeltaM x)))) ≡⟨ refl ⟩
249 deltaM-mu (deltaM-mu (deltaM (mono x)))
250
251 deltaM-association-law {n = S n} M fm mm (deltaM (delta x d)) = begin
252 deltaM-mu (deltaM-fmap deltaM-mu (deltaM (delta x d))) ≡⟨ refl ⟩
253 deltaM-mu (deltaM (delta-fmap (fmap fm deltaM-mu) (delta x d))) ≡⟨ refl ⟩
254 deltaM-mu (deltaM (delta (fmap fm deltaM-mu x) (delta-fmap (fmap fm deltaM-mu) d))) ≡⟨ refl ⟩
255 appendDeltaM (deltaM (mono (mu mm (fmap fm headDeltaM (fmap fm deltaM-mu x)))))
256 (deltaM-mu (deltaM-fmap tailDeltaM (deltaM (delta-fmap (fmap fm deltaM-mu) d)))) ≡⟨ {!!} ⟩
257
258 appendDeltaM (deltaM (mono (mu mm (fmap fm headDeltaM (mu mm (fmap fm headDeltaM x))))))
259 (deltaM-mu (deltaM-fmap tailDeltaM (deltaM-mu (deltaM-fmap tailDeltaM (deltaM d))))) ≡⟨ {!!} ⟩
260 deltaM-mu (appendDeltaM (deltaM (mono (mu mm (fmap fm headDeltaM x))))
261 (deltaM-mu (deltaM-fmap tailDeltaM (deltaM d))))≡⟨ refl ⟩
262 deltaM-mu (deltaM-mu (deltaM (delta x d)))
263
264
265
266
171 267
172 deltaM-is-monad : {l : Level} {A : Set l} {n : Nat} 268 deltaM-is-monad : {l : Level} {A : Set l} {n : Nat}
173 {M : Set l -> Set l} 269 {M : Set l -> Set l}
174 (functorM : Functor M) 270 (functorM : Functor M)
175 (monadM : Monad M functorM) -> 271 (monadM : Monad M functorM) ->
176 Monad {l} (\A -> DeltaM M {functorM} {monadM} A (S n)) (deltaM-is-functor {l} {n}) 272 Monad {l} (\A -> DeltaM M {functorM} {monadM} A (S n)) (deltaM-is-functor {l} {n})
177 deltaM-is-monad functorM monadM = record 273 deltaM-is-monad {l} {A} {n} {M} functorM monadM =
178 { mu = deltaM-mu; 274 record { mu = deltaM-mu;
179 eta = deltaM-eta; 275 eta = deltaM-eta;
180 return = deltaM-eta; 276 return = deltaM-eta;
181 bind = deltaM-bind; 277 bind = deltaM-bind;
182 association-law = {!!}; 278 association-law = (deltaM-association-law M functorM monadM) ;
183 left-unity-law = deltaM-left-unity-law; 279 left-unity-law = deltaM-left-unity-law;
184 right-unity-law = (\x -> (sym (deltaM-right-unity-law x))) ; 280 right-unity-law = (\x -> (sym (deltaM-right-unity-law x))) ;
185 eta-is-nt = deltaM-eta-is-nt 281 eta-is-nt = deltaM-eta-is-nt }
186 } 282
187 283
188
189
190
191
192
193 {-
194 deltaM-association-law : {l : Level} {A : Set l}
195 {M : {l' : Level} -> Set l' -> Set l'}
196 (functorM : {l' : Level} -> Functor {l'} M)
197 (monadM : {l' : Level} {A : Set l'} -> Monad {l'} {A} M functorM)
198 -> (d : DeltaM M (DeltaM M (DeltaM M {functorM} {monadM} A)))
199 -> ((deltaM-mu ∙ (deltaM-fmap deltaM-mu)) d) ≡ ((deltaM-mu ∙ deltaM-mu) d)
200 deltaM-association-law functorM monadM (deltaM (mono x)) = begin
201 (deltaM-mu ∙ deltaM-fmap deltaM-mu) (deltaM (mono x)) ≡⟨ refl ⟩
202 deltaM-mu (deltaM-fmap deltaM-mu (deltaM (mono x))) ≡⟨ refl ⟩
203 deltaM-mu (deltaM (delta-fmap (fmap functorM deltaM-mu) (mono x))) ≡⟨ {!!} ⟩
204 deltaM-mu (deltaM (mono (bind monadM x headDeltaM))) ≡⟨ refl ⟩
205 deltaM-mu (deltaM-mu (deltaM (mono x))) ≡⟨ refl ⟩
206 deltaM-mu (deltaM-mu (deltaM (mono x))) ≡⟨ refl ⟩
207 (deltaM-mu ∙ deltaM-mu) (deltaM (mono x)) ∎
208 deltaM-association-law functorM monadM (deltaM (delta x d)) = {!!}
209 -}
210
211 {-
212
213 nya : {l : Level} {A B C : Set l} ->
214 {M : {l' : Level} -> Set l' -> Set l'}
215 {functorM : {l' : Level} -> Functor {l'} M }
216 {monadM : {l' : Level} {A : Set l'} -> Monad {l'} {A} M functorM}
217 (m : DeltaM M {functorM} {monadM} A) -> (f : A -> (DeltaM M {functorM} {monadM} B)) -> (g : B -> (DeltaM M C)) ->
218 (x : M A) ->
219 (deltaM (fmap delta-is-functor (\x -> bind {l} {A} monadM x (headDeltaM ∙ (\x -> deltaM-bind (f x) g))) (mono x))) ≡
220 (deltaM-bind (deltaM (fmap delta-is-functor (\x -> (bind {l} {A} monadM x (headDeltaM ∙ f))) (mono x))) g)
221 nya = {!!}
222
223 deltaM-monad-law-h-3 : {l : Level} {A B C : Set l} ->
224 {M : {l' : Level} -> Set l' -> Set l'}
225 {functorM : {l' : Level} -> Functor {l'} M }
226 {monadM : {l' : Level} {A : Set l'} -> Monad {l'} {A} M functorM}
227 (m : DeltaM M {functorM} {monadM} A) -> (f : A -> (DeltaM M B)) -> (g : B -> (DeltaM M C)) ->
228 (deltaM-bind m (\x -> deltaM-bind (f x) g)) ≡ (deltaM-bind (deltaM-bind m f) g)
229 {-
230 deltaM-monad-law-h-3 {l} {A} {B} {C} {M} {functorM} {monadM} (deltaM (mono x)) f g = begin
231 (deltaM-bind (deltaM (mono x)) (\x -> deltaM-bind (f x) g)) ≡⟨ refl ⟩
232
233 (deltaM (mono (bind {l} {A} monadM x (headDeltaM ∙ (\x -> deltaM-bind (f x) g))))) ≡⟨ {!!} ⟩
234 (deltaM-bind (deltaM (fmap delta-is-functor (\x -> (bind {l} {A} monadM x (headDeltaM ∙ f))) (mono x))) g) ≡⟨ refl ⟩
235 (deltaM-bind (deltaM (mono (bind {l} {A} monadM x (headDeltaM ∙ f)))) g) ≡⟨ refl ⟩
236 (deltaM-bind (deltaM-bind (deltaM (mono x)) f) g) ∎
237 -}
238
239 deltaM-monad-law-h-3 {l} {A} {B} {C} {M} {functorM} {monadM} (deltaM (mono x)) f g = begin
240 (deltaM-bind (deltaM (mono x)) (\x -> deltaM-bind (f x) g)) ≡⟨ refl ⟩
241 (deltaM (mono (bind {l} {A} monadM x (headDeltaM ∙ (\x -> deltaM-bind (f x) g))))) ≡⟨ {!!} ⟩
242 -- (deltaM (fmap delta-is-functor (\x -> bind {l} {A} monadM x (headDeltaM ∙ (\x -> deltaM-bind (f x) g))) (mono x))) ≡⟨ {!!} ⟩
243 deltaM (mono (bind {l} {B} monadM (bind {_} {A} monadM x (headDeltaM ∙ f)) (headDeltaM ∙ g))) ≡⟨ {!!} ⟩
244 deltaM (mono (bind {l} {B} monadM (bind {_} {A} monadM x (headDeltaM ∙ f)) (headDeltaM ∙ g))) ≡⟨ {!!} ⟩
245 (deltaM-bind (deltaM (mono (bind {l} {A} monadM x (headDeltaM ∙ f)))) g) ≡⟨ refl ⟩
246 (deltaM-bind (deltaM-bind (deltaM (mono x)) f) g)
247
248 deltaM-monad-law-h-3 (deltaM (delta x d)) f g = {!!}
249 {-
250 begin
251 (deltaM-bind m (\x -> deltaM-bind (f x) g)) ≡⟨ {!!} ⟩
252 (deltaM-bind (deltaM-bind m f) g)
253
254 -}
255 -}