Mercurial > hg > Papers > 2015 > atton-thesis

changeset 18:086fc8bb6ea9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add description for category/functor in program
author Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp>
date Sun, 08 Feb 2015 21:19:55 +0900
parents e2afa8266ecc
children 43d3e7b31fc0
files category.tex fig/delta_example.xbb fig/functor.xbb fig/functor_in_haskell.graffle fig/functor_in_haskell.pdf fig/functor_in_haskell.xbb fig/monad_laws.xbb fig/morphism_composition_law.xbb fig/natural_transformation.xbb fig/non_delta_example.xbb fig/ryukyu.xbb fig/simple_category.xbb src/exec_list_in_haskell.txt src/functor_class.hs src/functor_laws_in_haskell.txt src/list.hs
diffstat 16 files changed, 937 insertions(+), 8 deletions(-) [+]
line wrap: on
line diff
--- a/category.tex	Sun Feb 08 19:57:44 2015 +0900
+++ b/category.tex	Sun Feb 08 21:19:55 2015 +0900
@@ -269,4 +269,165 @@
 
 % }}}
 
+% {{{ Category in Functional Programming
+
+\section{Category in Functional Programming}
+\label{section:category_in_program}
+\ref{section:monad}節では Monad の定義について述べた。
+これからプログラムにおける Monad について述べていく。
+そのために\ref{section:category_in_program}節はプログラムと category の対応について述べる。
+
+プログラムには値と関数のみが存在するとする。
+
+任意の値は型付けられるとする。
+変数x が型 A を持つ時、式\ref{exp:value_in_program}のように記述する。
+
+\begin{equation}
+    \label{exp:value_in_program}
+    x : A
+\end{equation}
+
+関数は値を受けとり値を返すものとする。
+A を取り B を返す関数f の型は式\ref{exp:function_in_program}のように記述する。
+
+\begin{equation}
+    \label{exp:function_in_program}
+    f : A \rightarrow B
+\end{equation}
+
+そして、引数と返り値の型が等しい関数は関数結合できるとする。
+関数結合の記号には $ \circ $ を用いる。
+例えば、 A を取り B を返す関数 f と B を取り C を返す関数 g の合成は式\ref{exp:function_compose_in_program}のようになる。
+
+\begin{eqnarray}
+    \label{exp:function_compose_in_program}
+    f : A \rightarrow B \\ \nonumber
+    g : B \rightarrow C \\ \nonumber
+    g \circ f : A \rightarrow C
+\end{eqnarray}
+
+この時、型を object とし、関数を morphism とする category が構成できる。
+
+この category が category が満たすべき法則を満たしているか確認する。
+
+\begin{itemize}
+    \item 全ての object について identity mapping が存在する
+
+        任意の型 A に対し $ A \rightarrow A $ である関数 id が定義できれば identitiy mapping が存在することになる。
+        任意の型の値x を受けとり、その値を返す関数が id となる。
+
+    \item 同じ obejct が domain と codomain になっている2つのmorphismは合成することができ、合成の順番は結果に影響しない。
+
+        morpshim は関数である。
+        つまり domain は引数の型であり、 codomain は返り値の型となる。
+        morphism の合成は関数合成に相当し、合成の順序によらず引数と返り値の型は同じとなる。
+\end{itemize}
+
+プログラムに対応する category が構成できた。
+特に例として用いているプログラミング言語 Haskell では値と関数は型を持つため、 category との対応が分かりやすい。
+よって例題には Haskell のプログラムを用いることとする。
+
+% }}}
+
+% {{{ Functor in Functional Programming
+
+\section{Functor in Functional Programming}
+\label{section:functor_in_program}
+\ref{section:category_in_program}節ではプログラムとcategoryが対応していることを述べた。
+\ref{section:functor_in_program}節ではプログラムにおけるfunctor について述べる。
+
+プログラムにおけるfunctor は型引数を持つことのできるデータ型に対応する。
+型引数を持つデータ型とは、任意のデータ型に対して構成可能なデータ構造であり、List などが相当する。
+
+たとえば、List は数値の List であっても Bool の List であっても構成可能である。
+この List を、型を受けとり型を返す型であると考えると、渡す型が引数のように振る舞う。
+この引数が型引数である。
+
+\begin{eqnarray}
+    \label{exp:functor_type}
+    A : Type       \\ \nonumber
+    List A : Type  \\ \nonumber
+    List : Type \rightarrow Type
+\end{eqnarray}
+
+つまり、型と関数から構成される category から List 型と List に対応する関数からなる category へと置きかえるような functor が存在すれば良い。
+
+Haskell では functor は \ref{src:functor_in_haskell} のように型クラスとして提供される。
+
+\begin{table}[html]
+    \lstinputlisting[label=src:functor_in_haskell, caption=Haskell における Functor の定義] {src/functor_class.hs}
+\end{table}
+
+functor であることを保証したい型は f として表される。
+そしてデータ型が functor であることを示すためには、 fmap という関数を定義すれば良いことが分かる。
+fmap は型a から型bへの関数を取り、f a を取り f b を返す。
+つまり、f でない型への演算をfの型においても適用するために変換する関数である。
+morpshim は関数であるため、 $ A \rightarrow B $ の morphism を $ F A \rightarrow F B $ へと mapping する役割を担っていることが分かる。
+よって morphism を morphism へと mapping することができるため functor となる。
+
+また、fmap の型に $ f a $ が存在するように、 f は型を引数として受けとっている。
+ここで object は型であるため、 $ A $ の object を $ F(A) $ への mapping する役割をf が担っていることが分かる。
+よって型引数を持つ型f と対応する fmap を定義することにより functor が定義できる。
+なお、 fmap の型を \verb/ fmap :: (a -> b) -> ((f a) -> (f b))/ と読むことで、関数を受けとりfにおける関数に変換していることが分かりやすくなる。
+
+functor の例として、型がInt である変数 x と Int から Bool を返す even 関数を考える。
+このプログラムがなす category C は object が Int であり、 morphism が show となる。
+category C を functor によって別の category に写すことができる。
+
+例えば List がなす category がある。
+
+まずHaskell において List を定義する。
+List は任意の型 a を取り、 List a とする。
+空の List は Nil とし、List a に対して a の値を Cons で追加することによって List を構築するとする。
+
+ここで List が Functor であると定義する。
+fmap は a を取りbを返す関数を取り、List a を取って List b を返す関数である。
+つまり、関数を取ってList の全ての要素に適用することで実現できる。
+
+定義した結果が\ref{src:list_in_haskell} である。
+
+\begin{table}[html]
+    \lstinputlisting[label=src:list_in_haskell, caption=Haskell におけるListの例] {src/list.hs}
+\end{table}
+
+Int型を持つ値x と、Intから Bool返す関数 even を考える。
+even を x に適用すると Bool となる。
+
+この際、x を持つ List の型は List Int であり、 fmap によって even を List Int に適用すると List Bool となる。
+Haskell における実行結果は\ref{src:exec_list_in_haskell} のようになる。
+
+\begin{table}[html]
+    \lstinputlisting[label=src:exec_list_in_haskell, caption=Haskell における List の実行例] {src/exec_list_in_haskell.txt}
+\end{table}
+
+なお、 Haskell において型Aを持つ値xは $ x :: A $ のように記述される。
+x と even からなるプログラムから、型List と fmap を用いることにより List におけるプログラムでも同じように Bool が得られる。
+これを通常のプログラムから List のプログラムへの functor とみなす。
+
+このように、型引数を持つ型とfmapによる関数の変換を定義することによってプログラムにおける functor を実現する。
+可換図で表現すると図\ref{fig:functor_in_haskell}となる。
+
+\begin{figure}[htbp]
+    \begin{center}
+        \includegraphics[scale=0.8]{fig/functor_in_haskell.pdf}
+        \caption{Haskell における Functor の例がなす可換図}
+        \label{fig:functor_in_haskell}
+    \end{center}
+\end{figure}
+
+functor の定義にあたり、\ref{section:functor}節で示したように Functor則を満たすようにデータ型と fmap を定義しなくてはならない。
+
+Haskell における Functor則は\ref{src:functor_laws_in_haskell}のように表される。
+
+\begin{table}[html]
+    \lstinputlisting[label=src:functor_laws_in_haskell, caption=Haskellにおける Functor則] {src/functor_laws_in_haskell.txt}
+\end{table}
+
+1行目がid の保存に、2行目が関数の合成の保存に対応している。
+なお、 Haskell における関数合成は \verb/./ によって行なわれる。
+
+% }}}
+
 \section{Monads in Functional Programming}
+
+プログラムにおける
--- a/fig/delta_example.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/delta_example.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 559.000000 279.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/functor.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/functor.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 545.000000 456.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fig/functor_in_haskell.graffle	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,737 @@
+<?xml version="1.0" encoding="UTF-8"?>
+<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
+<plist version="1.0">
+<dict>
+	<key>ActiveLayerIndex</key>
+	<integer>0</integer>
+	<key>ApplicationVersion</key>
+	<array>
+		<string>com.omnigroup.OmniGraffle</string>
+		<string>139.18.0.187838</string>
+	</array>
+	<key>AutoAdjust</key>
+	<true/>
+	<key>BackgroundGraphic</key>
+	<dict>
+		<key>Bounds</key>
+		<string>{{0, 0}, {558.99997329711914, 783}}</string>
+		<key>Class</key>
+		<string>SolidGraphic</string>
+		<key>ID</key>
+		<integer>2</integer>
+		<key>Style</key>
+		<dict>
+			<key>shadow</key>
+			<dict>
+				<key>Draws</key>
+				<string>NO</string>
+			</dict>
+			<key>stroke</key>
+			<dict>
+				<key>Draws</key>
+				<string>NO</string>
+			</dict>
+		</dict>
+	</dict>
+	<key>BaseZoom</key>
+	<integer>0</integer>
+	<key>CanvasOrigin</key>
+	<string>{0, 0}</string>
+	<key>ColumnAlign</key>
+	<integer>1</integer>
+	<key>ColumnSpacing</key>
+	<real>36</real>
+	<key>CreationDate</key>
+	<string>2015-02-08 11:57:35 +0000</string>
+	<key>Creator</key>
+	<string>atton</string>
+	<key>DisplayScale</key>
+	<string>1 0/72 in = 1 0/72 in</string>
+	<key>GraphDocumentVersion</key>
+	<integer>8</integer>
+	<key>GraphicsList</key>
+	<array>
+		<dict>
+			<key>Bounds</key>
+			<string>{{179, 6.0000074782112733}, {132.00001525878906, 143}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>44</integer>
+			<key>Shape</key>
+			<string>Circle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{10.999979342671566, 16.999999523162842}, {81.000015258789062, 143}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>42</integer>
+			<key>Line</key>
+			<dict>
+				<key>ID</key>
+				<integer>35</integer>
+				<key>Position</key>
+				<real>0.5486111044883728</real>
+				<key>RotationType</key>
+				<integer>0</integer>
+			</dict>
+			<key>Shape</key>
+			<string>Circle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{134, 65}, {27, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>41</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 fmap}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{250, 78}, {57, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>40</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 fmap even}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{18, 78}, {27, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>39</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 even}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>37</integer>
+				<key>Position</key>
+				<real>0.47222220897674561</real>
+			</dict>
+			<key>ID</key>
+			<integer>38</integer>
+			<key>Points</key>
+			<array>
+				<string>{51.499986972066097, 83.000106334686279}</string>
+				<string>{236.00000605950413, 82.999999046325684}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>35</integer>
+				<key>Position</key>
+				<real>0.47222369909286499</real>
+			</dict>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>34</integer>
+			</dict>
+			<key>ID</key>
+			<integer>37</integer>
+			<key>Points</key>
+			<array>
+				<string>{236.00000605950413, 49}</string>
+				<string>{236.00000605950413, 121}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>11</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>11</integer>
+			</dict>
+			<key>ID</key>
+			<integer>36</integer>
+			<key>Points</key>
+			<array>
+				<string>{67, 34.999056839010279}</string>
+				<string>{207, 34.990537965554772}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>Pattern</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>9</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Class</key>
+			<string>LineGraphic</string>
+			<key>Head</key>
+			<dict>
+				<key>ID</key>
+				<integer>33</integer>
+			</dict>
+			<key>ID</key>
+			<integer>35</integer>
+			<key>Points</key>
+			<array>
+				<string>{51.499986972066097, 49}</string>
+				<string>{51.499986972066097, 121}</string>
+			</array>
+			<key>Style</key>
+			<dict>
+				<key>stroke</key>
+				<dict>
+					<key>HeadArrow</key>
+					<string>FilledArrow</string>
+					<key>Legacy</key>
+					<true/>
+					<key>LineType</key>
+					<integer>1</integer>
+					<key>TailArrow</key>
+					<string>0</string>
+				</dict>
+			</dict>
+			<key>Tail</key>
+			<dict>
+				<key>ID</key>
+				<integer>9</integer>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{207, 121}, {58, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>34</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 List Bool}</string>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{31, 121}, {41, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>33</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Bool}</string>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{142, 17}, {19, 14}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>FitText</key>
+			<string>YES</string>
+			<key>Flow</key>
+			<string>Resize</string>
+			<key>ID</key>
+			<integer>15</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>fill</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Pad</key>
+				<integer>0</integer>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 List}</string>
+				<key>VerticalPad</key>
+				<integer>0</integer>
+			</dict>
+			<key>Wrap</key>
+			<string>NO</string>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{207, 21}, {58, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>11</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 List Int}</string>
+			</dict>
+		</dict>
+		<dict>
+			<key>Bounds</key>
+			<string>{{36, 21}, {31, 28}}</string>
+			<key>Class</key>
+			<string>ShapedGraphic</string>
+			<key>ID</key>
+			<integer>9</integer>
+			<key>Shape</key>
+			<string>Rectangle</string>
+			<key>Style</key>
+			<dict>
+				<key>shadow</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+				<key>stroke</key>
+				<dict>
+					<key>Draws</key>
+					<string>NO</string>
+				</dict>
+			</dict>
+			<key>Text</key>
+			<dict>
+				<key>Text</key>
+				<string>{\rtf1\ansi\ansicpg1252\cocoartf1265\cocoasubrtf210
+\cocoascreenfonts1{\fonttbl\f0\fswiss\fcharset0 Helvetica;}
+{\colortbl;\red255\green255\blue255;}
+\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc
+
+\f0\fs24 \cf0 Int}</string>
+			</dict>
+		</dict>
+	</array>
+	<key>GridInfo</key>
+	<dict/>
+	<key>GuidesLocked</key>
+	<string>NO</string>
+	<key>GuidesVisible</key>
+	<string>YES</string>
+	<key>HPages</key>
+	<integer>1</integer>
+	<key>ImageCounter</key>
+	<integer>1</integer>
+	<key>KeepToScale</key>
+	<false/>
+	<key>Layers</key>
+	<array>
+		<dict>
+			<key>Lock</key>
+			<string>NO</string>
+			<key>Name</key>
+			<string>Layer 1</string>
+			<key>Print</key>
+			<string>YES</string>
+			<key>View</key>
+			<string>YES</string>
+		</dict>
+	</array>
+	<key>LayoutInfo</key>
+	<dict>
+		<key>Animate</key>
+		<string>NO</string>
+		<key>circoMinDist</key>
+		<real>18</real>
+		<key>circoSeparation</key>
+		<real>0.0</real>
+		<key>layoutEngine</key>
+		<string>dot</string>
+		<key>neatoSeparation</key>
+		<real>0.0</real>
+		<key>twopiSeparation</key>
+		<real>0.0</real>
+	</dict>
+	<key>LinksVisible</key>
+	<string>NO</string>
+	<key>MagnetsVisible</key>
+	<string>NO</string>
+	<key>MasterSheets</key>
+	<array/>
+	<key>ModificationDate</key>
+	<string>2015-02-08 12:05:09 +0000</string>
+	<key>Modifier</key>
+	<string>atton</string>
+	<key>NotesVisible</key>
+	<string>NO</string>
+	<key>Orientation</key>
+	<integer>2</integer>
+	<key>OriginVisible</key>
+	<string>NO</string>
+	<key>PageBreaks</key>
+	<string>YES</string>
+	<key>PrintInfo</key>
+	<dict>
+		<key>NSBottomMargin</key>
+		<array>
+			<string>float</string>
+			<string>41</string>
+		</array>
+		<key>NSHorizonalPagination</key>
+		<array>
+			<string>coded</string>
+			<string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string>
+		</array>
+		<key>NSLeftMargin</key>
+		<array>
+			<string>float</string>
+			<string>18</string>
+		</array>
+		<key>NSPaperSize</key>
+		<array>
+			<string>size</string>
+			<string>{594.99997329711914, 842}</string>
+		</array>
+		<key>NSPrintReverseOrientation</key>
+		<array>
+			<string>int</string>
+			<string>0</string>
+		</array>
+		<key>NSRightMargin</key>
+		<array>
+			<string>float</string>
+			<string>18</string>
+		</array>
+		<key>NSTopMargin</key>
+		<array>
+			<string>float</string>
+			<string>18</string>
+		</array>
+	</dict>
+	<key>PrintOnePage</key>
+	<false/>
+	<key>ReadOnly</key>
+	<string>NO</string>
+	<key>RowAlign</key>
+	<integer>1</integer>
+	<key>RowSpacing</key>
+	<real>36</real>
+	<key>SheetTitle</key>
+	<string>Canvas 1</string>
+	<key>SmartAlignmentGuidesActive</key>
+	<string>YES</string>
+	<key>SmartDistanceGuidesActive</key>
+	<string>YES</string>
+	<key>UniqueID</key>
+	<integer>1</integer>
+	<key>UseEntirePage</key>
+	<false/>
+	<key>VPages</key>
+	<integer>1</integer>
+	<key>WindowInfo</key>
+	<dict>
+		<key>CurrentSheet</key>
+		<integer>0</integer>
+		<key>ExpandedCanvases</key>
+		<array>
+			<dict>
+				<key>name</key>
+				<string>Canvas 1</string>
+			</dict>
+		</array>
+		<key>Frame</key>
+		<string>{{373, 4}, {693, 874}}</string>
+		<key>ListView</key>
+		<true/>
+		<key>OutlineWidth</key>
+		<integer>142</integer>
+		<key>RightSidebar</key>
+		<false/>
+		<key>ShowRuler</key>
+		<true/>
+		<key>Sidebar</key>
+		<true/>
+		<key>SidebarWidth</key>
+		<integer>120</integer>
+		<key>VisibleRegion</key>
+		<string>{{0, 0}, {558, 735}}</string>
+		<key>Zoom</key>
+		<real>1</real>
+		<key>ZoomValues</key>
+		<array>
+			<array>
+				<string>Canvas 1</string>
+				<real>1</real>
+				<real>1</real>
+			</array>
+		</array>
+	</dict>
+</dict>
+</plist>
Binary file fig/functor_in_haskell.pdf has changed
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/fig/functor_in_haskell.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,8 @@
+%%Title: ./fig/functor_in_haskell.pdf
+%%Creator: extractbb 20140317
+%%BoundingBox: 0 0 324 176
+%%HiResBoundingBox: 0.000000 0.000000 324.000000 176.000000
+%%PDFVersion: 1.3
+%%Pages: 1
+%%CreationDate: Sun Feb  8 21:05:26 2015
+
--- a/fig/monad_laws.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/monad_laws.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 464.000000 137.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/morphism_composition_law.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/morphism_composition_law.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 412.000000 273.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/natural_transformation.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/natural_transformation.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 211.000000 136.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/non_delta_example.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/non_delta_example.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 504.000000 244.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/ryukyu.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/ryukyu.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 595.000000 842.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- a/fig/simple_category.xbb	Sun Feb 08 19:57:44 2015 +0900
+++ b/fig/simple_category.xbb	Sun Feb 08 21:19:55 2015 +0900
@@ -4,5 +4,5 @@
 %%HiResBoundingBox: 0.000000 0.000000 205.000000 82.000000
 %%PDFVersion: 1.3
 %%Pages: 1
-%%CreationDate: Sun Feb  8 16:05:26 2015
+%%CreationDate: Sun Feb  8 21:05:26 2015
 
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/exec_list_in_haskell.txt	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,14 @@
+*Main> let x = 100 :: Int
+*Main> let even = even :: Int -> Bool
+*Main> :type x
+x :: Int
+*Main> :type even
+even :: Int -> Bool
+*Main> :type (even x)
+(even x) :: Bool
+
+*Main> let list = Cons x Nil
+*Main> :type list
+list :: List Int
+*Main> :type fmap even list
+fmap even list :: List Bool
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/functor_class.hs	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,2 @@
+class Functor f where
+  fmap :: (a -> b) -> f a -> f b
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/functor_laws_in_haskell.txt	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,2 @@
+fmap id      = id
+fmap (p . q) = (fmap p) . (fmap q)
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/list.hs	Sun Feb 08 21:19:55 2015 +0900
@@ -0,0 +1,5 @@
+data List a = Nil | Cons a (List a) deriving (Show)
+
+instance Functor List where
+    fmap f Nil = Nil
+    fmap f (Cons x xs) = Cons (f x) (fmap f xs)