Mercurial > hg > Papers > 2015 > atton-thesis

comparison category.tex @ 11:76ce5bb18092

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add Category definition
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Sun, 08 Feb 2015 11:53:19 +0900
parents c2dda6eeab57
children 11015b94a5cd
comparison
equal deleted inserted replaced
10:c2dda6eeab57 11:76ce5bb18092
1 \chapter{Categorical Definitions of Monad} 1 \chapter{Categorical Definitions of Monad}
2 \label{chapter:category}
3
4 \ref{chapter:delta}章ではプログラムの変更がメタ計算としてMonadを用いて定義可能であることを示した。
5 ここで Monad の定義と要請されるMonad則について述べる。
6 また、定義は Monad の解説に必要な部分についてのみ解説する。
2 7
3 \section{Category} 8 \section{Category}
9 まずは Monad の定義に必要な Category (圏)について述べる。
10
11 Category は2つの要素を持つ。
12
13 \begin{itemize}
14 \item object (要素)
15
16 \item morphism (射, arrow)
17
18 object から object へのマッピング。
19
20 morphism によってマップされる対象を domain と呼び、マップした先の対象を codomain と呼ぶ。
21 つまり domain から codomain への object をマップするものが morphism である。
22 domain A と codomain B を持つ morphism f は式\ref{exp:morphism}のように書くこととする。
23
24 \begin{equation}
25 f : A \rightarrow B
26 \label{exp:morphism}
27 \end{equation}
28
29 \end{itemize}
30
31
32
33 そして2つの法則を満たす。
34 \begin{itemize}
35 \item 全ての object について identity mapping が存在する
36
37 identity mapping とは domain と codomain が同じ morphism のことである。
38 identity mappping は id と略する。
39 id は全ての object に存在するため、 object A に対する id は $ id_A $ と書く。
40 なお、id は全ての object に存在するために省略して書くことが多い。
41
42 \item 同じ obejct が domain と codomain になっている2つのmorphismは合成することができ、合成の順番は結果に影響しない。
43
44 morphism の合成には記号 $ \circ $ を用いる。
45 object B から C への morpshim f と object A から B への morphism g があった時、 f と g を合成すると式\ref{exp:morpshim_compose}となる。
46
47 \begin{equation}
48 f \circ g : A \rightarrow C
49 \label{exp:morphism_compose}
50 \end{equation}
51
52 改めて、morphism の合成の順序が結果に影響しないことを式にすると式\ref{exp:morphism_composition_law}のようになる。
53
54 \begin{eqnarray}
55 f : C \rightarrow D \nonumber \\
56 g : B \rightarrow C \nonumber \\
57 h : A \rightarrow B \nonumber \\
58 (f \circ g) \circ h = f \circ (g \circ h) : A \rightarrow D
59 \label{exp:morphism_composition_law}
60 \end{eqnarray}
61 \end{itemize}
62
63 例えば、object A,B と A から B への moprhism を持つ category は図\ref{fig:simple_category}のようになる。
64
65 % TODO: simple category figure
66
67
68 object を点、morphism を線とした図を commutative diagram (可換図式) と呼ぶ。
69 ある object から object への morphism の合成の path に関わらず結果が同じである時、その図を commutative (可換)と呼ぶ。
70 例えば、式\ref{exp:morphism_composition_law}の category の commutative diagram は図\ref{fig:morphism_composition_law}のようになる。
71
72 % TODO: morphism_composition_law
73
74
75 commutative diagram が commutative である時、moprhism の合成順序が異なっても結果が同じであることを利用して等価性の証明を行なうことを diagram chasing と呼ぶ。
76 ある性質を category に mapping し、diagram chasing を用いて証明を導くことで性質を解析していく。
77
78
4 \section{Functor} 79 \section{Functor}
5 \section{Natural Transformation} 80 \section{Natural Transformation}
6 \section{Monad} 81 \section{Monad}
7 \section{Monads in Functional Programming} 82 \section{Monads in Functional Programming}
8 83