# HG changeset patch # User Yasutaka Higa # Date 1423397995 -32400 # Node ID 086fc8bb6ea9cd315709cab48593a79b349b069b # Parent e2afa8266ecc9d87857c9a1fd107ffc656d60afb Add description for category/functor in program diff -r e2afa8266ecc -r 086fc8bb6ea9 category.tex --- 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} + +プログラムにおける diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/delta_example.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/functor.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/functor_in_haskell.graffle --- /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 @@ + + + + + ActiveLayerIndex + 0 + ApplicationVersion + + com.omnigroup.OmniGraffle + 139.18.0.187838 + + AutoAdjust + + BackgroundGraphic + + Bounds + {{0, 0}, {558.99997329711914, 783}} + Class + SolidGraphic + ID + 2 + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + + BaseZoom + 0 + CanvasOrigin + {0, 0} + ColumnAlign + 1 + ColumnSpacing + 36 + CreationDate + 2015-02-08 11:57:35 +0000 + Creator + atton + DisplayScale + 1 0/72 in = 1 0/72 in + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{179, 6.0000074782112733}, {132.00001525878906, 143}} + Class + ShapedGraphic + ID + 44 + Shape + Circle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + + + + Bounds + {{10.999979342671566, 16.999999523162842}, {81.000015258789062, 143}} + Class + ShapedGraphic + ID + 42 + Line + + ID + 35 + Position + 0.5486111044883728 + RotationType + 0 + + Shape + Circle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + + + + Bounds + {{134, 65}, {27, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 41 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\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} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{250, 78}, {57, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 40 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\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} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{18, 78}, {27, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 39 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\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} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + Head + + ID + 37 + Position + 0.47222220897674561 + + ID + 38 + Points + + {51.499986972066097, 83.000106334686279} + {236.00000605950413, 82.999999046325684} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + Pattern + 1 + TailArrow + 0 + + + Tail + + ID + 35 + Position + 0.47222369909286499 + + + + Class + LineGraphic + Head + + ID + 34 + + ID + 37 + Points + + {236.00000605950413, 49} + {236.00000605950413, 121} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 11 + + + + Class + LineGraphic + Head + + ID + 11 + + ID + 36 + Points + + {67, 34.999056839010279} + {207, 34.990537965554772} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + Pattern + 1 + TailArrow + 0 + + + Tail + + ID + 9 + + + + Class + LineGraphic + Head + + ID + 33 + + ID + 35 + Points + + {51.499986972066097, 49} + {51.499986972066097, 121} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 9 + + + + Bounds + {{207, 121}, {58, 28}} + Class + ShapedGraphic + ID + 34 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\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} + + + + Bounds + {{31, 121}, {41, 28}} + Class + ShapedGraphic + ID + 33 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\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} + + + + Bounds + {{142, 17}, {19, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 15 + Shape + Rectangle + Style + + fill + + Draws + NO + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Pad + 0 + Text + {\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} + VerticalPad + 0 + + Wrap + NO + + + Bounds + {{207, 21}, {58, 28}} + Class + ShapedGraphic + ID + 11 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\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} + + + + Bounds + {{36, 21}, {31, 28}} + Class + ShapedGraphic + ID + 9 + Shape + Rectangle + Style + + shadow + + Draws + NO + + stroke + + Draws + NO + + + Text + + Text + {\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} + + + + GridInfo + + GuidesLocked + NO + GuidesVisible + YES + HPages + 1 + ImageCounter + 1 + KeepToScale + + Layers + + + Lock + NO + Name + Layer 1 + Print + YES + View + YES + + + LayoutInfo + + Animate + NO + circoMinDist + 18 + circoSeparation + 0.0 + layoutEngine + dot + neatoSeparation + 0.0 + twopiSeparation + 0.0 + + LinksVisible + NO + MagnetsVisible + NO + MasterSheets + + ModificationDate + 2015-02-08 12:05:09 +0000 + Modifier + atton + NotesVisible + NO + Orientation + 2 + OriginVisible + NO + PageBreaks + YES + PrintInfo + + NSBottomMargin + + float + 41 + + NSHorizonalPagination + + coded + BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG + + NSLeftMargin + + float + 18 + + NSPaperSize + + size + {594.99997329711914, 842} + + NSPrintReverseOrientation + + int + 0 + + NSRightMargin + + float + 18 + + NSTopMargin + + float + 18 + + + PrintOnePage + + ReadOnly + NO + RowAlign + 1 + RowSpacing + 36 + SheetTitle + Canvas 1 + SmartAlignmentGuidesActive + YES + SmartDistanceGuidesActive + YES + UniqueID + 1 + UseEntirePage + + VPages + 1 + WindowInfo + + CurrentSheet + 0 + ExpandedCanvases + + + name + Canvas 1 + + + Frame + {{373, 4}, {693, 874}} + ListView + + OutlineWidth + 142 + RightSidebar + + ShowRuler + + Sidebar + + SidebarWidth + 120 + VisibleRegion + {{0, 0}, {558, 735}} + Zoom + 1 + ZoomValues + + + Canvas 1 + 1 + 1 + + + + + diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/functor_in_haskell.pdf Binary file fig/functor_in_haskell.pdf has changed diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/functor_in_haskell.xbb --- /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 + diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/monad_laws.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/morphism_composition_law.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/natural_transformation.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/non_delta_example.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/ryukyu.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 fig/simple_category.xbb --- 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 diff -r e2afa8266ecc -r 086fc8bb6ea9 src/exec_list_in_haskell.txt --- /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 diff -r e2afa8266ecc -r 086fc8bb6ea9 src/functor_class.hs --- /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 diff -r e2afa8266ecc -r 086fc8bb6ea9 src/functor_laws_in_haskell.txt --- /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) diff -r e2afa8266ecc -r 086fc8bb6ea9 src/list.hs --- /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)