# HG changeset patch # User Yasutaka Higa # Date 1423448220 -32400 # Node ID fc44782929a7a3d87cf3aedfe4a79178efcd963e # Parent 7d94faaeb4486db57d02c4101494cf9e7d49fd06 Add monad in Haskell diff -r 7d94faaeb448 -r fc44782929a7 category.tex --- a/category.tex Mon Feb 09 09:47:09 2015 +0900 +++ b/category.tex Mon Feb 09 11:17:00 2015 +0900 @@ -481,7 +481,97 @@ % }}} +% {{{ Monads in Functional Programming \section{Monads in Functional Programming} \label{section:monads_in_program} +\ref{section:natural_transformation_in_program}節ではプログラムにおける natural transformation について述べた。 +\ref{section:monads_in_program}節ではプログラムにおける Monad について述べる。 + +Monad とは 図\ref{fig:monad_laws}の可換図を満たす $ triple (T, \eta, \mu) $ であった。 +T は functorであり、$ \eta $ は $ A \rightarrow T A $ 、 $ \mu $ は $ T^2 A \rightarrow T $ の natural transformation であった。 + +Haskell において functor は型引数を持つ型とfmapで表現され、 natural transformation は図\ref{fig:natural_transformation}の可換図を満たす関数であった。 +つまり、型と fmap、2つの関数を適切に定義することによって表現される。 + +Haskell において、 $ \eta $ と $ \mu $ の型は以下のようになる。 + +\begin{itemize} + \item eta : \verb/A -> T A/ + + ここで、 T は functor である型引数を持つ型 + + \item mu : \verb/T (T A) -> T A/ + + 本来の $ \mu $ は $ T^2 \rightarrow T $ であるため、 T によって2度 mapping された値から T によって mapping された値への関数になる。 +\end{itemize} + +Monad 則により、Tに対する演算は単位元のように振る舞わせることと、演算の可換性を持つ。 +ここでメタ計算を T に対する演算として定義する。 +そうすることで、型Aを持つ値に対する計算から functor Tにより T の計算へと変換し、メタ計算部分は T に対する演算として行なうことで任意のAに対応するメタ計算を行なうことができるようになる。 +これがプログラムにおける monad を通したデータ型とメタ計算の対応である。 +そして、 Monad 則はメタ計算をTに対して $ \eta $ と $ \mu $ で定義する際に満たすべき制約として機能する。 + +Haskell において List は monad としても振る舞う。 +List は nondeterminism (非決定性)を表現するデータ構造である。 +List に対する演算を行なう際、結果としてありうる値を全て列挙することにより非決定性を表現しようとするものである。 + +List において非決定性を表現する時、$ \eta $ は通常の値から List を構築する関数、 $ \mu $ は List の List から List を返す concat 関数となる。 +$ \mu $ で何故非決定性を表現できるかと述べる。 +まず、List a と、 a から List a を返す関数を考える。 +List a がありうる値の集合で、関数が値から取りうる値を計算して返すものだとする。 +List a に対して fmap することで、ありうる値に対して全ての取りうる値を計算することができる。 +この際、 List a に対して a から List a を返す関数を適用するために List a を持つ List が構築される。 +ネストされた List を、全ての取りうる値として通常の List に戻すために concat を用いる。 + +ここで、Haskell における monad の型クラスを振り返る(リスト\ref{src:monad_class})。 +Haskell においては monad は Monad 型クラスとして提供されているが、$ \eta $ と $ \mu $ による記述はされていない。 +これは、Haskell がメタ計算との対応として Kleisli Category の triple を採用しているからである。 +monad と Kleisli category は互いに同型であるために相互に変換することができる。 +また、 category や program の文脈が変わることで $ \eta $ を unit と呼んだり、 $ \mu $ を join と呼んだり、 \verb/>>=/ を bind と呼んだりする。 +しかし今までの解説には $ \eta $ と $ \mu $ を用いているために、このまま $ \eta $ と $ \mu $ で解説していくこととする。 + +なお、monad と Kleisli triple との変換は Haskell においてはリスト \ref{src:monad_and_bind} のようになる。 + +\begin{table}[html] + \lstinputlisting[label=src:monad_and_bind, caption=Haskell における monad と Kleisli triple との変換] {src/monad_and_bind.hs} +\end{table} + +では List を用いて非決定性を表現した例を示す。 + +まずは List を monad とする(リスト\ref{src:list_monad})。 + +\begin{table}[html] + \lstinputlisting[label=src:list_monad, caption= Haskell における List に対する monad の定義] {src/list_monad.hs} +\end{table} + +先程述べたように、 $ \eta $ は値を List とする関数、 $ \mu $ はList を内包する List を全て結合する関数である。 + +この List Monad を実行する。 +まずはありうる値のリストとして100, 200, 400 を持つ List の x を考える。 +次に、値から取りうる計算結果を返す関数として f を定義する。 +取りうる計算結果として、1加算した結果、10加算した結果、2乗した結果が存在するとし、結果は List として返す。 + +この x と f から全ての取りうる値を計算した結果がリスト\ref{src:exec_list_monad}である。 + +\begin{table}[html] + \lstinputlisting[label=src:exec_list_monad, caption= Haskell において List を monad として実行した例] {src/exec_list_monad.txt} +\end{table} + +3つのありうる値に対して、取りうる3つの計算結果から生成された9つの値が全て計算されている。 +このように、ある性質を持つデータ型と、そのデータ型を返す関数の演算によって通常の計算に加えてメタ計算を実現することができた。 + +これがプログラムにおける Monad であり、結果としてメタ計算とデータ型の対応が得られる。 + +なお、 Haskell においても Monad 則は存在し、リスト\ref{src:monad_laws_in_haskell}の性質を満たすよう $ \eta $ や $ \mu $ を定義しなくてはならない。 + +\begin{table}[html] + \lstinputlisting[label=src:monad_laws_in_haskell, caption=Haskell における Monad 則] {src/monad_laws_in_haskell.hs} +\end{table} + +1つめの則が図\ref{fig:monad_laws}における左側の可換図に対応し、Tに対する演算の可換性を示す。 +2つめの則が図\ref{fig:monad_laws}における右側の可換図に対応し、Tに対する演算における単位元のような振舞いを強制する。 +3つめの則が eta に対する natural transformation の要請であり、4つめの則が mu に対する natural transformation の要請である。 + +% }}} diff -r 7d94faaeb448 -r fc44782929a7 fig/natural_transformation_in_haskell.graffle --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig/natural_transformation_in_haskell.graffle Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,674 @@ + + + + + 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-09 00:41:49 +0000 + Creator + atton + DisplayScale + 1 0/72 in = 1 0/72 in + GraphDocumentVersion + 8 + GraphicsList + + + Bounds + {{36, 84}, {57, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 42 + 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 + {{283, 84}, {57, 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 fmap even} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + Head + + ID + 34 + + ID + 38 + Points + + {264.4999902382379, 66} + {264.4999902382379, 116} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 11 + + + + Class + LineGraphic + Head + + ID + 33 + + ID + 37 + Points + + {113.49999131984168, 66} + {113.49999131984168, 116} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 9 + + + + Bounds + {{175, 107}, {16, 14}} + Class + ShapedGraphic + FitText + YES + Flow + Resize + ID + 36 + 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 tail} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + Head + + ID + 34 + + ID + 35 + Points + + {144, 130.0000119638957} + {234, 130.0000119638957} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 33 + + + + Bounds + {{234, 116}, {61, 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 + {{83, 116}, {61, 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 List Bool} + + + + Bounds + {{175, 26}, {16, 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 tail} + VerticalPad + 0 + + Wrap + NO + + + Class + LineGraphic + Head + + ID + 11 + + ID + 12 + Points + + {144, 52.000008045718587} + {234, 52.000008045718587} + + Style + + stroke + + HeadArrow + FilledArrow + Legacy + + LineType + 1 + TailArrow + 0 + + + Tail + + ID + 9 + + + + Bounds + {{234, 38}, {61, 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 + {{83, 38}, {61, 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 List 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-09 00:44:08 +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 7d94faaeb448 -r fc44782929a7 fig/natural_transformation_in_haskell.pdf Binary file fig/natural_transformation_in_haskell.pdf has changed diff -r 7d94faaeb448 -r fc44782929a7 fig/natural_transformation_in_haskell.xbb --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/fig/natural_transformation_in_haskell.xbb Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,8 @@ +%%Title: ./fig/natural_transformation_in_haskell.pdf +%%Creator: extractbb 20140317 +%%BoundingBox: 0 0 322 136 +%%HiResBoundingBox: 0.000000 0.000000 322.000000 136.000000 +%%PDFVersion: 1.3 +%%Pages: 1 +%%CreationDate: Mon Feb 9 09:44:36 2015 + diff -r 7d94faaeb448 -r fc44782929a7 src/exec_list_monad.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/exec_list_monad.txt Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,4 @@ +*Main> let x = Cons 100 (Cons 200 (Cons 400 Nil)) +*Main> let f = \x -> Cons (x+1) (Cons (x+10) (Cons (x*x) Nil)) +*Main> x >>= f +Cons 101 (Cons 110 (Cons 10000 (Cons 201 (Cons 210 (Cons 40000 (Cons 401 (Cons 410 (Cons 160000 Nil)))))))) diff -r 7d94faaeb448 -r fc44782929a7 src/exec_tail_in_haskell.txt --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/exec_tail_in_haskell.txt Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,22 @@ +*Main> :type Main.tail +Main.tail :: List a -> List a +*Main> let list = Cons 100 (Cons 200 (Cons 300 Nil)) :: List Int +*Main> :type list +list :: List Int +*Main> :type even :: Int -> Bool +even :: Int -> Bool :: Int -> Bool + +*Main> :type (fmap even list) +fmap even list :: List Bool +*Main> :type Main.tail (fmap even list) +Main.tail (fmap even list) :: List Bool + +*Main> :type (Main.tail list) +Main.tail list :: List Int +*Main> :type fmap even (Main.tail list) +fmap even (Main.tail list) :: List Bool + +*Main> Main.tail (fmap even list) +Cons True (Cons True Nil) +*Main> fmap even (Main.tail list) +Cons True (Cons True Nil) diff -r 7d94faaeb448 -r fc44782929a7 src/list_monad.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/list_monad.hs Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,17 @@ +append :: List a -> List a -> List a +append Nil xs = xs +append (Cons x xs) xss = Cons x (append xs xss) + +concat :: List (List a) -> List a +concat Nil = Nil +concat (Cons x xs) = append x (Main.concat xs) + +eta :: a -> List a +eta x = Cons x Nil + +mu :: List (List a) -> List a +mu = Main.concat + +instance Monad List where + return x = eta x + li >>= f = mu (fmap f li) diff -r 7d94faaeb448 -r fc44782929a7 src/monad_and_bind.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/monad_and_bind.hs Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,5 @@ +return x = eta x +x >>= f = mu (fmap f x) + +eta x = return x +mu x = (>>= id) diff -r 7d94faaeb448 -r fc44782929a7 src/monad_laws_in_haskell.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/monad_laws_in_haskell.hs Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,5 @@ +mu . fmap mu = mu . mu +mu . fmap eta = mu . eta = id + +eta . f = fmap f . eta +mu . fmap (fmap f) = fmap f . mu diff -r 7d94faaeb448 -r fc44782929a7 src/natural_transformation_list.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/natural_transformation_list.hs Mon Feb 09 11:17:00 2015 +0900 @@ -0,0 +1,3 @@ +tail :: List a -> List a +tail Nil = Nil +tail (Cons x xs) = xs