モナド (プログラミング)
\text{call/cc} \colon \left( \left( T \rarr \left( T' \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R \right) \rarr \left( T \rarr R \right) \rarr R = f \mapsto k \mapsto \left( f \left( t \mapsto x \mapsto k \, t \right) \, k \right)
研究者により発見されたモナドになる概念を挙げる。
自由モナドは自由モノイドと似ていて、直観的には、使う型に依存せずにモナド則(またはモノイド則)を満たすようにできる汎用の構造である。
型 t に対して、t の自由モノイドは [t] であり、結合的な二項演算子として ++、単位元として [] を選ぶ。Haskellでは以下のように書ける。
具体的なモノイドとでは、値 t1,t2,...,tn を二項演算で足すことができるが、[] では単に、結合 [t1,t2,...,tn] になるだけであり、単に「一緒に集めた」だけである。ここで、「一緒に集めた」結果がどうなるべきかは定めない。
自由モナドも同じ考えに基づいて定義される。上の定義 List t = Nil | Cons t (List t) に函手を挿入することで、次の定義を得る。
List が値のリストを保存するのと違って、Free はドメインの値を決めた函手のリストを保存する。Free の Functor と Monad インスタンスの定義によると、受け取った関数を fmap でリストに落としているだけしかしていないことが分かる。
コモナドはモナドの圏論的な双対である。型構築子 W T と2つの演算 extract と extend を持つ。extract の型は W T → T であり、extend の型は (W T → T' ) → W T → W T'  であり、以下のコモナド則を満たすとする。
\text{extend} \,\, \text{extract} = \text{id}
\text{extract} \circ (\text{extend} \, f) = f
(\text{extend} \, f) \circ (\text{extend} \, g) = \text{extend} \, (f \circ (\text{extend} \, g))
他の方法として、fmap と extract と duplicate を使った定義もできる。fmap と extract により W は余基点付き函手となる。duplicate がコモナドを特徴付ける。duplicate の型は W T → W (W T) であり、次の規則を満たす。
\text{extract} \circ \text{duplicate} = \text{id}
\text{fmap} \, \text{extract} \circ \text{duplicate} = \text{id}
\text{duplicate} \circ \text{duplicate} = \text{fmap} \, \text{duplicate} \circ \text{duplicate}
\text{fmap}: (A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto \text{extend} \, (f \circ \text{extract})
\text{duplicate}: \mathrm{W} \, A \rarr \mathrm{W} \, \mathrm{W} \, A = \text{extend} \, \text{id}
\text{extend}: (\mathrm{W} \, A \rarr B) \rarr \mathrm{W} \, A \rarr \mathrm{W} \, B = f \mapsto (\text{fmap} \, f) \circ \text{duplicate}
で与えられる。
モナドが副作用を表現すると言われているのに対して、コモナド W は一種の「文脈」を表している。extract は文脈から値を取り出す関数である。extend は型 W A → B を持つ「文脈依存の関数」を合成してパイプラインを作る。
恒等コモナドはもっとも単純なコモナドであり、型 T をそれ自身にうつす。extractは恒等関数であり、extendは関数適用である。
積コモナドは型 T を積の型 C \times T にうつす。ここで C はコモナドの文脈の型である。コモナド演算は
\text{extract}: (C \times T) \rarr T = (c, t) \mapsto t
\text{extend}: ((C \times A) \rarr B) \rarr C \times A \rarr C \times B = f \mapsto (c, a) \mapsto (c, f \, (c, a))
\text{fmap}: (A \rarr B) \rarr (C \times A) \rarr (C \times B) = (c, a) \mapsto (c, f \, a)
\text{duplicate}: (C \times A) \rarr (C \times (C \times A)) = (c, a) \mapsto (c, (c, a))
で定める。
関数コモナドは型 T を関数型 M \rarr T にうつす。ここで、M はモノイド構造を持つ型である。コモナド演算は
\text{extract}: (M \rarr T) \rarr T = f \mapsto f \, \varepsilon
\text{extend}: ((M \rarr A) \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto m \mapsto f \, (m' \mapsto g \, (m * m'))
\text{fmap}: (A \rarr B) \rarr (M \rarr A) \rarr M \rarr B = f \mapsto g \mapsto (f \circ g)
\text{duplicate}: (M \rarr A) \rarr M \rarr (M \rarr A) = f \mapsto m \mapsto m' \mapsto f \, (m * m')
で定める。εと * はモノイド M の単位元と二項演算子である。
余状態コモナドは型 T を型 (S \rarr T) \times S にうつす。ここで S はストアの型である。コモナド演算は
\text{extract}: ((S \rarr T) \times S) \rarr T = (f, s) \mapsto f \, s
\text{extend}: (((S \rarr A) \times S) \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S \,= f \mapsto (g, s) \mapsto ((s' \mapsto f \, (g, s')), s)
\text{fmap}: (A \rarr B) \rarr ((S \rarr A) \times S) \rarr (S \rarr B) \times S = f \mapsto (f', s) \mapsto (f \circ f', s)
\text{duplicate}: ((S \rarr A) \times S) \rarr (S \rarr ((S \rarr A) \times S)) \times S = (f, s) \mapsto ((s' \mapsto (f, s')), s)
で定義される。