汎関数プログラミング(24)−汎関数データ型−Monad,monadic programming
前節ではMonadを紹介しました.Monadは高度に要約された抽象モデルであることを知っています.Monadを作成する目的は、重複符号化を回避するために、様々なデータ型の共通コンポーネント関数を抽出してコンポーネントライブラリに集約することであるようです.これらはMonadとは何か明確な答えを提供することができますか?まず、前節で設計したMonadコンポーネントライブラリの基本的な関数から、Monadの理解を深めます.
それぞれM[A]対応List[A],Option[A]およびPar[A]を用いてsequence関数の役割を解析する.
1.sequence>>>map 2で実現>>>flatMapで実現:
List:sequence[A](lm:List[M[A]):M[List[A]>>sequence[A](lm:List[List[A]):List[List[A]]について
>>> map2(list(list1),list(list2)){_::_} ,リストに封入されたリストを要素分割クロスコンビネーションし、
例:(List(List(1,2),List(3,4)>>>>List[Int]=List(List(1,3),List(1,4),List(2,3),List(2,3),List(2,4))
sequenceの役割はリストに現れる.map 2機能.リストmap 2はListである.flatMapが実現しました.したがって、sequenceの動作は、リストインスタンスにおけるflatMapの実装方法に依存する.
Option:sequence[A](lm:List[M[A]):M[List[A]>>>sequence[A](lm:List[Option[A]):List[Option[A]]について
>>> map2(list(opton1),list(option2)){_::_} ,リストにカプセル化された要素option値をリストにリストし、
例:(List(Some(1),Some(2),Some(3)>>Option[List[Int]=Some(List(1,2,3))
シーケンスの動作はインスタンス内のflatMapの実装に依存するため、Optionの特徴:flatMap None=Noneは次のような効果を生じます.
List(Some(1),None,Some(3)) >>> Option[List[Int]] = None
Par:sequence[A](lm:List[M[A]):M[M[A]>>sequence[A](lm:List[par[A]):List[par[A]]の場合
>>> map2(list(par1),list(par2)){_::_} ,リストにカプセル化された並列演算を実行し、結果をリストに直列にします.
ここだflatMapの機能はpar,run(par)を実行することです.この機能は並列演算Parの核心的な動作である.
sequenceの異なる挙動を解析することから,Monadは確かに汎用的な概括抽象モデルであることが分かった.これは多くのデータ型コンポーネントライブラリのソフトウェアインタフェースです.統一された関数名を使用して、異なるデータ型の異なる機能効果を実現します.
前述したMonoidと同様に,Monadも一定の法則に従って作用を規範化し,関数組合せ(composition)を実現する必要がある.Monadも結合操作(associativity)および恒等(identity)に従う必要がある.Monoidの結合操作は次のとおりです.
op(a,op(b,c))==op(op(a,b),c)はMonadにとってflatMapとmapで結合的な動作を表現することは困難である.しかし,Monadic値M[A](Monadic value)ではなくMonadic関数A=>M[B](Monadic function)に従ってMonad結合操作が容易であることを証明する.A=>[B]はスイスの数学者Heinrich Kleisliの法則の矢印(Kleisli Arrow)である.Kleisli Arrowを用いて関数composeを実現することができます.
def compose[A,B,C](f: A=>[B], g: B=>M[C]): A=>M[C].関数のデザインから見るとcomposeはMonadic関数の組み合わせです.戻り値のタイプA=>M[C]から実装フレームワークa=>????;入力パラメータタイプB=>M[C]からflatMap(M[A])と推定できる(B=>M[C];従って:
注意:composeの実装はflatMapという主導的なMonadインスタンス挙動の関数を通過した.composeがあれば証明できます
compose(f,compose(g,h)) == compose(compose(f,g),h)
flatMapとcomposeは互いに通じ合い,互いに変換できる.私たちはcomposeでflatMapを実現することができます.
例を用いて、それらの相互接続性を証明することができます.
Monadの恒等性については、unitというMonadの恒等値を得ました.
def unit[A](a: A): M[A].unitによってMonadの左右恒等を証明することができます.
compose(f,unit) == f
compose(unit,f) == f
composeはflatMapによって実現されるからです.compose+unitはMonadの最も基本的なコンポーネントにもなります.実際には、join+map+unitの基本コンポーネントのセットもあります.
またflatMapで実現しました.
私たちはjoinでflatMapとcomposeを実現することができます.
関数デザイン(signature)をよく観察すると,導出は難しくない.map A=>M[B]>>M[M[B]]、実はjoinは平坦化関数M[M[A]>>M[A]です.
3つの基本コンポーネントがありますが、私はflatMapに傾いています.flatMapができる限りMonadですから.私にとってMonadic programmingはflatMap programmingで、その中で最も重要な原因はscalaのfor-comprehensionです.for-comprehensionはscalaの特徴であり、Monadの例であればfor-comprehension、flatMapさえあればfor-comprehensionという文法糖を食べることができるとも言える.複雑で実用的なデータ型について説明します.
前にStateタイプを実現しました.また、Stateタイプのmap、flatMapの2つの関数も実現しました.
flatMapが実現した以上、StateはMonadになるでしょう.State Monadの例を作成してみました.
Stateクラス定義は、case class State[S,+A](run:S=>(A,S))
val StateMonad=new Monad[State[????,しまった,Monad[M[]]],Mは1つのクラスパラメータを受け入れる高次タイプですが、State[S,A]は2つのクラスパラメータを受け入れる高次タイプです.どうすればいいですか?State:State[S,]:実際State[S,]異なるSのセットのState[A]であり、言い換えれば、Stateは1つのMonadインスタンスではなく、1つのクラスのMonadインスタンスである.このようなMonadをこのように記述することができます.
以上のState Monad:StateMonad[List[Int].monad
上記の問題はStateタイプとMonad M[]タイプの互換性がないためです.この問題はscalaコンパイラのクラスシステム(type system)に捕まえられ、コンパイルプロセスを終了します.クラスシステムの問題の解決に着手できるのではないでしょうか.クラスシステムをtype lambdaでごまかすことができます.
ほら、Monadクラスパラメータでクラスシステムをからかった後、StateMonad内部はStateの正常な表現に沿っていて、何の変化もありません.type lambdaはscalazで一般的に使用されており,主にデータ型パラメータの不整合問題を解決している.
State Monadが実装されたら、関連例を見てみましょう.
説明:foldLeft(z:B)(f:(B,A)=>B)のzはintStateMonadインスタンスタイプBであるため、foldLeftの操作関数は:(intStateMonad,A)=>intStateMonadであり、for-comprehensionを使用することができる.この操作関数の戻り結果はintStateMonadインスタンスです.したがって、Stateクラスのrun(0)を使用してState変換を演算することができます.Stateの状態開始値は0です.
以上の例では,List[String]をList[(Int,String)]に変換し,List[String]の各文字列をインデックスした.この例ではMonadの意味を理解しました.
1、for-comprehensionが使用可能
2、汎関数式の逐次命令実行プロセスをサポートする.すなわち、高次クラス構造内部で操作プロセスを実行する.flatMapはここで重要な役割を果たし、プロセスループの一環の出力値が別の環境の入力値になることを保証します.
では、Monadは、汎関数プログラミングで汎関数方式のフローコマンド実行をサポートする特別なプログラミングモードであると言えるでしょうか.
trait Monad[M[_]] extends Functor[M] {
def unit[A](a: A): M[A]
def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B]
def map[A,B](ma: M[A])(f: A => B): M[B] = {
flatMap(ma){a => unit(f(a))}
}
def map2[A,B,C](ma: M[A], mb: M[B])(f: (A,B) => C): M[C] = {
flatMap(ma) { a => map(mb){ b => f(a,b) }}
}
def sequence[A](lm: List[M[A]]): M[List[A]] = {
lm.foldRight(unit(Nil: List[A])){(a,b) => map2(a,b){_ :: _} }
}
// sequence
def sequence_r[A](lm: List[M[A]]): M[List[A]] = {
lm match {
case Nil => unit(Nil: List[A])
case h::t => map2(h,sequence_r(t)){_ :: _}
}
}
// sequence( Par)
def bsequence[A](iseq: IndexedSeq[M[A]]): M[IndexedSeq[A]] = {
if (iseq.isEmpty) unit(Vector())
else if (iseq.length == 1) map(iseq.head){Vector(_)}
else {
val (l,r) = iseq.splitAt(iseq.length / 2)
map2(bsequence(l),bsequence(r)) {_ ++ _}
}
}
def traverse[A,B](la: List[A])(f: A => M[B]): M[List[B]] = {
la.foldRight(unit(Nil: List[B])){(a,b) => map2(f(a),b){_ :: _}}
}
def replicateM[A](n: Int, ma: M[A]): M[List[A]] = {
if (n == 0) unit(Nil)
else map2(ma,replicateM(n-1,ma)) {_ :: _}
}
def factor[A,B](ma: M[A], mb: M[B]): M[(A,B)] = {
map2(ma,mb){(a,b) => (a,b)}
}
def cofactor[A,B](e: Either[M[A],M[B]]): M[Either[A,B]] = {
e match {
case Right(b) => map(b){x => Right(x)}
case Left(a) => map(a){x => Left(x)}
}
}
}
それぞれM[A]対応List[A],Option[A]およびPar[A]を用いてsequence関数の役割を解析する.
1.sequence>>>map 2で実現>>>flatMapで実現:
List:sequence[A](lm:List[M[A]):M[List[A]>>sequence[A](lm:List[List[A]):List[List[A]]について
>>> map2(list(list1),list(list2)){_::_} ,リストに封入されたリストを要素分割クロスコンビネーションし、
例:(List(List(1,2),List(3,4)>>>>List[Int]=List(List(1,3),List(1,4),List(2,3),List(2,3),List(2,4))
sequenceの役割はリストに現れる.map 2機能.リストmap 2はListである.flatMapが実現しました.したがって、sequenceの動作は、リストインスタンスにおけるflatMapの実装方法に依存する.
Option:sequence[A](lm:List[M[A]):M[List[A]>>>sequence[A](lm:List[Option[A]):List[Option[A]]について
>>> map2(list(opton1),list(option2)){_::_} ,リストにカプセル化された要素option値をリストにリストし、
例:(List(Some(1),Some(2),Some(3)>>Option[List[Int]=Some(List(1,2,3))
シーケンスの動作はインスタンス内のflatMapの実装に依存するため、Optionの特徴:flatMap None=Noneは次のような効果を生じます.
List(Some(1),None,Some(3)) >>> Option[List[Int]] = None
Par:sequence[A](lm:List[M[A]):M[M[A]>>sequence[A](lm:List[par[A]):List[par[A]]の場合
>>> map2(list(par1),list(par2)){_::_} ,リストにカプセル化された並列演算を実行し、結果をリストに直列にします.
ここだflatMapの機能はpar,run(par)を実行することです.この機能は並列演算Parの核心的な動作である.
sequenceの異なる挙動を解析することから,Monadは確かに汎用的な概括抽象モデルであることが分かった.これは多くのデータ型コンポーネントライブラリのソフトウェアインタフェースです.統一された関数名を使用して、異なるデータ型の異なる機能効果を実現します.
前述したMonoidと同様に,Monadも一定の法則に従って作用を規範化し,関数組合せ(composition)を実現する必要がある.Monadも結合操作(associativity)および恒等(identity)に従う必要がある.Monoidの結合操作は次のとおりです.
op(a,op(b,c))==op(op(a,b),c)はMonadにとってflatMapとmapで結合的な動作を表現することは困難である.しかし,Monadic値M[A](Monadic value)ではなくMonadic関数A=>M[B](Monadic function)に従ってMonad結合操作が容易であることを証明する.A=>[B]はスイスの数学者Heinrich Kleisliの法則の矢印(Kleisli Arrow)である.Kleisli Arrowを用いて関数composeを実現することができます.
def compose[A,B,C](f: A=>[B], g: B=>M[C]): A=>M[C].関数のデザインから見るとcomposeはMonadic関数の組み合わせです.戻り値のタイプA=>M[C]から実装フレームワークa=>????;入力パラメータタイプB=>M[C]からflatMap(M[A])と推定できる(B=>M[C];従って:
def compose[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
a => flatMap(f(a))(g)
}
注意:composeの実装はflatMapという主導的なMonadインスタンス挙動の関数を通過した.composeがあれば証明できます
compose(f,compose(g,h)) == compose(compose(f,g),h)
flatMapとcomposeは互いに通じ合い,互いに変換できる.私たちはcomposeでflatMapを実現することができます.
def flatMapByCompose[A,B](ma: M[A])(f: A => M[B]): M[B] = {
compose((_ : Unit) => ma, f)(())
}
例を用いて、それらの相互接続性を証明することができます.
optionMonad.flatMap(Some(12)){a => Some(a + 10)}//> res12: Option[Int] = Some(22)
optionMonad.compose((_: Unit) => Some(12), { (a : Int) => Some(a + 10)}) (())
//> res13: Option[Int] = Some(22)
Monadの恒等性については、unitというMonadの恒等値を得ました.
def unit[A](a: A): M[A].unitによってMonadの左右恒等を証明することができます.
compose(f,unit) == f
compose(unit,f) == f
composeはflatMapによって実現されるからです.compose+unitはMonadの最も基本的なコンポーネントにもなります.実際には、join+map+unitの基本コンポーネントのセットもあります.
def join[A](mma: M[M[A]]): M[A] = flatMap(mma) {ma => ma}
またflatMapで実現しました.
私たちはjoinでflatMapとcomposeを実現することができます.
def flatMapByJoin[A,B](ma: M[A])(f: A => M[B]): M[B] = {
join(map(ma)(f))
}
def composeByjoin[A,B,C](f: A => M[B], g: B => M[C]): A => M[C] = {
a => join(map(f(a))(g))
}
関数デザイン(signature)をよく観察すると,導出は難しくない.map A=>M[B]>>M[M[B]]、実はjoinは平坦化関数M[M[A]>>M[A]です.
3つの基本コンポーネントがありますが、私はflatMapに傾いています.flatMapができる限りMonadですから.私にとってMonadic programmingはflatMap programmingで、その中で最も重要な原因はscalaのfor-comprehensionです.for-comprehensionはscalaの特徴であり、Monadの例であればfor-comprehension、flatMapさえあればfor-comprehensionという文法糖を食べることができるとも言える.複雑で実用的なデータ型について説明します.
前にStateタイプを実現しました.また、Stateタイプのmap、flatMapの2つの関数も実現しました.
case class State[S, A](run: S => (A, S)) {
def map[B](f: A => B): State[S, B] =
State(s => {
val (a, s1) = run(s)
(f(a), s1)
})
def flatMap[B](f: A => State[S, B]): State[S, B] =
State(s => {
val (a, s1) = run(s)
f(a).run(s1)
}) }
flatMapが実現した以上、StateはMonadになるでしょう.State Monadの例を作成してみました.
Stateクラス定義は、case class State[S,+A](run:S=>(A,S))
val StateMonad=new Monad[State[????,しまった,Monad[M[]]],Mは1つのクラスパラメータを受け入れる高次タイプですが、State[S,A]は2つのクラスパラメータを受け入れる高次タイプです.どうすればいいですか?State:State[S,]:実際State[S,]異なるSのセットのState[A]であり、言い換えれば、Stateは1つのMonadインスタンスではなく、1つのクラスのMonadインスタンスである.このようなMonadをこのように記述することができます.
class StateMonad[S] {
type StateS[A] = State[S,A]
val monad = new Monad[StateS] {
def unit[A](a: A): StateS[A] = State(s => (a,s))
def flatMap[A,B](ma: StateS[A])(f: A => StateS[B]): StateS[B] = flatMap(ma)(f)
}
}
以上のState Monad:StateMonad[List[Int].monad
上記の問題はStateタイプとMonad M[]タイプの互換性がないためです.この問題はscalaコンパイラのクラスシステム(type system)に捕まえられ、コンパイルプロセスを終了します.クラスシステムの問題の解決に着手できるのではないでしょうか.クラスシステムをtype lambdaでごまかすことができます.
def StateMonad[S] = new Monad[({type StateS[A]=State[S,A]})#StateS] {
def unit[A](a: A) = State(s => (a,s))
def flatMap[A,B](sa: State[S,A])(f: A => State[S,B]): State[S,B] = flatMap(sa)(f)
}
ほら、Monadクラスパラメータでクラスシステムをからかった後、StateMonad内部はStateの正常な表現に沿っていて、何の変化もありません.type lambdaはscalazで一般的に使用されており,主にデータ型パラメータの不整合問題を解決している.
State Monadが実装されたら、関連例を見てみましょう.
val intStateMonad = StateMonad[Int] //> intStateMonad : ch6.state.Monad[[A]ch6.state.State[Int,A]] = ch6.state$$an
//| onfun$main$1$$anon$2@7946e1f4
def zipWithIndex[A](as: List[A]): List[(Int,A)] = {
as.foldLeft(intStateMonad.unit(List[(Int, A)]()))((acc,a) => for {
n <- getState
xs <- acc
_ <- setState(n+1)
} yield((n,a) :: xs)).run(0)._1.reverse
} //> zipWithIndex: [A](as: List[A])List[(Int, A)]
val lines=List("the quick","fox is","running","and runnng","...")
//> lines : List[String] = List(the quick, fox is, running, and runnng, ...)
zipWithIndex(lines) //> res3: List[(Int, String)] = List((0,the quick), (1,fox is), (2,running), (3
//| ,and runnng), (4,...))
説明:foldLeft(z:B)(f:(B,A)=>B)のzはintStateMonadインスタンスタイプBであるため、foldLeftの操作関数は:(intStateMonad,A)=>intStateMonadであり、for-comprehensionを使用することができる.この操作関数の戻り結果はintStateMonadインスタンスです.したがって、Stateクラスのrun(0)を使用してState変換を演算することができます.Stateの状態開始値は0です.
以上の例では,List[String]をList[(Int,String)]に変換し,List[String]の各文字列をインデックスした.この例ではMonadの意味を理解しました.
1、for-comprehensionが使用可能
2、汎関数式の逐次命令実行プロセスをサポートする.すなわち、高次クラス構造内部で操作プロセスを実行する.flatMapはここで重要な役割を果たし、プロセスループの一環の出力値が別の環境の入力値になることを保証します.
では、Monadは、汎関数プログラミングで汎関数方式のフローコマンド実行をサポートする特別なプログラミングモードであると言えるでしょうか.