-
Notifications
You must be signed in to change notification settings - Fork 4
/
2.html
1139 lines (1005 loc) · 45.5 KB
/
2.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!doctype html>
<html lang="ja">
<head>
<meta charset="utf-8">
<title>圏論勉強会 第2回 @ ワークスアプリケーションズ</title>
<meta name="description" content="Seminar of category theory">
<meta name="author" content="Koichi Nakamura">
<meta name="apple-mobile-web-app-capable" content="yes" />
<meta name="apple-mobile-web-app-status-bar-style" content="black-translucent" />
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no">
<link rel="stylesheet" href="css/reveal.css">
<link rel="stylesheet" href="css/theme/sky.css" id="theme">
<meta http-equiv="X-UA-Compatible" CONTENT="IE=EmulateIE7" />
<!-- For syntax highlighting -->
<link rel="stylesheet" href="plugin/highlight/styles/github.css">
<!-- If the query includes 'print-pdf', use the PDF print sheet -->
<script>
document.write( '<link rel="stylesheet" href="css/print/' + ( window.location.search.match( /print-pdf/gi ) ? 'pdf' : 'paper' ) + '.css" type="text/css" media="print">' );
</script>
<script type="text/javascript" async
src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML">
</script>
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
tex2jax: {
inlineMath: [ ['$','$'], ["\\(","\\)"] ],
displayMath: [ ['$$','$$'], ["\\[","\\]"] ]
}
});
</script>
<style type="text/css">
<!--
div.definition {
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 4px solid #333333;
box-shadow: 0 0 10px rgba(0, 0, 0, 0.15);
}
div.theorem {
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 4px solid #333333;
box-shadow: 0 0 10px rgba(0, 0, 0, 0.15);
}
div.equation {
margin: 10px;
padding-top: 10px;
padding-bottom: 10px;
padding-left: 10px;
padding-right: 10px;
border: 2px solid #C0C0C0;
}
-->
</style>
<!--[if lt IE 9]>
<script src="lib/js/html5shiv.js"></script>
<![endif]-->
</head>
<body>
<div class="reveal">
<!-- Any section element inside of this container is displayed as a slide -->
<div class="slides">
<section>
<h1>圏論勉強会<br>第2回</h1>
<h3>@ワークスアプリケーションズ</h3>
<small> 中村晃一 <br> 2013年5月23日</small>
$$ \newcommand\append{{+\hspace{-.7em}+}} $$
</section>
<section>
<h3>謝辞</h3>
<p>
この勉強会の企画，会場設備の提供をして頂きました<br>
㈱ ワークスアプリケーションズ様<br>
にこの場をお借りして御礼申し上げます。
</p>
</section>
<section>
<h3> この会について </h3>
<ul>
<li> <span style="color:red">圏論(category theory)</span>を題材にいろんなことを学びます。</li>
<li> 分かり易さを重視して初歩的な例を多用します。</li>
<li> 関数型言語の経験がある方がより楽しめると思います。資料中では主にHaskellを使います。 </li>
<li> この資料は<a href="http://nineties.github.com/category-seminar/">http://nineties.github.com/category-seminar</a>に置いてあります。</li>
</ul>
</section>
<section>
<h2> 第２回:モノイド・群 </h2>
</section>
<section>
<h3> 第2回の内容 </h3>
<div class="fragment" align="center"> <img src="fig/pie_chart.png"> </div>
</section>
<section>
<h1>モノイド勉強会</h1>
<h3>@ワークスアプリケーションズ</h3>
<small> 中村晃一 <br> 2013年5月23日</small>
</section>
<section>
<h3> 第2回の内容 </h3>
<p>
本日は予定を変更して一旦圏論を離れ,モノイド・群という概念について紹介します。
モノイド・群は「対象が$1$つの圏」でもありますので,本格的に圏論を学習する前に是非抑えておきたい内容です。
</p>
</section>
<section>
<h3> 用語・記法について </h3>
<ul>
<li> 自然数$\mathbb{N}$とは$0$以上の整数の事とします。 </li>
<li> ２項演算子$\star$の第1引数,第2引数を定数に固定した関数を便宜的に以下の様に表す事にします。
$$ \color{red}{(a\ \star)} : x \mapsto a \star x $$
$$ \color{red}{(\star\ a)} : x \mapsto x \star a $$
例えば
$$ (2\ +)(3) = 2 + 3 \qquad (+\ 2)(3) = 3 + 2$$
という感じです。
</li>
</ul>
</section>
<section>
<h2> モノイド </h2>
</section>
<section id="monoid">
<h3> モノイド </h3>
<div class="definition">
<p>
<span style="color:red">モノイド(monoid)</span>とは集合$M$，$M$上の二項演算$\cdot$の組$(M, \cdot)$で，以下の条件を満たすものである。<br>
</p>
<ul>
<li>結合律: 任意の$x,y,z \in M$について
$$ (x\cdot y)\cdot z = x\cdot (y \cdot z)$$
</li>
<li> 単位元の存在: $e \in M$が存在し,任意の$x \in M$について
$$ e\cdot x = x\cdot e = x $$
</li>
</ul><br>
<p>
$M$をこのモノイドの<span style="color:red">台集合(underlying set)</span>と言う。誤解の恐れがない場合にはモノイドと台集合に同じ記号を用いる。
</p>
</div>
</section>
<section>
<h3> モノイド:自然数と加法 </h3>
<p>
$\mathbb{N}$を自然数の集合,$+$を整数の足し算としたとき,
$$ (\mathbb{N}, +) $$
はモノイドとなります。単位元は$0$です。
</p>
<p>
モノイドの条件を全て満たす事を確認しましょう。<br>
<div class="equation">
<ul>
<li> $x,y \in \mathbb{N}$ならば$x + y\in\mathbb{N}$ </li>
<li> $(x + y) + z = x + (y + z)$ </li>
<li> $0 + x = x + 0 = x$ </li>
</ul>
</div>
</p>
</section>
<section>
<h3> モノイド:自然数と乗法 </h3>
<p>
$\mathbb{N}$を自然数の集合,$\cdot $を整数の掛け算としたとき,
$$ (\mathbb{N}, \cdot) $$
はモノイドです。単位元は$1$です。
</p>
<div class="equation">
<ul>
<li> $x,y \in \mathbb{N}$ならば$x \cdot y\in\mathbb{N}$ </li>
<li> $(x \cdot y) \cdot z = x \cdot (y \cdot z)$ </li>
<li> $1 \cdot x = x \cdot 1 = x$ </li>
</ul>
</div>
</section>
<section>
<h3> 加法・乗法によるモノイド </h3>
<div align="left">
<p> 加法については </p>
<ul>
<li> 整数$\mathbb{Z}$,有理数$\mathbb{Q}$,実数$\mathbb{R}$,複素数$\mathbb{C}$,$\cdots$ </li>
<li> $2$の倍数,$3$の倍数,$\cdots$ </li>
<li> $\{a+b\sqrt{2} | a,b\in \mathbb{Q}\}$ </li>
</ul>
<p> など。乗法については </p>
<ul>
<li> 整数$\mathbb{Z}$,有理数$\mathbb{Q}$,実数$\mathbb{R}$,複素数$\mathbb{C}$,$\cdots$ </li>
<li> 正の自然数$\mathbb{N}^{+}$ </li>
<li> $\{1,2,4,8,16,32,\cdots\}$ </li>
</ul>
<p> など、様々な集合がモノイドの条件を満たします。 </p>
</div>
</section>
<section>
<h3> モノイド:列と連結 </h3>
<p>
$[A]$を集合$A$を要素の有限列
$$ [a_0, a_1,\cdots,a_n] \qquad (a_i \in A) $$
とし,$\append$を列の結合
$$ [a_0,\cdots,a_m]\append[b_0,\cdots,b_n] = [a_0,\cdots,a_m,b_0,\cdots,b_n] $$
としたとき,$ ([A], \append) $はモノイドです。単位元は空列$[\,]$です。
</p>
<div class="equation">
<ul>
<li> $x,y \in [A]$ならば$x \append y\in [A]$ </li>
<li> $(x \append y) \append z = x \append (y \append z)$ </li>
<li> $[\,] \append x = x \append [\,] = x$ </li>
</ul>
</div>
</section>
<section>
<h3> モノイド:文字列と連結 </h3>
<p>
「列」の一例として,文字列も連結に関してモノイドとなります。単位元は空文字列$\text{""}$です。
</p>
$$ \text{"Hello"} \append \text{" "} \append \text{"World!"} = \text{"Hello World!"} $$
</section>
<section>
<h3> モノイド:論理積・論理和 </h3>
<p> $(\{\mathrm{true},\mathrm{false}\}, \mathrm{and})$ 単位元は$\mathrm{true}$。</p>
<div class="equation">
$$\begin{aligned}
&\mathrm{true}\ \mathrm{and}\ \mathrm{true} = \mathrm{true} \\
&\mathrm{true}\ \mathrm{and}\ \mathrm{false} = \mathrm{false}\ \mathrm{and}\ \mathrm{true} = \mathrm{false}
\end{aligned}
$$
</div>
<br>
<p> $(\{\mathrm{true},\mathrm{false}\}, \mathrm{or})$ 単位元は$\mathrm{false}$。</p>
<div class="equation">
$$\begin{aligned}
& \mathrm{false}\ \mathrm{or}\ \mathrm{false} = \mathrm{false} \\
& \mathrm{false}\ \mathrm{or}\ \mathrm{true} = \mathrm{true}\ \mathrm{or}\ \mathrm{false} = \mathrm{true}
\end{aligned}
$$
</div>
</section>
<section>
<h3> モノイド:集合の$\mathrm{join}$,$\mathrm{meet}$ </h3>
<p> $(\mathcal{P}(A), \cup)$ 単位元は$\emptyset$。</p>
<div class="equation">
$ X\cup\emptyset = \emptyset\cup X = X$
</div>
<br>
<p> $(\mathcal{P}(A), \cap)$ 単位元は$A$。 </p>
<div class="equation">
$ X\cap A = A\cap X = X \quad (X\subseteq A) $
</div>
</ul>
<p style="font-size:80%">
$\mathcal{P}(A)$は$A$の部分集合全てからなる集合($A$のべき集合(power set))です。例えば
$$ \mathcal{P}(\{1,2,3\}) = \{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{2,3\},\{1,3\},\{1,2,3\}\}$$
のような集合です。
</p>
</section>
<section>
<h3> モノイド:最大値・最小値</h3>
<p> $A$を最小値$m$を持つ数値の集合とすると,$(A, \max)$は$m$を単位元とするモノイドです。</p>
<div class="equation">
$\max\{m, x\} = \max\{x, m\} = x \quad (x \in A) $
</div>
<br>
<p> $A$を最大値$M$を持つ数値の集合とすると,$(A, \min)$は$M$を単位元とするモノイドです。</p>
<div class="equation">
$\min\{M, x\} = \min\{x, M\} = x \quad (x \in A) $
</div>
</section>
<section>
<p>
今の３つの例は「有界半束はモノイドである」という事実の具体例です。
「束」は積・余積と関係するので後の回に説明します。本日は分からなくても大丈夫です。
</p>
</section>
<section>
<h3> プログラミングにおけるモノイド </h3>
</section>
<section>
<h3> 集約演算 </h3>
<p> データ列に対する集約・集積演算はモノイドと関係します。 </p>
<ul>
<li> 値の和・積を求める。 </li>
<li> 条件を満たす要素を集める。 </li>
<li> 最大値・最小値を計算する。 </li>
<li> 全て～であるか？～を満たす物があるか？ </li>
</ul>
<p> 関数型言語では<span style="color:red">畳み込み(folding)</span>と呼ぶ事が多いです。</p>
</section>
<section>
<p> 格納データを<span style="color:red">直列化</span>出来るコンテナに対して,モノイドによる畳込みを定義する事が出来ます。</p>
<div align="center"> <img height="70%" src="fig/fold1.png"> </div>
</section>
<section>
<p> モノイドの結合性は任意の部分列から畳み込む事を正当化しますので,効率のよいアルゴリズムを考える際に重要です。 </p>
<div align="center"> <img height="70%" src="fig/fold2.png"> </div>
</section>
<section>
<p> 都合良くモノイドな値を格納している事は少ないので,個々の値を適当なモノイドにマッピングする操作とセットで考えましょう。 </p>
<div align="center"> <img height="70%" src="fig/fold3.png"> </div>
</section>
<section>
<p> つまり,$\mathrm{map}$と$\mathrm{fold}$を合成した関数によって様々な畳み込みを行うことがはずです。 </p>
<div align="center"> <img height="70%" src="fig/fold4.png"> </div>
</section>
<section>
<h3> Haskellでの例 </h3>
GHCiをお持ちの方は<code>..... > </code>となっている部分のコードを動かしてみて下さい。
<pre><code data-trim class="haskell" contenteditable>
-- モノイド,畳込み,木のライブラリを読み込みます
Prelude> :m +Data.Monoid Data.Foldable Data.Tree
Prelude Data.Monoid Data.Foldable Data.Tree> :set prompt "> "
-- 木を作ってみます
> let tree = unfoldTree (\x -> (x, [1..x-1])) 4
> let showTree t = putStr . drawTree . fmap show $ t
> showTree tree
4
|
+- 1
|
+- 2
| |
| `- 1
|
`- 3
|
+- 1
|
`- 2
|
`- 1
-- Monoidというライブラリには様々なモノイドが定義されています。
> :info Monoid
class Monoid a where
mempty :: a
mappend :: a -> a -> a
mconcat :: [a] -> a
-- Defined in `Data.Monoid'
instance Monoid [a] -- Defined in `Data.Monoid'
instance Num a => Monoid (Sum a) -- Defined in `Data.Monoid'
instance Num a => Monoid (Product a) -- Defined in `Data.Monoid'
instance Monoid Ordering -- Defined in `Data.Monoid'
instance Monoid a => Monoid (Maybe a) -- Defined in `Data.Monoid'
instance Monoid (Last a) -- Defined in `Data.Monoid'
instance Monoid (First a) -- Defined in `Data.Monoid'
instance Monoid (Endo a) -- Defined in `Data.Monoid'
instance Monoid a => Monoid (Dual a) -- Defined in `Data.Monoid'
instance Monoid Any -- Defined in `Data.Monoid'
instance Monoid All -- Defined in `Data.Monoid'
instance Monoid b => Monoid (a -> b) -- Defined in `Data.Monoid'
instance (Monoid a, Monoid b, Monoid c, Monoid d, Monoid e) =>
Monoid (a, b, c, d, e)
-- Defined in `Data.Monoid'
instance (Monoid a, Monoid b, Monoid c, Monoid d) =>
Monoid (a, b, c, d)
-- Defined in `Data.Monoid'
instance (Monoid a, Monoid b, Monoid c) => Monoid (a, b, c)
-- Defined in `Data.Monoid'
instance (Monoid a, Monoid b) => Monoid (a, b)
-- Defined in `Data.Monoid'
instance Monoid () -- Defined in `Data.Monoid'
-- fmapという関数は木の各ノードに関数を適用してくれます。
-- 下の例では,各整数を足し算によるモノイドの値にマッピングしています。
> showTree (fmap Sum tree)
Sum {getSum = 4}
|
+- Sum {getSum = 1}
|
+- Sum {getSum = 2}
| |
| `- Sum {getSum = 1}
|
`- Sum {getSum = 3}
|
+- Sum {getSum = 1}
|
`- Sum {getSum = 2}
|
`- Sum {getSum = 1}
-- 要素がモノイドの値である木に対し,foldを適用すると畳込みが行われます。
> fold (fmap Sum tree)
Sum {getSum = 15}
-- fmapとfoldを続けて行なってくれる(もちろん,内部的にはより効率のよい実装になっている)関数が
-- foldMapです。
> foldMap Sum tree
Sum {getSum = 15}
-- foldMapの計算結果はモノイドの要素としての値です。getXXXXなどの関数で中身を取り出す事が出来ます。
> getSum (foldMap Sum tree)
15
-- 積
> foldMap Product tree
Product {getProduct = 48}
-- 列(Haskellでは \x -> f(x)という記法で引数がxの関数を表します。)
> foldMap (\x -> [x]) tree
[4,1,2,1,3,1,2,1]
-- 文字列
> foldMap show tree
"41213121"
-- 集合のjoin
> foldMap (\x -> Data.Set.singleton x) tree
fromList [1,2,3,4]
-- 組(タプル)を使うと複数の畳み込みを同時に行えます。
> foldMap (\x -> (Sum x, Product x)) tree
(Sum {getSum = 15},Product {getProduct = 48})
-- 木のノード数の計算
> foldMap (\x -> Sum 1) tree
Sum {getSum = 8}
-- evenという関数は整数が偶数か否かを判定します。
> showTree (fmap even tree)
True
|
+- False
|
+- True
| |
| `- False
|
`- False
|
+- False
|
`- True
|
`- False
-- evenにAllを合成してみます。
> showTree (fmap (All . even) tree)
All {getAll = True}
|
+- All {getAll = False}
|
+- All {getAll = True}
| |
| `- All {getAll = False}
|
`- All {getAll = False}
|
+- All {getAll = False}
|
`- All {getAll = True}
|
`- All {getAll = False}
-- Allは論理積によるモノイドを表します。全てが偶数であるか => No
> foldMap (All . even) tree
All {getAll = False}
-- Anyは論理和です。
> foldMap (Any . even) tree
Any {getAny = True}
-- 条件分岐と組み合わせてみます。条件を満たさないものを単位元に移せば,
-- 条件を満たす値だけでの畳込みとなります。
> foldMap (\x -> if even x then Sum x else Sum 0) tree
Sum {getSum = 8}
</code></pre>
</section>
<section>
<h3> とても便利ですね～</h3>
<p class="fragment">
冷静に考えるとまだよく分からない。
<ul>
<li class="fragment"> 足すとか掛けるとか,一種類の計算しか出来ないのか？ </li>
<li class="fragment"> 何が出来て何が出来ないのか? </li>
</ul>
</p>
</section>
<section>
<h3> 例えば絵を描くという作業 </h3>
<img width="45%" src="fig/monoid_endofunction_example.png" align="right" hspace="20">
<ul>
<ol> 円を描いて </ol>
<ol> 線を引いて </ol>
<ol> 色を塗って </ol>
<ol> ･･･ </ol>
</ul><br clear="right">
<p> 絵とは一連の作業の<span style="color:red">集積</span>では？ </p>
</section>
<section>
<h3> 例えばロボットの操作 </h3>
<img width="45%" src="fig/monoid_endofunction_example2.png" align="right" hspace="20">
<ul>
<ol> 右を向け </ol>
<ol> 前へ進め </ol>
<ol> 止まれ </ol>
<ol> ・・・ </ol>
</ul><br clear="right">
<p> ロボットの動きとは一連の命令の<span style="color:red">集積</span>では？ </p>
</section>
<section>
<h3> モノイド: endomorphismと合成 </h3>
<img width="30%" src="fig/endomorphism.png" align="right" hspace="20">
<p style="font-size:90%">
ドメインとコドメインが同じ集合である関数を,<span style="color:red">自己準同型写像(endomorphism)</span>と言います。
</p>
<div class="fragment">
<p style="font-size:90%">
集合$A$上の自己準同型全ての集合は関数合成に関して,恒等関数$\mathrm{id}_A$を単位元とするモノイドです。
このモノイドを$\color{red}{\mathrm{End}(A)}$と表すことにします。
</p><br clear="right">
<div class="equation">
$$ \begin{aligned}
& h\circ(g\circ f) = (h\circ g)\circ f \\
& \mathrm{id}_A\circ f = f\circ \mathrm{id}_A = f
\end{aligned}$$
</div>
</div>
<div align="left" style="font-size:50%">
注: 集合は全く構造のない代数系と見なせるので,後の事も考えて準同型と呼ぶことにします。正確には$\mathrm{End}_{\mathbf{Sets}}(A)$と書きます。
</div>
</section>
<section>
<h3> Haskellでの例 </h3>
<pre><code data-trim class="haskell" contenteditable>
-- Endomorphismの使用例です。
-- 以下は1を足すという関数。整数から整数へのendomorphismです。
> (+ 1) 2
3
-- 3を掛けるという関数。これも整数上のendomorphismです。
> (3 *) 3
9
-- このようなendomorphismをEndoというモノイドにして畳み込む事が出来ます。
-- foldMap (\x -> if even x then Endo (x *) else Endo (+ x)) tree
-- 正しこの畳込みの結果得られるのは
-- Endo { appEndo = 関数(表示出来ない) }
-- というモノイドとしての値ですので,appEndoで関数を取り出して何か数値を代入する必要があります。
-- 偶数なら掛けて,奇数なら足すという畳込みです。複数種類の演算を混ぜる事が出来ました。
> appEndo( foldMap (\x -> if even x then Endo (x *) else Endo (+ x)) tree ) 0
60
-- 検算をしてみます。
-- 要素の順番は以下のようになっています。
> foldMap (\x -> [x]) tree
[4,1,2,1,3,1,2,1]
-- これが
-- (4 *) . (+ 1) . (2 *) . (+ 1) . (+ 3) . (+ 1) . (2 *) . (+ 1)
-- というendomorphismの合成に移ります。
> ((4 *) . (+ 1) . (2 *) . (+ 1) . (+ 3) . (+ 1) . (2 *) . (+ 1)) 0
60
</code></pre>
</section>
<section>
<h3> モノイドの表現 </h3>
</section>
<section>
<p style="font-size:120%">
もしかして,任意のモノイドは自己準同型のなすモノイドとして表せるのでは？
</p>
<div class="fragment" align="center"> <img src="fig/monoid_cayley.png"> </div>
</section>
<section>
<p> いくつか言葉を準備して,この現象について考えてみます。 </p>
<div align="center"> <img src="fig/monoid_cayley2.png"> </div>
</section>
<section>
<h3> 準備: モノイド準同型 </h3>
<p>
モノイドからモノイドへの構造を保ったマッピングを(モノイドの)<span style="color:red">準同型写像(homomorphism)</span>と言います。「写像」を省略して準同型と呼びます。ところでモノイドの構造とは結合的な２項演算と単位元の事でした。
</p>
<div class="fragment">
<div class="definition">
<p>
モノイド$(M,\star)$から$(N,\diamond)$への準同型$F: (M,\star) \rightarrow (N,\diamond)$とは,$M$から$N$への関数であり以下の条件を満たすもの。<br>
<ul>
<li> $ F(x\star y) = F(x)\diamond F(y)$ </li>
<li> $ F(e_{\star}) = e_{\diamond}\quad(\text{$e_{\star}$,$e_{\diamond}$は各モノイドの単位元}) $ </li>
</ul>
</p>
</div>
</div>
</section>
<section>
<h3> 準同型の例: $\mathrm{length}$ </h3>
<p>
有限列の長さを得る関数$\mathrm{length}$は準同型
$$ \mathrm{length} : ([A],\append) \rightarrow (\mathbb{N},+) $$
と見なせます。
<br>
<div class="equation">
$$ \begin{aligned}
&\mathrm{length}([a_0,\cdots,a_m]\append[b_0,\cdots,b_n]) \\
&\quad = \mathrm{length}([a_0,\cdots,a_m]) + \mathrm{length}([b_0,\cdots,b_n]) \\
&\mathrm{length}([\ ]) = 0
\end{aligned} $$
</div>
</p>
</section>
<section>
<h3> 準備: モノイドの同型 </h3>
<p> 同型とは「本質的に同じ」という事です。</p>
<div class="definition">
<p>
モノイド$M$から$N$への準同型$f: M\rightarrow N$に対して準同型$g: N\rightarrow M$が存在し,
$$ g\circ f= \mathrm{id}_M \qquad f\circ g = \mathrm{id}_N $$
である時,$f$を$M$から$N$への<span style="color:red">同型写像(isomorphism)</span>と言う。モノイド$M$と$N$の間に同型写像が存在する時,$M$と$N$は<span style="color:red">同型(isomorphic)</span>であると言い
$$ M \cong N $$
と表す。
</p>
</div>
</section>
<section>
<h3> 同型の例: $x \mapsto a^x$ </h3>
<div style="font-size:90%">
<p>
例えば$f(x) = 2^x$という関数は準同型
$$ f: (\mathbb{N},+) \rightarrow (\{1,2,4,8,16,\cdots\},\cdot) $$
と見なせます。
</p>
<div class="equation">
$$ 2^{x+y} = 2^x\cdot 2^y \qquad 2^0 = 1 $$
</div>
<p>
同様に$g(x) = \log_2 x$が逆方向の準同型を与え,
$$ \log_2 2^x = x \qquad 2^{\log_2 x} = x $$
なので$f$が同型写像である事が判ります。
$$ (\mathbb{N},+) \cong (\{1,2,4,8,16,\cdots\},\cdot) $$
</p>
</div>
</section>
<section>
<h3> 準備: 部分モノイド </h3>
<div class="definition">
<p>
同じ演算からなるモノイド$(A, \cdot)$と$(B,\cdot)$について,$A \subseteq B$であるならば$A$は$B$の<span style="color:red">部分モノイド</span>であると言い
$$ (A,\cdot) \subseteq (B,\cdot) $$
と表す。
</p>
</div>
<p>
例えば,下のような例があります。
$$(\{0,2,4,6,8,\cdots\},+) \subseteq (\mathbb{N}, +) \subseteq (\mathbb{Z}, +) $$
</p>
</section>
<section>
<h3> 定理 </h3>
<div class="theorem">
<p>
任意のモノイドは適当な集合$A$について$\mathrm{End}{A}$の部分モノイドと同型。
</p>
</div>
<div style="font-size:90%">
<p class="fragment">
この定理は「表現定理」と呼ばれる一連の定理の一つです。<br>
「モノイド」というよく分からない抽象概念に「集合と関数」からなる具体的な表現を与える事によって,
その正体が掴みやすくなるのです。今後の授業でも度々登場する重要なテーマです。
</p>
</div>
</section>
<section>
<div align="left" style="font-size:80%">
【証明】<br>
<span class="fragment">モノイド$M=(\{a,b,\cdots\},\cdot)$に対して,$\overline{M} = \{(a\ \ \cdot),(b\ \ \cdot),\cdots\}$とする。$e\in M$を単位元とする。</span><span class="fragment">すると,任意の$a,b\in M$に対して</span>
<ul>
<li class="fragment"> 任意の$x\in M$について$((a\cdot b)\ \ \cdot)(x) = (a\ \ \cdot)\circ(b\ \ \cdot)(x) = a\cdot b\cdot x$ なので
$$ ((a\cdot b)\ \ \cdot) = (a\ \ \cdot)\circ(b\ \ \cdot) $$
</li>
<li class="fragment"> 任意の$x\in M$について$(e\ \ \cdot)(x) = e\cdot x = x$なので
$$ (e\ \ \cdot) = \mathrm{id}_{M} $$
</li>
</ul>
<p class="fragment">
すなわち$\phi: a\mapsto (a\ \ \cdot)$は$M$から$\overline{M}\subseteq\mathrm{End}(M)$への準同型を定める。
</p>
</div>
</section>
<section>
<p> ここで$\overline{M}$から$M$への写像$\psi: f\mapsto f(e)$を考えると,</p>
<ul>
<li class="fragment"> 任意の$x \in M$について
$$ \psi\circ \phi(x) = \psi((x\ \ \cdot)) = (x\ \ \cdot)(e) = x\cdot e = x$$
</li>
<li class="fragment"> 任意の$(x\ \ \cdot) \in \overline{M}$について
$$ \phi\circ\psi((x\ \ \cdot)) = \phi((x\ \ \cdot)(e)) = \phi(x) = (x\ \ \cdot)$$
</li>
</ul>
<p class="fragment">
すなわち
$$ \psi\circ\phi = \mathrm{id}_{M}\qquad\phi\circ\psi = \mathrm{id}_{\overline{M}}$$
となる。
</p>
<p class="fragment"> 従って$(M, \cdot) \cong (\overline{M}, \circ)$ <span style="float:right">□</span> </p>
</section>
<section>
<p> 同様に$a\mapsto (\cdot\ \ a)$という同型写像を考える事も出来ます。ただし,畳み込みの順番を保つ為には関数合成の順番を逆にしたモノイド($\mathrm{End}(A)$の反モノイドと言います。)への写像を考える必要があります。
</p>
<div align="center"> <img src="fig/opposite_monoid_cayley.png"> </div>
</section>
<section>
<h2> $\mathrm{foldr}と\mathrm{foldl}$ </h2>
</section>
<section>
<p>
関数型言語を勉強するとそのうち$\color{red}{\mathrm{foldr}}$,$\color{red}{\mathrm{foldl}}$という謎の関数に出くわします。この授業でも今後よく登場すると思います。
</p>
<p class="fragment">
さて,名前から分かる様にこれも畳み込みを行う関数ですのでモノイドと関係があるはずです。
今回はそのような視点からこれらを眺めてみます。
</p>
</section>
<section>
<h3> $\mathrm{foldr},\,\mathrm{foldl}$とは</h3>
<p>
$\mathrm{foldr}$は二項演算$\star : A\times B\rightarrow B$,$x \in B$を受け取り,$A$の要素の列を以下のように$B$の値に畳み込みます。
</p>
<p>
同様に$\mathrm{foldl}$は二項演算$\diamond : B\times A\rightarrow B$,$x \in B$を受け取り,以下のように畳み込みます。
</p>
<div align="center"> <img src="fig/foldr_foldl.png"> </div>
</section>
<section>
<p> 書きなおすと・・・</p>
<div class="fragment" align="center"> <img src="fig/foldr_foldl2.png"> </div>
<p class="fragment">
つまり$\mathrm{foldr},\,\mathrm{foldl}$は、自己準同型へのマッピングと値の代入を一挙に行なってくれる関数という見方が出来ます。数学的には作用素モノイドという概念と関係します。
</p>
<p class="fragment">
$\star$,$\diamond$は<span style="color:red">モノイドの演算でなくても良い</span>ので非常に汎用的な関数であると言えます。
</p>
</section>
<section>
<h3> Haskellでの例 </h3>
<pre><code data-trim class="haskell" contenteditable>
-- (x :)という関数はリストの先頭にxを追加するリストからリストへのendomorphismです。
> (1 :) [0,1,2]
[1,0,1,2]
-- [1,2,3,4,5]をこのendomorphismにして[2,3]に右から順番に適用してみます。
-- 5,4,3,2,1の順番に追加が行われた事が判ります。
> Data.Foldable.foldr (\x -> (x :)) [2,3] [1,2,3,4,5]
[1,2,3,4,5,2,3]
-- 今度は左から順番に適用してみます。foldrとfoldlは渡す関数の引数の順番が逆なので
-- flipという関数を挟む必要があります。
-- 1,2,3,4,5の順番に追加が行われた事が判ります。
> Data.Foldable.foldl (flip (\x -> (x :))) [2,3] [1,2,3,4,5]
[5,4,3,2,1,2,3]
-- foldr,foldlには任意のendomorphismを食わす事が出来ますから、様々な複雑な処理を行えます。
-- 例えばconst []という関数は引数を捨てて空リストを返す関数です。リストを引数に取れば
-- リストからリストへのendomorphismとなります。
> (const []) [2,3]
[]
-- リストを順番に見ていって,3に出くわしたら入力を捨てて空にしてしまうという例です。
> Data.Foldable.foldr (\x -> if x == 3 then const [] else (x :)) [2,3] [1,2,3,4,5]
[1,2]
-- foldrには任意のendomorphismを食わす事ができますが,有用なパターンは独立したモノイドとして
-- 取り出す事が出来ます。先ほどの掛けたり足したりの例から取り出してみます。
-- まず掛けたり,足したりする関数を合成すると全てf(x) = ax+bという形になります。
-- f(x) = ax+bとg(x) = cx+dを合成してみると
-- f(g(x)) = a(cx+d)+b = acx + ad+b
-- となります。係数だけ取り出してみれば
-- (a, b) と (c, d)の積が(ac, ad+b)になるという事です。こうして新しいモノイドを取り出す事が出来ました。
-- AddMulというモノイドを定義してみます
-- AddMulは２つのIntegerからなります。deriving (Show)というのはデータを表示出来るようにする為の指示です。
> data AddMul = AddMul Integer Integer deriving (Show)
-- モノイドである事を宣言します。
-- 単位元(mempty)は恒等関数f(x) = x = 1x + 0に対応するAddMul 1 0です。
-- 二項演算(mappend)は上で述べた通りです。
> instance Monoid AddMul where mempty = AddMul 1 0; AddMul a b `mappend` AddMul c d = AddMul (a*c) (a*d + b)
-- 先ほどの例をAddMulを使って計算してみます。
> appEndo( foldMap (\x -> if even x then Endo (x *) else Endo (+ x)) tree ) 0
60
-- (a *)という関数はa x + 0なのでAddMul a 0
-- (+ b)という関数は1 x + bなのでAddMul 1 bです。
> foldMap (\x -> if even x then AddMul x 0 else AddMul 1 x) tree
AddMul 16 60
-- 畳み込まれた結果は実はf(x) = 16x + 60という関数だという事が判りました。
-- 確認してみると確かに16x + 60となっている事が判ります。
> appEndo( foldMap (\x -> if even x then Endo (x *) else Endo (+ x)) tree ) 1
76
> appEndo( foldMap (\x -> if even x then Endo (x *) else Endo (+ x)) tree ) 2
92
</code></pre>
</section>
<section>
<h3> 自由モノイド </h3>
</section>
<section>
<p>
$\mathrm{foldMap}\ f$という関数は列の各要素を$f$でマッピングしてから畳み込む関数でした。
</p>
<div align="center"> <img src="fig/foldMap_homomorphism.png"> </div>
<p class="fragment">
ところで連結演算によて<span style="color:red">列自体もモノイド</span>となります。すると$\mathrm{foldMap}\ f$はモノイド準同型と見なせます。
</p>
</section>
<section>
<h3> 自由モノイド </h3>
<p>
「畳込み」を「列に縮約演算を入れる事」だと思えば,全ての畳み込みが「列と連結」からのモノイド準同型として作れる事になります。つまり,「列と連結」は特別なモノイドです。
</p>
<p class="fragment">
この事を$([A], \append)$は$A$上の<span style="color:red">自由モノイド(free monoid)</span>であると言います。
</p>
</section>
<section>
<h3> 抽象的な自由モノイドの定義が欲しい! </h3>
<p>
「列と連結」という自由モノイドの定義は非常に具体的です。<br>
「もの」と「矢印」と「矢印の連結」よって定義を与える事が出来れば,後に圏論に進んだ際にモノイド以外の概念に応用できるはずです。
</p>
</section>
<section>
<h3> 自由モノイドの本質とは </h3>
<p>
任意の空でない列は下図のように長さ$1$の列に分解出来ます。一切の縮約演算が行われていないから,このような分解が出来るわけです。
</p>
<p>
すると,任意長の列からの準同型は「長さ$1$の列のマッピング」のみによって完全に決定されます。
</p>
<div align="center"> <img src="fig/free_monoid2.png"> </div>
</section>
<section>
<p> これがまさに$\mathrm{foldMap}$という関数が行なっている事です。</p>
</p>
<div align="center"> <img src="fig/free_monoid1.png"> </div>
</section>
<section>
<p>
集合$A$の要素を長さ$1$の列にする関数を$i$とすると,下の図式が可換である事は
$$ \mathrm{foldMap}\ f\ [a] = f(a) $$
が任意の$a\in A$について成り立つという事です。<br>
今説明したように,この可換図式が$\mathrm{foldMap}\ f$の機能を完全に決定します。(証明は後の回にやります。)
</p>
<div align="center"> <img height="30%" src="fig/free_monoid3.png"> </div>
</section>
<section id="free_monoid">
<h3> 自由モノイドの定義 </h3>
<div class="definition" style="font-size:80%">
<p>
モノイド$F(A)$が集合$A$上の自由モノイドであるとはそれがある関数$i: A\rightarrow F(A)$を備えており,任意の関数$f: A\rightarrow M$に対して下側の図式が可換となるようなモノイド準同型$\overline{f}: F(A)\rightarrow M$が唯一つ存在することである。
</p>
<div align="center"> <img height="40%" src="fig/free_monoid4.png"> </div>
</div>
<div align="left" style="font-size:50%">
注: モノイドと台集合,準同型と台集合間の関数に同じ記号を使っています。記号の使い分けは圏論に入ってからにします。
</div>
</section>
<section>
<p>
<span style="color:red">自由モノイドは同型を除いて一意</span>なので自由モノイドとは「列・連結」と同一視出来るものです。時間がないので証明は省略します。(Awodey本のProposition 1.10参照)<br>
定理の内容を理解するのにはなかなか時間が掛かると思いますが,今後の為に是非復習を行なって下さい。<br>
</p>
</section>
<section>
<h3> 最後に </h3>
</section>
<section>
<h3> モノイド: プログラム </h3>
<p>
プログラムを「文(statement)の列」と思うと,「何もしない文」を単位元とし「文を並べる事」を演算とするモノイドと見なせます。
</p>
<div align="center"><img height="50%" src="fig/monoid_program.png"></div>
</section>
<section>
<div align="left" style="font-size:150%">
モナドは(ry
</div>
</section>
<section>
<h2> 群 </h2>
</section>
<section id="group">
<h3> 群 </h3>
<div class="definition">
<p>
<span style="color:red">群(group)</span>とはモノイド$(M,\cdot)$であり,
任意の$x\in M$に対して
$$ x \cdot y = y \cdot x = e \qquad \text{($e$は単位元)} $$
となる$y$が存在するものである。<br>
$y$を$x$の<span style="color:red">逆元(inverse)</span>と言い,
$$ y = x^{-1} $$
と表す。
</p>
</div>
</section>
<section>
<h3> 群の例 </h3>
<div align="left" style="font-size:90%">
以下のようなモノイドは群です。<br>
<ul>
<li> $(\mathbb{Z}, +)$,$(\mathbb{Q}, +)$,$(\mathbb{R},+)$,$(\mathbb{C},+)$ </li>
<li> $(\mathbb{Q}^{*}, \cdot)$, $(\mathbb{R}^{*}, \cdot)$($A^{*}$は$A$から$0$を除いた集合)
</li>
<li> $(\{\cdots,-4,-2,0,2,4,\cdots\}, +)$ </li>
<li> $(\{\cdots,\frac{1}{4},\frac{1}{2},1,2,4,\cdots\},\cdot)$ </li>
</ul><br>
一方,以下のようなモノイドは群ではありません。
<ul>
</ul>
<li> $(\mathbb{N}, +)$ </li>
<li> $(\mathbb{N}, \cdot)$ </li>