# HG changeset patch # User Yasutaka Higa # Date 1423976827 -32400 # Node ID ba7f0b5454ab8056ab0d9ad13bd5df86582e5c56 # Parent 422e96fda05a7ec74cd1fd90f702be738ed5cfe6 Add description for DeltaM definition diff -r 422e96fda05a -r ba7f0b5454ab delta.tex --- a/delta.tex Sun Feb 15 12:35:58 2015 +0900 +++ b/delta.tex Sun Feb 15 14:07:07 2015 +0900 @@ -2,7 +2,8 @@ \label{chapter:delta} 本研究では Monad によりプログラムの変更を定義する。 -第\ref{chapter:delta}章ではプログラムの変更が Monad として表現可能であることを示す。 +第\ref{chapter:delta}章ではプログラムの変更を表す Delta Monad を定義し、その使用例とメタ計算の例を示す。 +なお、Monad についての定義と解説は第\ref{chapter:category}章と第\ref{chapter:functional_programming}章にて行なう。 % {{{ Delta Monad の定義 @@ -48,12 +49,12 @@ 型A を持つx の値をメタ計算と対応して型 T A とした値を x' 、メタ計算による関数の拡張を * と記述すると、式\ref{exp:non_failure_program} の式は式\ref{exp:failure_program} のように書ける。 \begin{equation} - {g*} ( {f*} ( x' )) + g^{*} ( f^{*} ( x' )) \label{exp:failure_program} \end{equation} -ここで重要な点は、元の関数 $ f $ と $g$ から $f*$ と $g*$ が導けることである。 -メタ計算が無い関数 $ f $ とメタ計算を持つ関数 $ f * $ が1対1に対応することは Monad により保証されている。 +ここで重要な点は、元の関数 $ f $ と $g$ から $f^{*}$ と $g^{*}$ が導けることである。 +メタ計算が無い関数 $ f $ とメタ計算を持つ関数 $ f^{*} $ が1対1に対応することは Monad により保証されている。 このように、値と関数で表されたプログラムにおいてメタ計算を用いることで、計算を拡張することができる。 プログラムの変更をメタ計算として記述することを考える。 @@ -72,6 +73,7 @@ ここで、プログラムが変更される際に過去のバージョンのプログラムも保存するメタ計算を提案する。 全ての変更単位で変更されたプログラムを保存し、それらを比較することでプログラムの変更を表現しようと考えた。 このメタ計算を表す Monad を Delta Monad と呼ぶ。 +なお、この Delta Monadが Monad であることの証明は \ref{chapter:proof_delta} 章で行なう % }}} @@ -137,7 +139,7 @@ その際、先頭の値を取り出すために headDelta 関数を、先頭以外の値を取り出すために tailDelta 関数を用いる。 \end{itemize} -なお、中置関数 \verb/>>=/ で用いたコンストラクタによる処理の分岐はパターンマッチと呼ばれる。 +なお、中置関数 \verb/>>=/ や headDelta関数などで用いたコンストラクタによる処理の分岐はパターンマッチと呼ばれる。 Haskell ではコンストラクタごとに関数を記述することでパターンマッチを実現する。 % }}} diff -r 422e96fda05a -r ba7f0b5454ab delta_with_monad.tex --- a/delta_with_monad.tex Sun Feb 15 12:35:58 2015 +0900 +++ b/delta_with_monad.tex Sun Feb 15 14:07:07 2015 +0900 @@ -1,4 +1,73 @@ \chapter{任意の Monad と Delta の組み合せ} +\label{chapter:delta_with_monad} +第\ref{chapter:proof_delta}章ではプログラムの変更を表現する Delta Monad が Monad であることを証明した。 +第\ref{chapter:delta_with_monad}章では、Delta Monad と、他の Monad との組み合せを考える。 +特に他の Monad のメタ計算も同時に実行できるようなデータ DeltaM を定義し、利用例を示す。 + +% {{{ Monad と組み合せた Delta である DeltaM + \section{Monad と組み合せた Delta である DeltaM} +\label{section:deltaM} +functional programming における monad とはデータ構造をメタ計算の対応付けであった。 +プログラミング言語 Haskell においては入出力や非決定性演算といった処理が monad として提供される。 +そのため、プログラムの変更を表現する Delta Monad では他の monad と組み合せることが可能でなくてはならない。 +Delta Monad を拡張し、Delta Monad の内部の monad のメタ計算を実行するデータ型 DeltaM を Haskell で定義する。 + +データ型 DeltaM と、DeltaM に対する Monad の instance 定義を示す(リスト\ref{src:deltaM_definition})。 + +\begin{table}[html] + \lstinputlisting[label=src:deltaM_definition, + caption= DeltaM の定義と Monad の instance 定義, + escapechar=&] + {src/deltaM_definition.hs} +\end{table} + +データ型 DeltaM は2つの型引数を持つ。 +型引数a と型引数を持つ型引数 m である。 +m に対して a を適用した型を持つ DeltaM から DeltaM コンストラクタを用いて DeltaM 型を構成できる。 +型名とコンストラクタ名が同一になっているので注意が必要である。 +m が Monad であり、 a が Monad が内包する型を表す。 + +次にいくつかの関数を定義する。 +unDeltaM は DeltaM から Delta へと戻す関数である。 +headDeltaM はDelta から先頭の値を取り出す。 +バージョン管理された Delta から最新のバージョンを取り出すことに相当する。 +tailDeltaM はDelta から先頭の値を取り除く。 +これはバージョン管理された Delta から最新以外のバージョンに対して処理を行う時に用いる。 + +DeltaM の instance 定義では \verb/>>=/ ではなく mu を介して行なう。 +ここで2つの新たな記法を解説する。 + +\begin{itemize} + \item \verb/ (Functor m) => ... / + + mu や Monad の instance 宣言に利用されている記法で、型制約を示す記号である。 + ある型 m が Functor の instance であることを示す。 + 例えば、 mu に記述されている \verb/(Functor m, Monad m) => ... / は型 m が Functor と Monad の instance である時に mu に適用できることを示す。 + 型制約により、型 m a は Functor である保証がつくため、 m a の値に対して fmap をかけることできる。 + + \item \verb/ d@(DeltaM (Mono ...)) / + + パターンマッチにおける記法で、asパターンと呼ばれる。 + パターンマッチにおいてコンストラクタを指定したのち、全体の値を \verb/@/ の前の変数に束縛する。 + 例えば \verb/ m@(Mono x) / と指定すると、 \verb/Mono x/ が m に束縛される。 + この記法を採用するメリットは、コンストラクタでパターンマッチしたものの、値はコンストラクタを含んだまま処理したい時にタイプ数を省略できることにある。 +\end{itemize} + +関数 mu ではDelta におけるバージョンの管理と内部の Monad のメタ計算の両方を一度に行なう。 + +バージョンが1であった場合は内部の DeltaM から fmap headDeltaM を用いて値を取り出し、 \verb/>>= id/ で内部の Monad のメタ計算を行なう。 +同じように、バージョンが1以上であった場合は先頭のバージョンに対しメタ計算を行なってから、残りのバージョンに対して再帰的に mu を行なう。 + +mu が定義できたので、 DeltaM を Monad の instance とする。 +m が Functor と Monad である時のみ、 DeltaM は Monad となる。 + +return は通常の値を内部の Monad の return でメタ計算に対応させ、バージョン1である Mono としてから DeltaM とする。 +中置関数 \verb/>>=/ は fmap と mu を用いて定義する。 + +以上で Delta Monad と 他の Monad を組み合せるための DeltaM が定義できた。 + +% }}} + \section{DeltaM を用いたプログラムの例} - +\label{section:deltaM_example} diff -r 422e96fda05a -r ba7f0b5454ab src/deltaM_definition.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/deltaM_definition.hs Sun Feb 15 14:07:07 2015 +0900 @@ -0,0 +1,25 @@ +data DeltaM m a = DeltaM (Delta (m a)) deriving (Show) + +-- DeltaM utils + +unDeltaM :: DeltaM m a -> Delta (m a) +unDeltaM (DeltaM d) = d + +headDeltaM :: DeltaM m a -> m a +headDeltaM (DeltaM d) = headDelta d + +tailDeltaM :: DeltaM m a -> DeltaM m a +tailDeltaM (DeltaM d) = DeltaM $ tailDelta d + +-- DeltaM instance definitions + +mu :: (Functor m, Monad m) => DeltaM m (DeltaM m a) -> DeltaM m a +mu d@(DeltaM (Mono _)) = + DeltaM (Mono ((>>= id) (fmap headDeltaM (headDeltaM d)))) +mu d@(DeltaM (Delta _ _)) = + DeltaM (Delta ((>>= id) (fmap headDeltaM (headDeltaM d))) + (unDeltaM (mu (fmap tailDeltaM (tailDeltaM d))))) + +instance (Functor m, Monad m) => Monad (DeltaM m) where + return x = DeltaM (Mono (return x)) + d >>= f = mu (fmap f d) diff -r 422e96fda05a -r ba7f0b5454ab src/deltaM_example.hs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/deltaM_example.hs Sun Feb 15 14:07:07 2015 +0900 @@ -0,0 +1,46 @@ +module Example.DeltaM where + +import Control.Monad.Writer +import Data.Numbers.Primes -- $ cabal install primes + +import Delta +import DeltaM + + +-- DeltaM examples + +-- DeltaM example utils +type DeltaLog = Writer [String] +type DeltaWithLog = DeltaM DeltaLog + +returnW :: (Show a) => a -> DeltaLog a +returnW x = do tell $ [show x] + return x + +dmap :: (m a -> b) -> DeltaM m a -> Delta b +dmap f (DeltaM d) = fmap f d + +deltaWithLogFromList :: (Show a) => [a] -> DeltaWithLog a +deltaWithLogFromList xs = DeltaM $ deltaFromList $ fmap returnW xs + + +-- example : prime filter +-- usage : runWriter $ checkOut 0 $ numberCountM 30 -- run specific version +-- : dmap runWriter $ numberCountM 30 -- run all version + +generatorM :: Int -> DeltaWithLog [Int] +generatorM x = let intList = [1..x] in + DeltaM $ deltaFromList $ fmap returnW $ replicate 2 intList + +numberFilterM :: [Int] -> DeltaWithLog [Int] +numberFilterM xs = let primeList = filter isPrime xs + evenList = filter even xs in + DeltaM $ deltaFromList $ fmap returnW [primeList, evenList] + + +countM :: [Int] -> DeltaWithLog Int +countM xs = let numberCount = length xs in + DeltaM $ deltaFromList $ fmap returnW $ replicate 2 numberCount + +numberCountM :: Int -> DeltaWithLog Int +numberCountM x = generatorM x >>= numberFilterM >>= countM diff -r 422e96fda05a -r ba7f0b5454ab src/delta_instance_monad.hs --- a/src/delta_instance_monad.hs Sun Feb 15 12:35:58 2015 +0900 +++ b/src/delta_instance_monad.hs Sun Feb 15 14:07:07 2015 +0900 @@ -1,3 +1,12 @@ +headDelta :: Delta a -> a +headDelta (Mono x) = x +headDelta (Delta x _) = x + +tailDelta :: Delta a -> Delta a +tailDelta (Mono x) = Mono x +tailDelta (Delta _ ds) = ds + + instance Monad Delta where return x = Mono x (Mono x) >>= f = f x