すごいH本の素朴な確率モナド
年末年始の連休から中五日あっての三連休で、正月ボケをぶり返してしまいそうな今日この頃ですが、いかがお過ごしでしょうか。
すごいH本こと、書籍「すごいHaskellたのしく学ぼう!」の最後のほう、第14章「もうちょっとだけモナド」の 14.8 (P356)にて、素朴な確率モナドが紹介されています。
- 作者: Miran Lipovača,田中英行,村主崇行
- 出版社/メーカー: オーム社
- 発売日: 2012/05/23
- メディア: 単行本(ソフトカバー)
- 購入: 25人 クリック: 580回
- この商品を含むブログ (51件) を見る
普通、モナドは作りたいと思って作るものではありません。むしろ、とある問題のある側面をモデル化した型を作り、後からその型が文脈付きの値を表現していてモナドのように振る舞うと分かった場合に、Monad のインスタンスを与える場合が多いです。
というのが印象的で。ふむふむ確かになるほどなあという感じです。
ぼけーっと、ただ連休をだらだらと過ごすだけなのもなんなので、正月ボケのリハビリを兼ねて何か書いておこうかなということで、これを F# で書いてみようと思います。
確率を表現するための有理数を表す型
数学では通常、確率はパーセント(%)ではなく、0 から 1 までの実数で表します。確率が 0 ということは絶対にありえないということであり、確率が 1 というのは確実に起こるということを意味します。確率を浮動小数点で表すのも間違いではないのですが、どうしても精度が落ちてしまう。そこで Haskell では、Rationalという分数を表すために最適な有理数を表す型があり、例えば 4分の1は、1%4 のように、分子と分母は % で区切って表現することができる。では、F# はどうでしょう。標準には用意されていませんが、F# では、F# PowerPack という追加ライブラリにて数学に関する様々な機能が提供されています。これを導入することで分数の表現に対応することができます(NuGetで簡単に導入することもできます)。有理数を表すことができる BigRational という型が定義されているので、それを使えます。BigRational は、Nリテラルを用いて表現することができ、4分の1は、1N/4N というように表せます。
F# で素朴な確率モナド
Haskellでの実装例は書籍や(Learn You a Haskell for Great Good! - For a Few Monads More)に出ている通りなので、そちらを参照されたい。BigRational型と FSharpx を使って、F# で素朴な確率モナドをとりえず実装してみる。
namespace FSharpx.Monad // 素朴な確率モナド module Probability = let probMap f m = List.map (fun (x,p) -> (f x, p)) m type ProbBuilder() = member this.ReturnFrom(x) = x member this.Return(x) = [x,1N/1N] member this.Bind(m, f) = let flatten xs = let concatMap f m = List.concat( List.map (fun x -> f x) m ) let multAll (innerxs,p) = List.map (fun (x,r) -> (x, p*r)) innerxs concatMap multAll xs flatten (probMap f m) member this.Zero () = [] let prob = new ProbBuilder() open FSharpx open Operators let inline returnM x = returnM prob x let inline (>>=) m f = bindM prob m f let inline (=<<) f m = bindM prob m f let inline (<*>) f m = applyM prob prob f m let inline ap m f = f <*> m let inline map f m = liftM prob f m let inline (<!>) f m = map f m let inline lift2 f a b = returnM f <*> a <*> b let inline lift3 f a b c = returnM f <*> a <*> b <*> c let inline ( *>) x y = lift2 (fun _ z -> z) x y let inline ( <*) x y = lift2 (fun z _ -> z) x y let inline (>>.) m f = bindM prob m (fun _ -> f) let inline (>=>) f g = fun x -> f x >>= g let inline (<=<) x = flip (>=>) x
使ってみる。3枚のコイン(イカサマコインが1つ混入している)がすべて裏が出る確率を出す。
module Program = open System open FSharpx.Monad.Probability type Coin = Heads | Tails let coin = [(Heads,1N/2N); (Tails,1N/2N)] let loadedCoin = [(Heads,1N/10N); (Tails,9N/10N)] let flipThree = prob { let! a = coin let! b = coin let! c = loadedCoin return List.forall (function |Tails->true |_->false) [a;b;c] } flipThree |> printfn "%A"
実行結果
[(false, 1/40N); (false, 9/40N); (false, 1/40N); (false, 9/40N); (false, 1/40N); (false, 9/40N); (false, 1/40N); (true, 9/40N)]
確率モナドによって、3枚とも裏が出る確率は、40分の9であると導きだすことができた。すごいH本と同じ結果になりましたね。めでたしめでたし。
続いて、6面のサイコロを2回振ったとき、その出目の合計値ごとの確率を出してみる。
let d sides = [for i in [1 .. sides] -> (i, 1N/ BigRational.FromInt(sides))] let dice = d 6 let diceTwoSum = prob { let! a = dice let! b = dice return a+b } diceTwoSum |> printfn "%A"
実行結果
[(2, 1/36N); (3, 1/36N); (4, 1/36N); (5, 1/36N); (6, 1/36N); (7, 1/36N); (3, 1/36N); (4, 1/36N); (5, 1/36N); (6, 1/36N); (7, 1/36N); (8, 1/36N); (4, 1/36N); (5, 1/36N); (6, 1/36N); (7, 1/36N); (8, 1/36N); (9, 1/36N); (5, 1/36N); (6, 1/36N); (7, 1/36N); (8, 1/36N); (9, 1/36N); (10, 1/36N); (6, 1/36N); (7, 1/36N); (8, 1/36N); (9, 1/36N); (10, 1/36N); (11, 1/36N); (7, 1/36N); (8, 1/36N); (9, 1/36N); (10, 1/36N); (11, 1/36N); (12, 1/36N)]
ここまでがすごいH本で書かれている範囲でできること。これから先については、読者への演習問題としている。
上記の実行結果を見てわかるように、確率の結果がまとまっておらず、バラバラに出力されていて結果の内容がわかりにくい。これはひどい。
できれば、
[(false, 31/40N); (true, 9/40N)]
とか
[(2, 1/36N); (3, 1/18N); (4, 1/12N); (5, 1/9N); (6, 5/36N); (7, 1/6N); (8, 5/36N); (9, 1/9N); (10, 1/12N); (11, 1/18N); (12, 1/36N)]
というように、結果が一致する事象の確率については1つにまとめて出力してくれるのが分かり易くて理想だよね、と。せっかくなので、この演習問題をやってみましょう。
とりあえず、結果が一致する事象の確率を1つにまとめてみる
あまり何も考えずに、とりあえず実装してみた版。
let rec merge (k,p) xs = xs |> function | [] -> [] | (k,p)::kps -> kps |> function | [] -> [(k,p)] | (k',p')::kps' -> if k = k' then (k,p+p')::(merge (k,p) kps') else (k,p)::(merge (k',p') kps) let agglomerate f pd = let xs : ('b * BigRational) list = (probMap f pd) |> List.sort List.foldBack merge pd xs let agg pd = agglomerate id pd
使ってみる。
let flipThree = prob { let! a = coin let! b = coin let! c = loadedCoin return List.forall (function |Tails->true |_->false) [a;b;c] } flipThree |> agg |> printfn "%A" //let flipThree2 = agg <| lift3 (fun a b c -> List.forall (function |Tails->true |_->false) [a;b;c]) coin coin loadedCoin //flipThree2 |> printfn "%A"
実行結果
[(false, 31/40N); (true, 9/40N)]
使ってみる。
let d sides = [for i in [1 .. sides] -> (i, 1N/ BigRational.FromInt(sides))] let dice = d 6 let diceTwoSum = prob { let! a = dice let! b = dice return a+b } diceTwoSum |> agg |> printfn "%A" //let diceTwoSum2 = agg <| lift2 (+) dice dice //diceTwoSum2 |> printfn "%A"
実行結果
[(2, 1/36N); (3, 1/18N); (4, 1/12N); (5, 1/9N); (6, 5/36N); (7, 1/6N); (8, 5/36N); (9, 1/9N); (10, 1/12N); (11, 1/18N); (12, 1/36N)]
うん。とりあえず動いているね。これで一応目的は達成できているのだけど、なんだか冗長な感じがするしカッコ悪い。俺が欲しいのコレジャナイ感がぱない。もっとシンプルに行きたい。
結果が一致する事象の確率を1つにまとめる(改訂版)
どのあたりがコレジャナイ感を出しているのか。落ち着いて先ほどの実装をよく見てみてみよう。
let rec merge (k,p) xs = xs |> function | [] -> [] | (k,p)::kps -> kps |> function | [] -> [(k,p)] | (k',p')::kps' -> if k = k' then (k,p+p')::(merge (k,p) kps') else (k,p)::(merge (k',p') kps) let agglomerate f pd = let xs : ('b * BigRational) list = (probMap f pd) |> List.sort List.foldBack merge pd xs let agg pd = agglomerate id pd
List.sort でソートしたリストと、ソートする前のリストとを比較して、再帰でマージしながら結果をまとめあげる実装となっている。
そもそもここでやりたいことは、集合として確率の結果をまとめ上げたいということ。集合を扱いたい場合、F# では set が使える。また、コレジャナイ実装では、List.foldBack で入力要素を順々に受け取りながら marge 関数で確率の和を求めながら結果の状態を順次更新していっているが、set を使って集合化することができれば、集合の要素ごとの確率の和をそれぞれ算出してゆくだけでよいことになる。あ、それって List.reduce 使えばいんじゃね? となる。
ところで、List.reduce とはなんだったのか。例えば、List.foldを用いてintのリストの和を求める場合を思い出してみよう。
List.fold (+) 0 [1;2;3]
のように書けるのでした。育てる種となる初期値の 0 を与えて、次々にリストを畳み込むことにより、結果 6 が得られる。
ここで、育てる種となる初期値の 0 を与えずにリストの和を求めるには、育てる種の初期値としてリストの最初の要素を採用すればよい。最初の要素と次の要素によって演算を開始するという処理を行えばよいことなる。
こう書く事ができる。
List.reduce (+) [1;2;3]
そう、List.fold が簡易化されたものが List.reduce ということだった。
ということで集合を扱える set と 育てる種を必要としない List.reduce を用いて実装すると次のように書ける。
let merge f (a,x) (b,y) : 'a * BigRational = f a b, x + y let agglomerate f pd = let d = pd |> List.map(fun (x,_) -> x) |> set |> Set.toList List.map (fun x -> List.filter(fun (y,b) -> x = y) pd |> List.reduce (merge f)) d let agg pd = agglomerate (fun _ x -> x) pd
ほむ。だいぶシンプルになりました。これはリハビリをして正解でしたね。
圏論でアハ体験
もう1週間以上前になりますが、Code2012という合宿イベントに参加してきました。いろいろな方との交流あり、温泉あり、クラウディアさんありと大変楽しかったので、ぜひ来年も参加したいです。
で、VBerのくせにそちらで「5分じゃわからないモナド - 圏論なんて華麗にスルー」というタイトルでLTをしてきました。なぜか、宴会の後にLTをやるという謎なタイムスケジュールとなっていたため、十分にアルコールが回った状態でお話をしました。時間通りにジャスト5分で話しきれたのは奇跡です。来年はそのあたり考慮してもらいたいかも...しれません。LTの後にいくつか質問をいただいて、モナドや圏やF#についてなんだか結構な時間追加でしゃべったような気がします。
LTの要点としましては、「モナドを使うのに圏論の知識は必要ない。」という意見はまったくそのとおりなのだけど、だからといって関数型言語を学ぶ人が圏論に触れることを無駄とは言えないということ。「プログラミングでモナドを使えるようになってから関数型言語の数学的背景であるところの圏論に触れてみることは、ぜんぜん無駄ではなかったし、むしろ思っていた以上に収穫があった!」という体験について伝えたい。「モナドは単なる自己関手の圏におけるモノイド対象だよ。」の意味を理解できるのとできないのとでは、見える景色がだいぶ違ってくる。圏論にはアハ体験があります。ある程度根気は必要だけど...ということを伝えたかったというものです。
当日話した内容とまったく同じではありませんが、大体以下のような内容でしゃべってきました。こわい人にこわいこわいされるのがこわいので、当初Webにはアップしないでおこうと考えていたのですが、いろいろと思うところが有り、思い直して現時点の自分の考えを晒しておくことにしました。かなり端折り気味な内容ですが雰囲気だけでも。
5分じゃわからないモナド - 圏論なんて華麗にスルー
5分じゃわからないモナド 始めさせていただきます。
ぜくるです。
静的型付け関数型言語が大好きです。 F#が大好きです。
美しいコードを書きたければ、より多くの良いコードを読まなければなりません。
ならば、関数型言語が読めないのは、あまりにも損です。
じゃいつやるか?今でしょ!
モナド。みなさん聞いたことくらいはありますよね。
モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?
関数型言語を成り立たせている構造がそもそも圏だよ。
プログラミングとは、だいたいクライスリ圏の射を作ることらしいよ。
数学由来の抽象であるところの、代数的な構造をプログラミングに応用したらしいよ。
「モナドは単なる自己関手の圏におけるモノイド対象だよ。何か問題でも?」
の意味がなんでわからんのかというと、そもそも専門用語がわからんからにほかならない。
4年くらい関数型言語を勉強してきた中で、わたしがモナドをわかるまでにやったこと。
まずは具体的にモナドを使ったプログラムを書きまくります。
野性的なプログラマはだいたい体で覚えます。
慣れてくると自分で定義します。より理解が深まります。
自分で考えた新しいモナドを定義することもできるようにもなります。
モナドを使うだけなら、高度な理論は全く必要ないんです。
モナドを使いこなすのに「圏論の知識なんて必要ない」そのとおりだと思います。
でも、最小限把握しておいたほうがよい用語や概念があります。
俺達プログラマは好奇心旺盛だもんね!
少し遠回りをしてもいいんじゃないか。
モナドの数学的な背景すべてを知らなくても、おおまかに概観を把握するだけで見える景色が違ってくる。
圏論に触れてみることにしました。
とりあえず、専門書に当たってみる。今年の正月からコツコツと勉強しています。
でも、この本はジャンル的に少し偏っているし、1,2章でお腹いっぱいです。
で、気づいたのが、そもそも群の知識がないと圏論を理解するのは困難ということです。
集合や群を理解するために、代数を勉強をします。この時点でかなり遠回り。でも、いいんです。
圏論の本にも頻出する集合や群に関する記号の意味を理解するのに役立つ。穴埋めの練習問題形式。
やさしい入門書ですが、基本的なことや記号の意味を把握するだけならこれで十分だと思いました。
でも、マグマとか半群とかモノイドの説明はないので、それらは別の書籍などで補う必要がある。
思いの他おもしろかったので、気持ちに余裕があったら高度な内容にも挑戦してみたいかも。
群と言えばガロア。置換群もプログラミングに関係が深いと感じました。
解説がわかりやすいだけではなく、数学の歴史的な背景も合わせて読めるからお得。
タイトル通り、中1でも読める内容なので安心です。でも後半は結構面倒くさいです。
代数的構造とはなんなのか。具体例を交えてわかりやすく解説してくれます。群の教科書。
こちらおすすめです。寝る前に読んだら、ぐっすり眠れます。
で、群・環・体...と、代数的構造にも色々とありますが、結局プログラミングに関係の深いのは、モノイドという構造です。
どうやら、プログラマ的には、モノイド以外の代数的構造については華麗にスルーしても問題なさそうです。
モナド則ととっても似ていますね。
というかむしろ、モノイドの構造そのものです。
「圏」と同時に最小限知っておかなきゃなんないのが、「関手」です。
圏から圏への写像のことです。
自己関手。同一の圏から圏への関手のこと。
そのまんまですね。
Haskellプログラムは、圏(Hask圏)の中で動いています
F#のコードです。FSharpxというライブラリのMaybeモナドを使ってモナド則をコードで表現してみます。
モナド則を満たすわけですから、これは単位律と結合律を満たします。
モナドを使わずに、ただの関数で同様の表現をしてみます。
恒等射はidですね。
完全に一致!!!
いずれも、圏の条件を満たしており、それぞれが圏だということがわります。
F#の世界の値と関数は、.NETの圏からMaybeモナドの圏への写像であるところの「関手」return によって、 Maybeモナドの圏の値と関数に写像することができる。
で、Maybeの圏はこのとき.NETの圏に含まれていますから、自己関手の圏になるわけですね。で、Maybeという代数的データ型はモノイドの構造を持っているモノイド対象ということですね。
つまり、プログラミングのモナドというのは、関手 return を使うことで、.NETの圏の中で、自己関手の圏であるところのさまざまなモナドの圏を扱えるようになるんですね。
圏論なんて華麗にスルーして、まずモナドを使えるようになったほうがいいです。
F#で順列(Permutation)と組み合わせ(Combination)。YOU、Listモナドしちゃいなよ。集合モナドもあるよ。
以前、C#で順列(Permutation)と組み合わせ(Combination)をすべて列挙してみようという記事を書きました。
今見ると、前に思っていた以上に「しょっぱいなぁ」と思わざるを得ませんが、C#で書き直すつもりになれません。
今回は、超イケてる言語のF#で書きます。
そして、最近わたしがモナドにハマっているということもあり、非決定性計算を得意とするListモナドを利用したいと思います。
非決定性計算に役立つ Listモナド
Listモナドは非決定性を持つ計算について合成する戦略を持つモナドです。
ということなのですが、「非決定性計算」という言葉の意味するところを知らない場合、「お前は何を言っているんだ。」と思わざるを得ません。
一体どういうことを言っているのかというと、要は総当たりする何かの計算と思ってさしつかえないと思います。
つまり、あるリストの全要素について任意の計算を適用しながら、リストを合成して、新しいリストを作り出すための戦略がListモナドということになります。
モナドの性質をうまく利用していて、ループが複数ネストしてしまうような総当たり計算であっても、
あたかもフラットであるかのような宣言的な記述方法で、曖昧性を解決する計算を構築しやすくしてくれる。
C#、VBプログラマであれば、LINQによる総当たり処理を思い浮かべてみるとイメージしやすいでしょう。
この件については、のいえさん(@neuecc)が、Linqと総当り - neue ccという記事を書いています。ぜひ参考にしてください。
Listモナドは大変便利なので、F#にもぜひ欲しい。
でもちょっと待って。そもそもF#にはシーケンス式があるよ
でも、ちょっと待ってください。
F#には、もともと シーケンス式 というナイスな構文が用意されているじゃないか。
なので「F#にListモナドなんて別にいらないんじゃね?」と思われるかもしれません。確かにそうかもしれません。
が、書き易さや可読性、メンテナンス性の観点から、私はコンピューテーション式でListモナドを用意しておきたい派です。
シーケンス式でFizzBuzzを書くとこう。
let fizzbuzz = [for x in [1..100] -> let f,b = "Fizz", "Buzz" match x % 3, x % 5 with | 0,0 -> f + b | 0,_ -> f | _,0 -> b | _ -> string x] List.iter (fun x -> printfn "%A" x) fizzbuzz
これは、ループがひとつなので特に気になりません。
では、覆面算 SEND MORE MONEYを書いてみましょう。
let solve () = let digits = Set.ofList [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs [for s in digits - Set.singleton 0 do for e in digits - Set.singleton s do for n in digits - Set.ofList [s;e] do for d in digits - Set.ofList [s;e;n] do for m in digits - Set.ofList [s;e;n;d;0] do for o in digits - Set.ofList [s;e;n;d;m] do for r in digits - Set.ofList [s;e;n;d;m;o] do for y in digits - Set.ofList [s;e;n;d;m;o;r] do let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then yield! [send; more; money]]
これはひどい。ネストが深くなってしまいました。
でも、実はインデントを下げる必要はなくて、
let solve () = let digits = Set.ofList [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs [for s in digits - Set.singleton 0 do for e in digits - Set.singleton s do for n in digits - Set.ofList [s;e] do for d in digits - Set.ofList [s;e;n] do for m in digits - Set.ofList [s;e;n;d;0] do for o in digits - Set.ofList [s;e;n;d;m] do for r in digits - Set.ofList [s;e;n;d;m;o] do for y in digits - Set.ofList [s;e;n;d;m;o;r] do let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then yield! [send; more; money]]
と、上記のようにフラットに書くこともできます。とはいえ、決して書き易いとは言えませんし、
可読性やメンテナンス性の観点から言って欠点が多く、ある程度複雑なリストを表現するような場合は適さないと考えます。
シンプルなリストを構築する場合にシーケンス式はとても有用ですが、その他の場合ではちょっと扱いにくいでしょう。
F#で Listモナド
そこで、コンピューテーション式でListモナドを用意しておきます。まず、Haskell での定義を。
Listモナドは型クラスMonadとMonadPlusのインスタンスとかなんとか。
instance Monad [] where m >>= k = concat (map k m) return x = [x] fail s = [] instance MonadPlus [] where mzero = [] mplus = (++)
F#のコンピューテーション式で書いてみます。
type ListBuilder() = let concatMap f m = List.concat( List.map (fun x -> f x) m ) member this.Bind (m, f) = concatMap (fun x -> f x) m member this.Return (x) = [x] member this.ReturnFrom (x) = x member this.Zero () = [] member this.Combine (a,b) = a@b let list = ListBuilder()
とりあえずまぁこんなところでしょう。
より多くの機能が欲しければ、各メソッドを実装していけばよいかと。
ListモナドのBindがなぜ複数のネストしたループを表現することができるのかは、実装を見れば明らかですが、
よくわからないという場合は、「リストモナドの動作原理を考える」を参照するとよいかもしれません。
ということで、覆面算SEND MORE MONEYを、コンピューテーション式によるListモナドで。
let solve' () = let digits = [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs let inline (-) a b = a |> List.filter (fun x -> List.forall (fun y -> x <> y) b) list { let! s = digits - [0] let! e = digits - [s] let! n = digits - [s;e] let! d = digits - [s;e;n] let! m = digits - [s;e;n;d] - [0] let! o = digits - [s;e;n;d;m] let! r = digits - [s;e;n;d;m;o] let! y = digits - [s;e;n;d;m;o;r] let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then return! [send; more; money]}
とても書き易く可読性もよいですね。コンピューテーション式によるモナドなので、
モジュール性が確保されていて、シーケンス式のfor - doよりもメンテナンス性が高いです。
別途コンピューテーション式でListモナドを用意しておくことは意味のあることです。
Listモナドで順列(Permutation)と組み合わせ(Combination)
ということで、タイトルにあったように、Listモナドで順列(Permutation)と組み合わせ(Combination)を実装してみた。
F# Snippentsに投稿しました。
http://fssnip.net/6C
open System type ListBuilder() = let concatMap f m = List.concat( List.map (fun x -> f x) m ) member this.Bind (m, f) = concatMap (fun x -> f x) m member this.Return (x) = [x] member this.ReturnFrom (x) = x member this.Zero () = [] member this.Combine (a,b) = a@b member this.Delay f = f () let list = ListBuilder() let rec permutations n lst = let rec selections = function | [] -> [] | x::xs -> (x,xs) :: list { let! y,ys = selections xs return y,x::ys } (n, lst) |> function | 0, _ -> [[]] | _, [] -> [] | _, x::[] -> [[x]] | n, xs -> list { let! y,ys = selections xs let! zs = permutations (n-1) ys return y::zs } let rec combinations n lst = let rec findChoices = function | [] -> [] | x::xs -> (x,xs) :: list { let! y,ys = findChoices xs return y,ys } list { if n = 0 then return! [[]] else let! z,r = findChoices lst let! zs = combinations (n-1) r return z::zs } let x4P0 = permutations 0 [1;2;3;4] printfn "4P0 = %d" x4P0.Length x4P0 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4P2 = permutations 2 [1;2;3;4] printfn "4P2 = %d" x4P2.Length x4P2 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4C0 = combinations 0 [1;2;3;4] printfn "4C0 = %d" x4C0.Length x4C0 |> Seq.iter (fun x -> printfn "%A" x) Console.WriteLine ("-----") |> ignore let x4C2 = combinations 2 [1;2;3;4] printfn "4C2 = %d" x4C2.Length x4C2 |> Seq.iter (fun x -> printfn "%A" x) Console.ReadLine () |> ignore
コード短すぎワロスwww さすが俺たちのF#さん!!
笑わない数学者「5つのビリヤード玉問題」
笑わない数学者からの挑戦状
http://r27.jp/quiz/mathematical-goodbye/
さっそく利用してみる。笑わない数学者「5つのビリヤード玉問題」を解いてみましょう。
// 5つのビリヤード玉問題 let billiardsProblem = let judge (xs:int list) = let a,b,c,d,e = (xs.[0],xs.[1],xs.[2],xs.[3],xs.[4]) [a;b;c;d;e]@ [a+b;b+c;c+d;d+e;e+a]@ [a+b+c;b+c+d;c+d+e;d+e+a;e+a+b]@ [a+b+c+d;b+c+d+e;c+d+e+a;d+e+a+b;e+a+b+c]@ [a+b+c+d+e] |> List.sort list { let! xs = permutations 5 [1..11] if [1..21] = judge xs then return xs} billiardsProblem |> printfn "%A"
実行結果
[[1; 3; 10; 2; 5]; [1; 5; 2; 10; 3]; [2; 5; 1; 3; 10]; [2; 10; 3; 1; 5]; [3; 1; 5; 2; 10]; [3; 10; 2; 5; 1]; [5; 1; 3; 10; 2]; [5; 2; 10; 3; 1]; [10; 2; 5; 1; 3]; [10; 3; 1; 5; 2]]
おまけ:集合モナド
Collections.Set<'T> クラス (F#)
http://msdn.microsoft.com/ja-jp/library/ee353619.aspx
Collections.Set Module (F#)
http://msdn.microsoft.com/ja-jp/library/ee340244.aspx
はい。あいかわらず機械翻訳が残念なことになっていますが、
上記のとおりF#では集合を扱うクラスとモジュールが用意されています。
Listだけじゃなく、集合もモナドになってたらいんじゃね?という単純すぎる発想です。
とはいえ、基本的にListで代用できてしまうので、ありがたみは少ししかないかもしれませんが…。
集合モナド
type SetBuilder() = let unionManyMap f m = Set.unionMany ( Set.map (fun x -> f x) m ) member this.Bind (m, f) = unionManyMap (fun x -> f x) m member this.Return (x) = Set.ofList x member this.ReturnFrom (x) = x member this.Zero () = Set.empty member this.Combine (a,b) = Set.union a b let set = SetBuilder ()
Listモナドを集合用に単純に書き換えただけですね。
Listモナドで言うところのconcatMapがunionManyMapとなっています。
積集合や対称差のための関数や演算子を用意するなどして、モジュールを充実させるとより扱いやすくなるかも。
集合モナドと他の方法とで、非決定性計算の速度を比較してみる。
let getProcessingTime f = let s = new System.Diagnostics.Stopwatch () s.Start() let r = f () s.Stop () r,s.Elapsed Console.WriteLine ("----- send + more = money -- for Set") let solve () = let digits = Set.ofList [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs [for s in digits - Set.singleton 0 do for e in digits - Set.singleton s do for n in digits - Set.ofList [s;e] do for d in digits - Set.ofList [s;e;n] do for m in digits - Set.ofList [s;e;n;d;0] do for o in digits - Set.ofList [s;e;n;d;m] do for r in digits - Set.ofList [s;e;n;d;m;o] do for y in digits - Set.ofList [s;e;n;d;m;o;r] do let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then yield! [send; more; money]] printfn "%A" <| getProcessingTime solve Console.WriteLine ("----- send + more = money -- Listモナド") let solve' () = let digits = [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs let inline (-) a b = a |> List.filter (fun x -> List.forall (fun y -> x <> y) b) list { let! s = digits - [0] let! e = digits - [s] let! n = digits - [s;e] let! d = digits - [s;e;n] let! m = digits - [s;e;n;d] - [0] let! o = digits - [s;e;n;d;m] let! r = digits - [s;e;n;d;m;o] let! y = digits - [s;e;n;d;m;o;r] let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then return! [send; more; money]} printfn "%A" <| getProcessingTime solve' Console.WriteLine ("----- send + more = money -- Setモナド") let solve'' () = let digits = Set.ofList [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs set { let! s = digits - Set.singleton 0 let! e = digits - Set.singleton s let! n = digits - Set.ofList [s;e] let! d = digits - Set.ofList [s;e;n;] let! m = digits - Set.ofList [s;e;n;d;0] let! o = digits - Set.ofList [s;e;n;d;m] let! r = digits - Set.ofList [s;e;n;d;m;o] let! y = digits - Set.ofList [s;e;n;d;m;o;r] let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then return [send; more; money]} printfn "%A" <| getProcessingTime solve'' Console.WriteLine ("----- send + more = money -- Seq") let solve''' () = let digits = Set.ofList [0..9] let inline toInt xs = List.fold (fun x y -> x * 10 + y) (0) xs seq {for s in digits - Set.singleton 0 do for e in digits - Set.singleton s do for n in digits - Set.ofList [s;e] do for d in digits - Set.ofList [s;e;n] do for m in digits - Set.ofList [s;e;n;d;0] do for o in digits - Set.ofList [s;e;n;d;m] do for r in digits - Set.ofList [s;e;n;d;m;o] do for y in digits - Set.ofList [s;e;n;d;m;o;r] do let send = toInt[s;e;n;d] let more = toInt[m;o;r;e] let money = toInt[m;o;n;e;y] if send + more = money then yield! [send; more; money] } printfn "%A" <| getProcessingTime solve''' Console.ReadLine () |> ignore
実行結果(マシンスペック等はお察しください)
----- send + more = money -- for Set ([9567; 1085; 10652], 00:00:04.2887953) ----- send + more = money -- Listモナド ([9567; 1085; 10652], 00:00:02.1857583) ----- send + more = money -- Setモナド (set [1085; 9567; 10652], 00:00:05.1224592) ----- send + more = money -- Seq (seq [9567; 1085; 10652], 00:00:00.0014052)
「集合モナド遅せーじゃん。」って、なってしまうわけですが、それは問題の性質や領域によって変わってくるお話。
この覆面算については扱う集合があまりにも単純すぎて、リストで扱った方が高速になるが、
より複雑な集合問題を扱う場合は、集合モナドを利用した方がよりシンプルに書くことができて、高速に処理できます。たぶん。
まぁ、多くの場合はListモナドで事足りてしまうような気がするので、集合モナドの活躍の場はあんまりないかも(えっ。
そして一見、「seq が圧倒的パフォーマンスを見せつけているぞ!」と思うかもしれませんが、それはぜんぜん違うくて、
単に遅延評価が働いているだけです。今回の時間の計測方法では早いように見えるだけです。seq は IEnumerable
ということで、Listモナドで順列(Permutation)と組み合わせ(Combination)を実装しなおしてみたら、
C#と比較にならないくらい短く書けましたよ!というご報告でした。俺達のF#がふつくしすぎる。
FizzBuzz問題から学ぶモナド
前回のエントリでモナドについて熱く語りました。今回はゆるいモナドの雑記です。
モナドを利用してFizzBuzz問題を書いてみることで、「モナドってなんなん?なにしてくれちゃってるん?」ということが、
もしかしたら分かるかもしれないよ、という息抜き的なお話です。
FizzBuzz問題から学ぶモナド
FizzBuzzをモナドで - トウフ日記
http://d.hatena.ne.jp/nskj77/20070512/1178952068
よりコードを引用します。
data FB a = FB (a, String) instance Monad FB where return x = FB (x, "") m >>= f = bind m f where bind (FB (x, y)) f = let FB (m, n) = f x in FB (m, y ++ n) instance (Show a) => Show (FB a) where show (FB (x, "")) = show x show (FB (_, y)) = y fizzbuzz = mapM_ (\x -> print (fizz x >>= buzz)) where fizz x | x `mod` 3 == 0 = FB (x, "Fizz") | otherwise = return x buzz x | x `mod` 5 == 0 = FB (x, "Buzz") | otherwise = return x
はい。FizzBuzz問題をモナドで実装してみようというHaskellのコードです。
これは非常に面白いですね。さっそくF#へ移植してみましょう。
type FB<'T> = FB of 'T * string let inline (>>=) (FB (x, y)) f = f x |> function | FB(m,n) -> FB(m, y + n) let bindFB m f = m >>= f let fbreturn x = FB x type FizzBuzzBuilder () = member this.Return (x) = fbreturn x member this.Bind (m,f) = m >>= f let fb = FizzBuzzBuilder () let fizz = function | x when x % 3 = 0 -> fb { return x,"Fizz" } | x -> fb { return x,"" } let buzz = function | x when x % 5 = 0 -> fb { return x,"Buzz" } | x -> fb { return x,"" } let printFB = function | FB(x,"") -> printfn "%A" x | FB(_,y) -> printfn "%s" y let fizzbuzz = Seq.iter (fun x -> (fizz x >>= buzz) |> printFB) [1..100] |> fizzbuzz |> ignore System.Console.ReadLine () |> ignore
とくになんの捻りもなく、ベタに移植。とりあえずFizzBuzzできました。
Bind(>>=)で、とある型'Tとstringなタプルを伝番させて、出力内容を構築する仕組みになっていますね。
で、気付いたんですが、これはモナド則を満たしていませんね。
当然、元ネタのHaskellのコードについても同じことが言えます。
元ネタは、確かに型クラスとしてのMonadを利用してFizzBuzzを実装してはいますが、
MonadのインスタンスであるFBがモナド則を満たしていないので、厳密にはモナドによるFizzBuzzの実装にはなっていないんですね。
具体的には、モナド則1について満たされていないので、残念な感じなっています。
モナド則1
return x >>= f == f x
ベタ移植できていませんでした。正しくはこうです。
type FB<'T> = FB of 'T * string let inline (>>=) (FB (x, y)) f = f x |> function | FB(m,n) -> FB(m, y + n) let bindFB m f = m >>= f let fbreturn (x:int) = FB (x,"") type FizzBuzzBuilder () = member this.Return (x) = fbreturn x member this.Bind (m,f) = m >>= f let fb = FizzBuzzBuilder () let fizz = function | x when x % 3 = 0 -> FB (x,"Fizz") | x -> fb { return x } let buzz = function | x when x % 5 = 0 -> FB (x,"Buzz") | x -> fb { return x } let printFB = function | FB(x,"") -> printfn "%d" x | FB(_,y) -> printfn "%s" y let fizzbuzz = Seq.iter (fun x -> fizz x >>= buzz |> printFB) [1..100] |> fizzbuzz |> ignore System.Console.ReadLine () |> ignore
そして、元ネタのHaskellのコード同様に、これはモナド則を満たします。
では、モナド則1を満たすように書き直してみます。
モナド則を満たしつつ、単に関数適用するようなかたちに書き換えてみます。
type FB<'T> = FB of 'T * string let inline (>>=) (FB (x, y)) f : FB<'b> = f (x,y) let fbreturn x = FB x type FizzBuzzBuilder () = member this.Return (x) = fbreturn x member this.Bind (m,f) = m >>= f let fb = FizzBuzzBuilder () let fizz = function | x when x % 3 = 0 -> fb { return x,"Fizz" } | x -> fb { return x,"" } let buzz = function | x,s when x % 5 = 0 -> fb { return x, s + "Buzz" } | x,s -> fb { return x,s } let printFB = function | FB(x,"") -> printfn "%A" x | FB(_,y) -> printfn "%s" y let fizzbuzz = Seq.iter (fun x -> (fizz x >>= buzz) |> printFB) [1..100] |> fizzbuzz System.Console.ReadLine () |> ignore
モナドでFizzBuzzを書くならこう書くのが自然ですね。
この例では、fizz関数で生成されたFBモナドにbuzz関数をBind(>>=)で適用することで、モナドが合成されていることがわかります。
どこが変わったのかと言えば、コンピューテーション式のBindの実装です。
修正前の実装では、Bind(>>=)で f を x に適用したあとに、ごにょごにょ(文字列を結合する操作を)していました。
これにより、モナド則1(左単位元)が満たされなくなっていたということです。
前回のエントリでも書きましたが、モナドは「ジェネリックな関数適用」と見なすことができました。
逆に言うと、Bind(>>=)で関数適用以上のことをしてしまうと、モナドとしての整合性がとれなくなってしまうということです。
このことから、Bind(>>=)時に関数適用の操作の範囲を超えてしまうような余計な操作はしてはいけないことがわかります。
「関数適用の操作の範囲を超えるような処理は、Bind(>>=)対象となるモナド側で構築する」のが作法ということになります。
この例では、fizz関数とbuzz関数内でやっていることがそれにあたります。
世界のナベアツ問題もモナドで
FizzBuzz問題に類似する世界のナベアツ問題(もはや死語)についても、
同じ戦略を利用することができるので、同様に関数適用の操作をするだけのFizzBuzzモナドを使って書いてみましょう。
let aho = function | x when x % 3 = 0 || (string x).Contains("3") -> fb { return x, string x + "あほ" } | x -> fb { return x, string x + "" } let ahan = function | x,s when x % 8 = 0 -> fb { return x, s + "あはん" } | x,s -> fb { return x,s } let printNabeatsu = function | M(x,"") -> printfn "%A" x | M(_,y) -> printfn "%s" y let nabeatsu = Seq.iter (fun x -> (aho x >>= ahan) |> printNabeatsu) [1..40] |> nabeatsu System.Console.ReadLine () |> ignore
FizzBuzzモナドがやっていること自体が、単なる関数適用にすぎないため、そのまま流用することができました。
「がぶさんのかんがえたさいきょうのBLげんご、F#」をモナドで
ぼくのかんがえたさいきょうのBLげんご、F# - Gab_kmのブログ
http://blog.livedoor.jp/gab_km/archives/1355595.html
サンプルとしてもう一つ、こちらも実装してみましょう。
ガブさん曰く、
今回できなかったこととして、他の人に「なんてものを見てしまったんだろうな感」を与えないようにしたいところ。
このキャッキャウフフを何かにくるんで、(精神的に)安全に扱う仕掛けが必要だ。
そう、それはまさにモナドの得意とするところ。
BLモナドの実装が次なるチャレンジになるだろう。
ということで、BLに特化したBLモナドの実装?と行きたくなるのかもしれませんが、
この場合も、戦略としてFizzBuzzモナドが利用できます。FizzBuzzモナドで実装してみましょう。
type SemeUke = Seme | Uke let createBoy name seme uke a = let say s nm line = let s = if s <> "" then s + "\n" else s s + nm + "「" + line + "」" a |> function | (Seme,s)-> fb { return Uke, say s name seme } | (Uke,s) -> fb { return Seme, say s name uke } let gab = createBoy <| "ガブ" <| "んー。やっぱりもっとクールに。ほら、こうできる。ねっ?(手を握りながら" <| "んっ。。。こうですか?/// もっと教えてほしいです。。。///" let kyon = createBoy <| "きょん" <| "このうさみみに触れたければ、軽やかにスレーブを使いこなして。ほら、もっと素直になって?" <| "っっっ/// うさみみがぴょんぴょんしちゃうよ///" let printBL = function | M(x,"") -> printfn "%A" "「・・・。」" | M(_,y) -> printfn "%s" y printfn "%s" "きょん×ガブ" (Seme,"") |> kyon >>= gab |> printBL printfn "%s" "\nガブ×きょん" (Seme,"") |> gab >>= kyon |> printBL System.Console.ReadLine () |> ignore
難なくモナドで実装することができました。FuzzBuzzモナドがとても抽象的な操作をしていることがわかります。
モナドは非常に柔軟で拡張性も高いので、もう一人BL対象を増やすことも容易です。
type SemeUke = Seme | Uke | Another let createBoy name seme uke another a = let say s nm line = let s = if s <> "" then s + "\n" else s s + nm + "「" + line + "」" a |> function | (Seme,s)-> fb { return Uke, say s name seme } | (Uke,s) -> fb { return Another, say s name uke } | (Another,s) -> fb { return Seme, say s name another } let gab = createBoy <| "ガブ" <| "んー。やっぱりもっとクールに。ほら、こうできる。ねっ?(手を握りながら" <| "んっ。。。こうですか?/// もっと教えてほしいです。。。///" <| "きゃっきゃ" let kyon = createBoy <| "きょん" <| "このうさみみに触れたければ、軽やかにスレーブを使いこなして。ほら、もっと素直になって?" <| "っっっ/// うさみみがぴょんぴょんしちゃうよ///" <| "ウフフ" let kusomiso = createBoy <| "くそみそ" <| "ウホッ!いい男。やらないか" <| "ん゛ん゛ん゛ん゛ん" <| "マッスル!マッスル!" let printBL = function | M(x,"") -> printfn "%A" "「・・・。」" | M(_,y) -> printfn "%s" y printfn "%s" "きょん×ガブ" (Seme,"") |> kyon >>= gab |> printBL printfn "%s" "\nガブ×きょん" (Seme,"") |> gab >>= kyon |> printBL printfn "%s" "\nガブ×きょん×くそみそ" (Seme,"") |> gab >>= kyon >>= kusomiso |> printBL printfn "%s" "\nくそみそ×きょん×ガブ" (Seme,"") |> kusomiso >>= kyon >>= gab |> printBL System.Console.ReadLine () |> ignore
で、何度もしつこく言っていますが、このFizzBuzzモナドでは単に関数適用をしているにすぎません。
このBL的な何かの処理を、モナドで実装すること自体に意味はありません。あくまでFizzBuzzモナドがやっていることに着目してください。
で、FizzBuzzモナドって結局何なの
ということを踏まえたところで、FizzBuzzモナドに注目してもっと抽象的に考えていきましょう。
判別供用体の FB<'T> ですが、 'Tはそもそもジェネリックな型なので、FB of 'T * stringである必要はないですね。
表現としては、 FB of 'T で十分に表現できます。
以下のように書き直せます。
type FB<'T> = FB of 'T let inline (>>=) (FB (x, y)) f : FB<'b> = f (x,y) let fbreturn x = FB x type FizzBuzzBuilder () = member this.Return (x) = fbreturn x member this.Bind (m,f) = m >>= f
また、同様の理由でBind(>>=)についても同じことが言えるので、
FBの'T型について、タプルであることを明示する必要はありません。
以下のように書き直せます。
type FB<'T> = FB of 'T let inline (>>=) (FB x) f : FB<'b> = f x let fbreturn x = FB x type FizzBuzzBuilder () = member this.Return (x) = fbreturn x member this.Bind (m,f) = m >>= f
これって、そもそもFBって名前である意味がないよね。
以下のように書き直せます。
type M<'T> = M of 'T let inline (>>=) (M x) f : M<'U> = f x let mreturn x : M<'T> = M x type MonadBuilder () = member this.Return (x) = mreturn x member this.Bind (m,f) = m >>= f
おやおや。なにかとても見覚えのある形になりましたね。
もうお気付きですね。「これって、モナドの基本形そのままやん!*1」 はいそのとおりです。
先ほどまでFizzBuzzモナドと呼んでいたものの正体は、実はモナドの基本形そのものだったんだよ!
当然のことながら、そのままFizzBuzz(世界のナベアツ、BL的な何か)が動きます。
type M<'T> = M of 'T let inline (>>=) (M x) f : M<'U> = f x let mreturn x : M<'T> = M x type MonadBuilder () = member this.Return (x) = mreturn x member this.Bind (m,f) = m >>= f let m = MonadBuilder () let fizz = function | x when x % 3 = 0 -> m { return x,"Fizz" } | x -> m { return x,"" } let buzz = function | x,s when x % 5 = 0 -> m { return x, s + "Buzz" } | x,s -> m { return x,s } let printFB = function | M(x,"") -> printfn "%A" x | M(_,y) -> printfn "%s" y let fizzbuzz = Seq.iter (fun x -> (fizz x >>= buzz) |> printFB) [1..100] |> fizzbuzz System.Console.ReadLine () |> ignore
ということで、FizzBuzz問題をモナドで書いてみることで、
「モナドが何をやっているのか」、あるいは「モナドはジェネリックな関数適用だよね」
ということを、さも説明してしまったかのような雰囲気をかもし出してみました。何かの参考になれば幸いです。
快刀乱麻を断つモナド - F#とIOモナドとコンピューテーション式の奥義と
,. -‐'''''""¨¨¨ヽ (.___,,,... -ァァフ| あ…ありのまま 今 起こった事を話すぜ! |i i| }! }} //| |l、{ j} /,,ィ//| 『F#でIOモナドっぽい何かを作ろうとしていたら、 i|:!ヾ、_ノ/ u {:}//ヘ いつのまにか、全然別モノのLazyモナドをつくっていた。』 |リ u' } ,ノ _,!V,ハ | /´fト、_{ル{,ィ'eラ , タ人 な… 何を言ってるのか わからねーと思うが /' ヾ|宀| {´,)⌒`/ |<ヽトiゝ おれも 何をされたのか わからなかった… ,゙ / )ヽ iLレ u' | | ヾlトハ〉 |/_/ ハ !ニ⊇ '/:} V:::::ヽ 頭がどうにかなりそうだった… // 二二二7'T'' /u' __ /:::::::/`ヽ /'´r -―一ァ‐゙T´ '"´ /::::/-‐ \ 素の「Lazy<'T>」の入れ子だとか 「unit -> 'T」の連鎖だとか / // 广¨´ /' /:::::/´ ̄`ヽ ⌒ヽ そんなチャチな遅延合成じゃあ 断じてねえ ノ ' / ノ:::::`ー-、___/:::::// ヽ } _/`丶 /:::::::::::::::::::::::::: ̄`ー-{:::... イ もっと恐ろしい言語指向プログラミングの 片鱗を味わったぜ…
に至るまでの前置き(能書き)が無駄に長いです。
F#でIOモナドの話についてのみ書くつもりが、モナド全般の話になってしまいました。
それにしてもこれは一体誰向けの記事なのか、書いた本人もよくわからないんだぜ…(ごくり)。
プログラミングの世界のモナドとは、計算を組み合わせてより複雑な計算を構築するための、戦略の抽象のことを言います。モナドと言えばHaskellが有名ですが、モナドという抽象概念は言語依存のものではありません。
「モナドは関数プログラミングにおける戦略の抽象である。」と言いました。戦略には計算に応じてさまざまな種類があり、それぞれに名前、問題、適用可能性、特徴、結果などがあります。たとえば、Maybeモナドという名前の戦略がある。これは「失敗する可能性のある計算の合成」という問題に対する解決策を持っている。複数の失敗するかもしれない計算を合成し、ひとまとめの失敗するかもしれない計算として扱いたいような場合に適用することができる。「失敗したらその後の処理はしない」という特徴を持っている。結果として、入れ子が深くなりがちな失敗可能性のある計算の連鎖について、複雑な計算をよりシンプルに表現することができる。感のよい人はもう気づいているかもしれないが、「これって、もしかしてデザインパターン?」そう、「○○モナド」をそれぞれの問題領域を解決するためのパターンとして捉えることができます。そしてそのパターン全体に係る「モナド」は、それぞれの○○モナドに対して同じ枠組みを提供している“より高い抽象”と言うことができます。モナドは同じ枠組み(同じ概念)の下で、実にさまざまな問題領域に対して解決策を提示してくれます。つまり、関数プログラミンにおける「メタデザインパターン」あるいは「メタ戦略」、「メタ理論」がモナドであると捉えることもできます。この高次な概念は、もともと数学の一分野である圏論から来ています。なぜ圏論のモナドなんていうプログラミングと何の関連もない数学的構造が、プログラミングのあらゆる問題の解決策を示していたり、多くのプログラミングパターンを説明することができるのかはわかりません。そこには深イイ理由があるのかもしれないし、ただの偶然なのかもしれない。ただこれだけは言える。「数学SUGEEEEEEEEEEE」と。
Haskellの「Monad」は、モナドの抽象概念を適用した単なる型クラスのひとつです。モナドはメタ戦略なので、他の言語でもモナドを表現することはできます。しかし、型クラスと同程度の表現力を持っていない限り、Haskellほど美しくモナドとその周辺事情を表現することはできません。HaskellのMonadは型クラスによって非常に洗練された表現をされているので、モナドを勉強する上でとても参考になります。なにかを学ぶ場合、抽象的な話だけではわかりにくいので、具体的な例で考えてみると理解の助けとなります。Haskellの知識が少し必要ですが、id:kazu-yamamotoさんの「QAで学ぶMonad - あどけない話」の説明がすばらしくわかりやすいです。
「モナドは難しい」、「モナドは象だ」、「モナドかわいいよモナド」、「このモナドの説明を書いた人はこんなモナドの説明を読んでいます」、「モナドはメタファーではない」、「モナにゃんぺろぺろ」、「圏論モナドこそ至高」など、実にさまざまな声を聞きます。Real World Haskell(オライリー)には、「モナドを使っていると苛々します」という皮肉めいた記述が現れたりもします。
憧れの(闇の)カンスウガタゲンガー達が語る「モナドの本当の意味」を理解しようとすると、やはり圏論の概念やら定理やらの正確な理解が必要なのかもしれず。でも、その域に達するには、おそらく私を含めた一般的なプログラマには険しくも困難な道。出口の見えない試練に身を投じることになります。
しかし、多くのカンスウガタゲンガーは、圏論の本質的な意味やその定理に強いわけではなく。それにもかかわらず、彼らはモナドを使ったプログラムを書きます。小難しい概念を正確に理解することはできなくても、モナドを利用してメリットを享受することはできるんです。そしてモナドはとても便利なんです。実際のところ「モナド則*1」さえわかっていればほとんどの場合は困りません。使っているうちにモナドの性質が徐々にわかってきて、いずれ立派なモナグラマ−になれるかもしれない。もしかすると、みんなに愛でられるような可愛いオレオレモナドを発明できるようになるかもしれない。
C++をモナドに置き換えて音読してみましょう。そんな感じです。
単に関数プログラミングにおけるモナドの実用性あるいは利便性という意味だけで言うと、モナド則(モナドが守るべき3つのルール)を満たす基本演算の定義をすれば、あらゆる操作を同じ枠組みのもとでジェネリックに連鎖できる仕組みを利用することができる、ということに他ならない。モナドがプログラミング上で表現している抽象は、ジェネリックな関数合成と言いかえることもできる。関数合成とモナドの合成の違いを考えると、モナドはジェネリックな合成であり、異なる型の値を持つことができる点で異なる。これはそれぞれのシグネチャを比較するとわかりやすい。
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(>>=)ではm aやm bと表されているように、合成時に異なる型の値が関わることがわかる。
Bind演算子(>>=)は、ある関数で値になんらかの処理をして、その値を次の関数に値を受け渡たしていく。ここでのある関数というのは、もちろん(a -> m b)のことであり、a は前の関数が返したモナドから値を取り出したものである。どのようにモナドから値を取り出して次の関数の引数にするのかを決定するのがBind演算子(>>=)というわけ。より関数型っぽく言いかえると、どのように(a -> m b)をm aに適用するのかを決めるための定義がBind演算子(>>=)。
では最初の、先頭にあたるモナドは一体どこからやってくるのか?ということになる。そこで、モナドが定義しなければならないもうひとつの定義、returnが導出される。returnは、なんらかの値を新たなモナド型の値にする関数で、しばしばモナドに包むなんて表現されたりもする。
return :: Monad m => a -> m a
シグネチャも御覧の通りで、何も難しいことはしていません。Haskellでは、return や Bind演算子(>>=)はただの関数ではなくて、Monadクラス(型クラス)のメソッドになっていて、これによってアドホック多相が使える。なので、モナドがどのように合成されるのかという実装の詳細を意識しなくてもよいようになっている。つまり、文法上は同じように(>>=)でモナドが合成されていたとしても、そのモナドの種類によって実際の合成の挙動は異なる。つまるところこれはオーバーロード (多重定義)のことを言っていて、F#ではコンピューテーション式を用いることで、似たようなことができる。
モナドがやっていることは、実は強力な関数合成の一種であって、実は複雑なことはなにもしていない。にもかかわらず、モナドが難しいと言われる理由は、モナドが関数合成とジェネリックとアドホック多相が絡み合う複合体として表現される抽象であるからかもしれない。加えて、Haskellにあらわれる「クラス」や「インスタンス」という用語が、一般的なオブジェクト指向のそれの意味とまるで異なることも一因かもしれない。こういった事情があるので、日頃から抽象的な設計手法やメタプログラミングにあまり馴染みのないプログラマが突然モナドに触れると火傷してしまうというのは致し方ないことだ。プログラミングの基礎的素養は必要だが、順を追って丁寧に学習していけば「モナドがなにをやってくれているのかを理解する」こと自体はそれほど難しいことではない。
憧れの(闇の)カンスウガタゲンガー達は、暇さえあればモナドの話をしています。彼らは三度の飯よりモナドを好みます。なぜ彼らはモナドに夢中になるのか。モナドはそんなにも魅力的な存在なのでしょうか。そしてモナドは一体なんの役立つのでしょう。モナドはジェネリックな関数合成だと説明しました。しかし、実際に何の役に立つかはあまりピンとこないかもしれません。
モナドはメタ戦略だといいました。プログラミングにおいて戦略は重要なファクターです。関数プログラミングを構造化するための戦略を定義するのに極めて重要なツール、それがモナドです。モナドなくして関数プログラミングは語れません。モナドには、そう言い切れるそれを特に決定付けるいくつかの特徴があります。
(1)複雑な計算の可読性向上が期待できる。モナドは美しい!
計算を繋ぐBind演算子(>>=)によって、関数プログラミングを命令型的に表現することができる。モナド合成時の実装の詳細を意識しなくてもよいようになっているので、コードを劇的に単純化することができ、可読性の向上が見込めます。HaskellのBind演算子(>>=)は、F#のコンピューテーション式(ビルダー)では
と表現されて、 シグネチャは、
です。
Bindの働きは、平たく言えばただの関数の結合ですが、通常の関数の合成を拡張した働きを持たせるのが一般的で、たとえば、Maybeモナドでは、成功と失敗を表す2種類のデータを次の関数へ伝達することができるようになっている。F#でoption型を利用することを考えた場合、Maybeモナドは欠かせないものとなります。→ F#プログラマのためのMaybeモナド入門 - みずぴー日記
ただし、モナドを利用することでコードの美しさが保てるかどうかは、実装言語によって大きく変わってくきます。たとえばHaskellには型クラスがあるのでとてもエレガントに表現されている。コードも非常に美しいです。F#ならコンピューテーション式できれいに表現できる。Scalaではfor式できれいに表現できる。他の言語だとまた状況は変わってきます。
(2)カプセル化とモジュール性を確保。頑丈なプログラミングを促進する!
モナドのBindによる合成においては、合成時の値がモナドの外に漏れ出ることがないのでモジュール性が保証されます。この特徴によって、プログラマはモナド内でプログラムしたものが他の領域に干渉することを懸念する必要がないので、とても幸せです。これはモナドプログラミングの純粋さを示すものであり、計算そのものとその合成戦略を分離していることを意味しています。つまりモナドは安全で動的に組み合わせ可能な計算として機能します。
まったくの別物なので、誤解を招いてしまいそうで例えることを躊躇しそうになるが、オブジェクト指向プログラマであれば、動的に機能拡張が可能という意味では、GoFデザインパターンにおける Decoratorパターン をイメージすると、モナドの拡張可能なモジュール性というものを想像しやすいかもしれない(あくまでイメージで)。オブジェクト指向パラダイムのDecoratorパターンでは、オブジェクトとオブジェクトを組み合わせることで、新たに複雑なオブジェクトを生成していました。 関数プログラミングのパラダイムでは、より高い抽象であるモナドでそれを高い次元で実現する。状況に応じてさまざまな用途のモナドを使い分けたり、必要に応じて複数のモナドを合成したりします。
(3)モナドによる柔軟性の高い関数型プログラミングは、アジャイル性を与える!
モナドは汎用なインターフェイスを持ち、関数の純粋さを保つ性質がある。これによりコードのリファクタリングが容易になり、また多くの場合は反復開発が容易になる(アジャイル性の向上)。モナドを用いない関数型プログラミングより、モナドを利用したプログラムはより柔軟性が高くなりやすい。これはモナドによる計算が、一連のプログラムとデータをカプセル化し、モジュール性があることからも説明できます。アジャイルというとオブジェクト指向とセットで語られることが多いが、真にアジャイル性を追及するならば、関数プログラミングを選択することがベターであることは確定的明らかである。前ふりが長くなりましたが、やっとこの記事を書くきっかけとなったIOモナドの話をします。IOモナドは副作用をモナドの中に封じ込めて、純粋関数を表現するための仕組みを提供するパターンであり、非常に巧妙な仕組みです。少し言い換えると、副作用のある部分と副作用のない部分を明確に分離するための仕組みを提供する戦略を持っています。
この夏、「ATEND - 第0回 スタートHaskell」というイベントがあるそうです。定員150人にもかかわらず、すでに定員オーバーしています(すごい)。最近モテ言語と言われているだけあって、Haskell恐ろしい人気です。そちらのキャッチフレーズ(?)より以下を引用させていただきます。
これが意味するところがそういう意味なのかはわかりませんが、IOモナドはHaskellにおいて、脱Haskell初心者の鬼門のひとつとされているモナドのひとつで、とりわけ特殊な存在として捉えられています。しかし、「IOモナドはモナドじゃないよ」「IOモナドなんて勉強しなくてもモナドは使えるよ」などと言う声もあります。それでいて魔術的な一面も持っていたり、IOモナドはモナドの中でも他とは毛色の違う不思議な存在です。これは、HaskellのIOモナドの定義がプラットフォーム依存(評価器, 実行器依存)であることに起因します。Haskellの「純粋さ(参照透明性)」に密接な関わりをもっています。さらにHaskellは遅延評価を採用している言語であることも関係してきます。このような特徴を持つIOモナドは特別な存在です。したがって、設計思想の異なる他の言語でHaskellのIOモナドを真似ることは難しいでしょう。
IOモナドについて語るには、まずは副作用とは何なのかを知る必要がありました。
副作用とは、関数やメソッドなどのある処理(計算)単位が、外部の環境になにかしら影響を及ぼすことを言います。つまり、処理の中で論理的な状態を変化させて、それ以降で得られる結果になんらかの影響を与えることです。代表的な例としては、コンソールを使った入出力や変数への値の破壊的代入、UIへの描画などがあげられます。
副作用がなく一貫性のある処理単位を純粋関数と呼ぶ。
「純粋」という修飾は、つまりそれがコンポーザブルであることを意味していて、大きく2つの特徴を持っている。まず、「自己完結」しているという特徴がある。そのため、純粋関数は他との結び付きや相互依存を一切気にすることなく、関数を自由に合成することができる。そして、純粋関数は「状態を持たない」。純粋関数の値(計算結果, 返り値)は、常にその引数の値によって決定される。同じ引数を伴う関数の計算が、いついかなる場合も同じ値となる(いわゆる参照透明性)ときそれは純粋関数だ。外部の環境に対して副作用を伴うような関数を部品として扱うと、必ず危険を伴う(バグりやすい)。環境に依存していて、事あるごとに結果が異なるような関数を使うなんて正気の沙汰じゃない!という意見はもっともです。それに対して、「自己完結」していて「状態がない」という環境に依存しない特徴を持っている純粋関数は、コンポーサブルな安全な部品として扱える。
関数型言語でこそ、より意味のある純粋関数
関数を純粋にすると、外部環境を意識せずに済むので可読性が高くなります。状態を持たないので、コードのリファクタリングが容易にもなります。また、多くの場合は設計の変更に強く、反復開発が容易になりやすいでしょう(アジャイル性の向上)。他との依存性もないので単独でのテストも容易で、テストコードは関数を呼び出すことに集中できて、デバッグも容易になるなど良いことずくめ。この純粋関数の特徴をより高く抽象的に昇華されたのがモナドで、合成可能なメタ純粋関数として捉えることもできる。純粋関数は、もちろんHaskellだけのものでもなければ、ScalaやF#などを含めた関数型言語だけのものでもない。Java, C#, VB.NETというような、一般的なオブジェクト指向言語での実装においても、副作用をともなわない純粋関数を書くことは常に意識されてきた。ただ、オブジェクト指向言語では、関数をファーストクラス(第一級の値, first-class)*2として扱えないため、関数を部品として扱えず、純粋関数が持つ特徴である「自己完結」していて「状態を持たない」ので構成可能で安全な部品として扱えるという最大のメリットを享受することができない。それに対して、関数型言語はコンポーサブルな純粋関数を自由に組み合わせることで、より大きな純粋関数を作り出して効果的に再利用することができる。モナドについても同様のことが言え、純粋関数よりもさらに強力さを持つ。これは「なぜ関数型で書くのか」の理由のひとつと言える。
初めて読んだHaskellの本「ふつうのHaskellプログラミング」にはこんなことが書いてありました。
IOモナドにはふたつの目的があって、まずひとつは「副作用を伴う処理(アクション)の評価順序を確実に指定する」こと。もつひとつは、「参照透明性を保ったまま副作用を実現する」ということでした。
あるいは、「IOモナドは、まだ入出力を実行していない世界をアクションの中に包み込んでいて、アクションが評価されると、入出力の結果と、入出力を実行した後の世界が生成されます。」というようなことも書いてありました。3年くらい前に読んで、なんとなくわかったような気になっていましたが実は何もわかっていませんでした。そのときはまだ他の関数型言語も学んだことがなく、Haskellにも触れたばかりだったので。とここに言い訳をしておく。今思えば、IOモナドからモナドを入門するのは、ちょっと難しいのではないかと思います。
IOモナドの目的ですが、まず、ひとつめの目的は、Haskellが遅延評価*3を特徴としている言語であるということが深く関係しています。なので、主にHaskellというプログラミング言語におけるIOモナドの立ち位置としての目的と言えるかもしれません。ふたつめの目的は、副作用のある計算を純粋関数で表現すること。ひいては、副作用のカプセル化とモジュール性の確保が目的であると言えます。Haskellでは、副作用を持ち込みながら参照透明性を保つ手段として、モナドの持つ特徴をうまく利用していて、IOモナドを一方向モナドとして扱い、実行器まで巻き込むことで副作用をうまく封じ込めることに成功している。実行器まで巻き込むということがあまり説明されていないことが多いので、初心者は路頭に迷ってしまうのだと思う。
一方向モナドの素晴しい機能は、プログラムのモナドではない部分の関数型の性質を破壊することなく、そのモナド演算子中で副作用をサポートすることができるというものです。
Haskellでは、すべての計算はトップレベルのIOモナドの中で起こります。実行器まで巻き込むというのはつまりそういう意味です。副作用は全てIOモナドにリフトされます。開発者が関数の外部環境に勝手にアクセスすることはできないようになっています。なので純粋です。「副作用のある計算を純粋関数で表現する」という、副作用と純粋関数の意味を考えると一見矛盾した要求に対して、モナドはみごとな解決策を与えているというわけです。IOモナドが一方向モナドであるため、純粋関数の役割を果たしていて、副作用を内包しながらも参照透明性が確保されている。これは実に巧妙というかなんというか、面白い。
F#やScalaなど副作用を許容する非純粋関数型言語においても、出来る限り参照透明性を保つようにプログラムを組むことが推奨される。非純粋関数型言語の「純粋さ」は開発者にゆだねられています。
IOモナドが副作用を構成可能な純粋関数としてくれるのならば、それは非純粋関数型言語屋にとっても朗報です。副作用をカプセル化してコンポーサブル化するということも、IOモナドの目的のひとつと言うことができるでしょう。
さて、無駄に長い前置きは以上です。
ここからが本題。
Haskellは純粋関数型言語です。副作用に対して厳格です。そして遅延評価を採用しています。よく訓練されたカンスウタガゲンガーは、副作用のある関数とない関数を分けて実装することを考えるそうです。しかし、それに依存したのでは、プログラムの純粋さを死守することはできません。そこで、HaskellではIOモナドというプラットフォーム依存のモナドを導入することでこの問題をエレガントに解決しました。言い方を変えると、Haskellでは、IOモナドによって副作用のある部分とない部分を完全に分けることをプログラマに強制させる仕組みを設けました。ゆえにHaskellは純粋でいられるのです。
先に「設計思想の異なる他の言語でHaskellのIOモナドを真似ることは難しいでしょう。」と述べました。F#でHaskellのIOモナドを完全模倣することはできません。が、「F#の立ち位置としてのIOモナド」ならば表現することはできなくはありません。
F#は非純粋関数型言語です。seq, asyncなどの組み込み済みのコンピューテーション式が提供されてはいますが、コンピューテーション式(によるモナドの実装)は基本的に自作してくださいというスタンスです。当然、IOモナドをはじめとしたHaskellで標準的に備わっているモナドはありません。
また、副作用に対しては比較的寛容で、プログラマのさじ加減ひとつでプログラムは純粋にも破壊的にもなります。
もちろん我々カンスウガタゲンガーは出来る限り純粋さを保つことを望んでいます。F#で開発する場合でも、副作用を適切に分けてプログラミングしたいという要求は当然あります。すべての副作用をIOモナドの中に封じ込めるいうのは、F#の場合あらゆる面で現実的ではありませんが、局所的に副作用をIOモナドによって管理することは、それなりに意味のあることです。なぜなら、よく訓練されたカンスウタガゲンガーは、副作用のある関数とない関数を分けて実装することを考えるから*4。
以上のことを踏まえて、F#でIOモナドを模倣することを考えてみます。しかし、これには大きな問題がいくつかあります。ひとつは、F#がオープンソースであるとは言え、Haskellのように評価器、実行器まで巻き込むことはできないこと。この点に関しては即詰みです。なので評価器と実行器のことは忘れて、能動的に着火する必要がある関数としてIOモナドの表現を考えます。また、副作用を含む合成可能な純粋関数としてのIOモナド(副作用のコンポーサブル化)を実現することを考えます。
では、さっそくF#でIOモナドを書いてみよう!となるわけですが、その前に、F#のもっとも優れた機能のひとつであり、F#でモナドを書く時に必要不可欠であるコンピューテーション式について簡単に触れておきたい。
コンピューテーション式は、あるF#コードを独自の解釈でユーザー定義することができる機能です。
つまり、F#言語構造の意味解析をプログラマが上書きしちゃえるんです。いわゆる言語指向プログラミング(LOP)を可能としています。非常に強力で面白い機能です。コンピューテーション式は、F#でモナドを実装するのにとても便利です。ただ、モナドを書くためだけに存在するものではなく、ドメイン固有言語(DSEL)としての利用も一般的です*5。for, if, yield!, use!, try withなどの補助的なキーワードの再定義も充実していて、モナドをより扱いやすいように式をカスタマイズすることもできます。目的によっては、コンピューテーション式(ビルダー)がモナドである(モナド則を満たす)必要はありません。
namespace CompExpr.Monad open System open Microsoft.FSharp.Core.Operators.Unchecked [<AutoOpen>] module Base = /// ComExprBase type ComExprBase () = member this.Using (x : #IDisposable, f) = use x = x f x member this.TryWith (f, handler) = try f () with e -> handler e member this.TryFinally (f, final) = try f () finally final () /// IOモナドモジュール module IO = /// IO判別共用体 type IO<'T> = internal IO of 'T let (>>) (_ : IO<_>) f = f () /// bind let (>>=) (IO(a)) k : IO<_> = k a let ioBind m k = m >>= k /// return let ioreturn a = IO a /// zero let iozero = IO () /// IOビルダー type IOBuilder() = inherit ComExprBase () member this.Bind (m, k) = m >>= k member this.Return x = ioreturn x member this.ReturnFrom m = m member this.Zero() = iozero member this.Delay (f : unit -> IO<_>) = f member this.Combine (g, f) = g >> f member this.For (xs : #seq<_>, f : (_ -> IO<unit>)) = xs |> Seq.fold (fun _ x -> f x) iozero member this.Yield (x) = ioreturn x member this.YieldFrom (x) = x member this.While (condition, (f : (_ -> IO<unit>))) = while condition() do f () |> ignore iozero /// IOビルダーを生成します。 let io = IOBuilder () let iowrap f a = IO (f a) let iowrap2 f a b = IO (f a b) let iowrap3 f a b c = IO (f a b c) let putChar = printf "%c" |> iowrap let putStr = printf "%s" |> iowrap let putStrLn = printfn "%s" |> iowrap let ioignore = fun _ -> iozero let getLine = System.Console.ReadLine |> iowrap let getKey = System.Console.ReadKey |> iowrap let getCurrentTime = io { return DateTime.Now } <| () let liftM f m = io { let! x = m <| () return f x} let join (IO(IO(a))) = io{ return a } type Either<'T, 'U> = |Left of 'T |Right of 'U //try :: Exception e => IO a -> IO (Either e a) let tryIO io = try Right ((io:unit -> IO<_>) <| ()) with e -> Left (id e) //catch :: Exception e => IO a -> (e -> IO a) -> IO a let catchIO io f = try (io: unit->IO<_>) <| () with e -> f e //finally :: IO a -> IO b -> IO a let finallyIO ioa iob = try (ioa:unit -> IO<_>) <| () finally (iob:unit ->IO<_>) <| () |> ignore let tryCatchFinallyIO io fio = try try Right ((io:unit->IO<_>) <| ()) with e -> Left e finally (fio:unit -> IO<_>) <| () |> ignore let getContents = seq { let condition = ref true while !condition do let line = System.Console.ReadLine() if line = null then condition := false yield fun () -> ioreturn line} let interact f = io { for x in getContents do let! x = x <| () putStr (f x) |> ignore }
とりあずではありますが、IOモナドっぽい何かと、その周辺機能の一部を実装しました。モナド則も満たしています。着火タイミングについては、IOモナドの合成結果をunit -> IO<'T> にすることでプログラマが制御できるようにしています。また、コンピューテーション式の特徴を活かしてビルダー内で、if, for, use!, try with, try finally などが利用できるようにしました。
let hello = io { return! putStrLn "Hello,World!" } let inout = io { let! s = getLine () return! putStrLn s } let h2 = io { do! hello () do! hello () return "こんにちは、世界!"} let h3 = io { let! s = h2 () do! hello () putStrLn s |> ignore do! inout () do! hello () return "さようなら" } let fire = io { let! s = h3 () do! hello () return s } fire () |> ignore ()
実行結果
Hello,World! Hello,World! Hello,World! こんにちは、世界! やっほー やっほー Hello,World! Hello,World!
IOモナドであるinout内のgetLineで入力を求められるので、「やっほー」と入力します。すると、実行結果は上記のようになります。とりあえずOKですね。「さようなら」はignoreで捨てられました。
IOモナドの処理順序
モナドは評価順序を決定するという特徴をもっていました。それは遅延評価の場合のみ関係してくるわけではありません。それを確認するために、forld(foldl)とfoldBack(foldr)で、IOモナドの合成順序を逆にしても評価順序に変化がないことを確認してみましょう。let aiueo = [io { return! putStrLn "あ"}; io { return! putStrLn "い"}; io { return! putStrLn "う"}; io { return! putStrLn "え"}; io { return! putStrLn "お"}] aiueo |> Seq.iter (fun x -> x () |> ignore) let compose a b = fun () -> ioBind (a()) b Console.WriteLine ("-----foldしても") |> ignore let aiueo'' = List.fold (fun (a:unit->IO<_>) b -> compose a b) (fun ()->iozero) aiueo aiueo'' () |> ignore Console.WriteLine ("-----foldBackしても") |> ignore let aiueo' = List.foldBack (fun (a:unit->IO<_>) b -> compose a b) aiueo (fun ()->iozero) aiueo' () |> ignore Console.WriteLine ("同じ結果になるよね?") |> ignore
実行結果
あ い う え お -----foldしても あ い う え お -----foldBackしても あ い う え お 同じ結果になるよね?
はい。いずれも同じ結果になりますね。Haskellの場合はさらに遅延評価も絡んでくるのでまた事情がちょっと変わってきますが、正確評価のF#において、IOモナドの処理順序が確定的に明らかになっていることが確認できました。
IOモナドの無限リスト
IOモナドによって副作用を包み込むことで、副作用をあたかもファーストクラスとして扱えるようになりました。つまり、副作用を含む関数をリストに格納できることを意味します。IOモナドで、副作用の無限リストを表現してみましょう。let hello = io { return! putStrLn "Hello,World!" } let infiniteHello = Seq.initInfinite (fun x -> hello) infiniteHello |> Seq.iter (fun x -> x () |> ignore)
Hello,World!フォーエバー…!!
5件だけ処理してみます。
let hello = io { return! putStrLn "Hello,World!" } let infiniteHello = Seq.initInfinite (fun x -> hello) infiniteHello |> Seq.take (5) |> Seq.iter (fun x -> x () |> ignore)
実行結果
Hello,World! Hello,World! Hello,World! Hello,World! Hello,World!
たいへんよくできました。
IOモナドと他のモナドを合成したい。
モナドを利用してプログラムを組んでいると、複数のモナドを組み合わせて扱いたくなるケースが多々でてきます。さまざまな領域の問題に対処するために必要なことです。例えば、IOモナドの中で「失敗するかもしれない計算」を扱いたいなんてことは、比較的多い要求のように思います。試しにIOモナドとMaybeモナドを組み合わせて利用してみましょう。let fire = io { let! iom = io {let! gl = getLine () return maybe { return gl } } <| () match iom with |Some x -> if x <> "" then putStrLn (x + x) |> ignore else putStrLn "入力してよねッ!ぷんぷくり〜ん(怒" |> ignore |None -> ()} fire () |> ignore
F#の立ち位置としてのIOモナドでは、上記のようにコンピューテーション式をネストして記述するかたちで、比較的簡単にモナドを合成することができます。ただ、ちょっと不吉なにおいがします。この程度のネストであれば許容範囲内かもしれないが、式が複雑化してくると可読性を犠牲にしてしまいそう。地獄のモナド「F#でモナドないわー、コンピューテーション式の多重入れ子ないわー、マジでないわー」と苛々しちゃうかもしれません。
そういえば、Haskellにはモナドを合成するための仕組みを持つ、モナド変換子というトランスレータがありました。IOモナドとMaybeモナドを合成するために、モナド変換子 MaybeTをちょっと真似てみましょう。
まず、合成対象のMaybeモナド
module Maybe = open IO let bind x k = match x with | Some value -> k value | None -> None let mreturn x = Some x type MaybeBuilder() = inherit ComExprBase () member this.Bind(x, k) = bind x k member this.Return(x) = mreturn x member this.ReturnFrom(x) = x member this.Delay(f) = f() member this.Combine(a, b) = if Option.isSome a then a else b () member this.Zero() = None member this.For(inp,f) = seq {for a in inp -> f a} member this.Yield(x) = mreturn x member this.YieldFrom(x) = x let maybe = new MaybeBuilder() let liftM f m = maybe { let! x = m return f x}
そしてモナド変換子 MaybeT
module Maybe = ...... module Trans = /// Maybeモナド変換子判別共用体 type MaybeT<'T> = internal MaybeT of 'T /// bind let (>>=) (MaybeT(a)) k : MaybeT<_> = k a let bindMaybeT m k = m >>= k /// return let maybeTreturn a = MaybeT a /// zero let maybeTzero = MaybeT () /// Maybeモナド変換子ビルダー type MaybeTBuilder () = inherit ComExprBase () member this.Bind(m, k) = m >>= k member this.Return(a) = maybeTreturn a member this.ReturnFrom(m) = m member this.Delay(f) = f() member this.Combine(a, b) = if Option.isSome a then a else b () member this.Zero() = maybeTzero member this.For(inp,f) = seq {for a in inp -> f a} member this.Yield(x) = maybeTreturn x member this.YieldFrom(x) = x // Maybeモナド変換子ビルダー let maybeT = new MaybeTBuilder () /// MaybeTはMonadIOのインスタンスだとかなんとか /// IO a をMaybeT IO aに持ち上げます let liftIO (m:IO<_>) = maybeT {return m} /// MaybeTはMonadのインスタンスだとかなんとか let liftM f m = maybeT { return f m } /// コンストラクター /// MaybeT IO a -> IO (Maybe a) let runMaybeT (MaybeT(IO(a))) = io { let! r = io { return maybe { return a } } <| () return r} module Unsafe = module IO = open IO /// 危険! (>_<) let unsafePerformIO (IO(a)) = a
MaybeTを使ってみます。
let fire = io { let iomaybe = Maybe.Trans.liftIO (getLine ()) |> runMaybeT <| () let! x = iomaybe match x with |Some x -> if x <> "" then putStrLn (x + x) |> ignore else putStrLn "入力してよねッ!ぷんぷくり〜ん(怒" |> ignore |None -> ()} fire () |> ignore
MaybeTを利用することで、IOモナドとMaybeモナドの合成をとてもシンプルに記述できました。それに、「ここでモナドを合成しているんだな!」ということが一目瞭然でわかりやすくなります。
F#でlazyれても、結局自分でファイヤーしなきゃスルーされてしまうわけで。あんまりありがたみないなあみたいな場面には割りと遭遇する。合成するような場合とか。
2011-06-20 16:31:57 via web
F#で遅延評価をするには、unit -> 'T で処理の実行を遅らせる。あるいは System.Lazy<'T>によって、遅延評価をカプセル化します。つまり、遅延評価の処理を合成したい場合は、lazy関数の中で合成したいすべてのSystem.Lazy<'T>に対してForce()メソッドを呼び出せばよいということになります。
let result = let a = lazy ("Hello,") let b = lazy ("World!") let h = lazy (a.Force() + b.Force()) lazy ([for i in 0..4 -> h.Force()]) Seq.iter (printfn "%s") <| result.Force()
たとえば、上記のような感じでlazyな関数は簡単に合成することができます。しかし、合成する際に必ず Force() で着火して評価しなればならず、着火漏れはバグの温床になりますし、見た目的にもどこか不恰好です。また、List.foldなどで、lazyな関数を合成したいような場合にも不便さを感じます。
F#のlazyは、System.Lazy<'T>型であらわされる遅延計算される値をカプセル化したものです。Lazy<'T>は遅延する値の入れ物とみなすことができます。ここで思い出されるのがモナド、あるいはコンピューテーション式です。モナドはジェネリックな関数合成を表現できて、どのように合成されるのかという実装の詳細を意識しなくてもよいという特徴がありました。ある入れ物に対して、モナド則を満たすようなBindとreturnを定義すれば、それはもう立派なモナドです。遅延評価な値を合成するための戦略を自作するとよさそうです。つまりオレオレモナドを作ることでこの不便さを解消できそうです。
とりあえず、基本的な実装をしてみます。以下のようになります。
namespace CompExpr.Monad module Lazy = type LazyBuilder () = let force (x : Lazy<'T>) = x |> function | Lazy x -> x /// bind let (>>=) (x:Lazy<'a>) (f:('a -> Lazy<'a>)) : Lazy<'a> = lazy (x |> force |> f |> force) /// zero let lazyzero = Seq.empty member this.Bind(x, f) = x >>= f member this.Return (x) = lazy x member this.ReturnFrom (x) = x member this.Zero() = lazyzero member this.Delay f = f() let lazyz = LazyBuilder () let lifM f (Lazy(a)) = lazy f a
利用側の実装サンプル
open System open CompExpr.Monad.Lazy let result = lazyz { let! a = lazy ("Hello,") let! b = lazy ("World!") return a + b} result.Force() |> (printfn "%s") |> ignore Console.ReadLine () |> ignore
実行結果
Hello,World!
で、とりあえずF#でコンピューテーション式として利用できるLazyモナドをつくることができたのですが、これだけだと利用する側は実はあまりうれしくありません。確かに、lazyな関数を合成する際に、Force ()メソッドを明示的に呼び出す部分を隠ぺいできましたが、この実装では単純な式を構築する場合にしか利用できません。lazyな関数をもっと直観的でかつ自由に組み立てることができる仕組みが欲しくなってきます。コンピューテーション式はそれができます。たとえば、コンピューテーション式内で、if式, for式, yield などを用いて遅延評価を合成しながら組み立てられるようにすると便利そうです。つまり、ドメイン固有言語(DSL)としての側面も持たせることで、さらに便利さが増します。
奥義とか言っちゃうと胡散臭さを禁じえませんが、あえてそう言い切っちゃいました。お察しください。
コンピューテーション式でドメイン固有言語(DSL)を作った経験をお持ちの方はおわかりの通り、
重要となってくるのは、Combine と Run をいかに使いこなすかということです。もちろん、コンピューテーション式で再定義可能なキーワードおよび、それに対応するすべてのメソッドが重要ですが、
コンピューテーション式を上手に使いこなす上で特に重要となってくるのが以下の2つメソッドです。
Combineメソッド
その名の通り式の「結合」を定義するためのものです。コンピューテーション式内の式の流れを統制するような役割を持っています。左から流れてくる式(式の境界線の上)を、右の式へ(式の境界線の下)受け流すというように、ムーディー勝山(消)をイメージすると理解しやすいです。さまざまな異なる式の変換をオーバーロード(多重定義)することで、柔軟な式を表現することができるようになります。ムーディー勝山は冗談なので忘れてください。
Runメソッド
これはコンピューテーション式の変換規則に明示されてはいませんが、ビルダークラス内で定義すると特殊な解釈がされます。Runメソッドを定義すると、builder {...}というコンピューテーション式を宣言すると同時にDelayメソッドが呼び出されます。つまり、最終的なビルダーの結果を決定づける定義を持たせることができ、最終的なビルダーの値を適切な型に変換する仕組みを提供していると解釈できます。Combineメソッドで扱っている式の流れにあわせて、最終的な式の結果を統一するのに役立ちます。もちろんオーバーロード(多重定義)可能です。Runメソッドの詳細については、The F# Draft Language Specification(http://goo.gl/7a1QH)を参照されたい。
F# Snippets(http://fssnip.net/)に投稿したものとして、冒頭でも紹介しましたが、LazyBuilderを作りました。
これは、ConbineとRunを効果的に利用した具体的な実装サンプルです。CombineおよびRunを多重定義することで、lazyな関数の合成を自然にコンピューテーション式内で表現可能にしています。また、IOモナドも扱えるように、F# Snippetsへ投稿したものに一部機能を追加しています。
namespace CompExpr.Monad open CompExpr.Monad.IO module Lazy = type LazyBuilder () = let force (x : Lazy<'T>) = x |> function | Lazy x -> x /// bind let (>>=) (x:Lazy<'a>) (f:('a -> Lazy<'a>)) : Lazy<'a> = lazy (x |> force |> f |> force) /// zero let lazyzero = Seq.empty let ioToLazyIgnore (xs:seq<Lazy<(unit -> IO<'T>)>>) = xs |> Seq.reduce (fun (Lazy(a)) (Lazy(b)) -> lazy (fun () -> (ioBind (a()) (fun x -> b()))) ) |> fun (Lazy(x)) -> lazy (x() |> ignore) let ioToLazy (xs:seq<Lazy<(unit -> IO<'T>)>>) = xs |> Seq.map (fun (Lazy(a)) -> a) |> fun x -> lazy (x) member this.Bind(x, f) = x >>= f member this.Return (x) = lazy x member this.ReturnFrom (x) = x member this.Zero() = lazyzero member this.Delay f = f() member this.Combine (a,b) = Seq.append a b member this.Combine (a,b) = Seq.append (Seq.singleton a) b member this.Combine (a,b) = Seq.append a (Seq.singleton b) member this.Combine (Lazy(a), Lazy(b)) = lazy Seq.append a b member this.Combine (a:Lazy<'T>, b:Lazy<seq<'T>>) = (a,b) |> function | (Lazy x, Lazy y) -> lazy Seq.append (Seq.singleton x) y member this.Combine (a:Lazy<seq<'T>>, Lazy(b)) = a |> function | Lazy x -> lazy Seq.append x (Seq.singleton b) member this.Combine (a:Lazy<seq<'T>>, b:seq<Lazy<'T>>) = let notlazy (xs:seq<Lazy<'T>>) = xs |> Seq.map (fun (Lazy(a)) -> a) a |> function | Lazy x -> lazy Seq.append x (notlazy b) member this.Combine (a:seq<Lazy<'T>>, b:Lazy<seq<'T>>) = let notlazy (xs:seq<Lazy<'T>>) = xs |> Seq.map (fun (Lazy(a)) -> a) b |> function | Lazy x -> lazy Seq.append (notlazy a) x member this.For (s,f) = s |> Seq.map f member this.Yield x = lazy x member this.YieldFrom x = x member this.Run (x:Lazy<'T>) = x member this.Run (xs:seq<Lazy<unit>>) = xs |> Seq.reduce (fun a b -> this.Bind(a, fun _ -> b)) member this.Run (xs:seq<Lazy<'T>>) = xs |> Seq.map (fun (Lazy(a)) -> a) |> fun x -> lazy x member this.Run (xs:seq<Lazy<(unit -> IO<unit>)>>) = xs |> ioToLazyIgnore member this.Run (xs:seq<Lazy<(unit -> IO<string>)>>) = xs |> ioToLazy member this.Run (xs:seq<Lazy<(unit -> IO<int>)>>) = xs |> ioToLazy let lazyz = LazyBuilder () let liftM f (Lazy(a)) = lazy f a let liftIO (Lazy(a)) = IO a
例1
let result = let h = lazyz { let! a = lazy ("Hello,") let! b = lazy ("World!") return a + b} lazyz { for i in 0..4 do yield! h } Seq.iter (printfn "%s") <| result.Force()
実行結果
Hello,World! Hello,World! Hello,World! Hello,World! Hello,World!
例2
CombineとRunを実装しているので、以下のように書くことができる。
let lazyp n = lazy (printfn "%d" n) let result2 = let a = lazyz { yield! lazyp 2 ()} lazyz { yield! lazyp 0 yield! lazyp 1 yield! a for i in 3..5 do yield! lazyp i yield! lazyp 6 yield! lazyz { yield! lazyp 7 yield! lazyp 8 ()} for i in 9..10 do yield! lazyp i yield! seq {for n in [11..15] -> lazyp n} yield! lazyz { yield! lazyp 16 yield! lazyp 17 ()} yield! lazyz { yield! lazyp 18 yield! lazyp 19 ()} yield! lazyp 20 () } result2.Force()
実行結果
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
例3
せっかくなのでIOモナドを利用したい。
let iom1 = io { return! getLine () } let iom2 = io { let! s = iom1 () return s} let iom3 = io { let! s = iom2 () return! putStrLn s} let result1 = lazyz { yield iom3 yield iom3 yield iom3 () } let ioResult1 = io { return result1.Force()} ioResult1 () |> ignore let iom5 = io { let! s = iom1 () putStrLn s |> ignore return s} let result2 = lazyz { yield iom5 yield iom5 yield iom5 () } let ioResult2 = result2.Force() let io6 = io{ let xs = Seq.map (fun x -> x) ioResult2 for x in xs do let! s = x() putStrLn s |> ignore return () } io6 () |> ignore Console.ReadLine () |> ignore
まとめ
・モナドはさまざまなプログラミングの問題に適用できるメタ戦略である。圏論からきてるらしいけど、ただ使うぶんには小難しい理論は割とどうでもいい。
・モナドを理解するには、ある程度プログラミングの素養が必要だが、とんでもなく難しいというわけではない。無意識に使っていることさえある。
・ある問題に対するモナドの適用可能性については、モナドをジェネリックな関数合成として捉えるとイメージしやすい。
・F#の立ち位置としてのIOモナドは、「副作用のある関数とそうでない関数を切り分けて管理したい」という要求に対してはある程度意味のあることだ。
・コンピューテーション式でモナドを表現することができる。さらにそれを柔軟なものとする仕組みを持っている。
・コンピューテーション式のCombineとRunを効果的に使えるようになると、利便性の高いモナドあるいはDSELを作れるようになる。要チェックや。
お疲れさまでした。
簡単そうに見えてややこしく 困難そうに思えてたやすい そんなモナド そんなモナド探してる 探してる
2011-06-19 16:00:34 via web
太陽系より果てしなく コンビニより身近な そんなモナド そんなモナド 探してる 探している
2011-06-19 16:06:45 via web
追記:やばい。モナドって実は空気だった。
.@igetaさんにモナドの(>>=)はF#の(>>)というより(|>)に似てんじゃね?と言われてアハ体験を頂いた。つまりモナドは空気だったんだよ!(えっまじで?)F#の(>>)は(>>=)の方じゃなくてKleisli composition演算子(>=>)というやつに似てたんだ
2011-07-05 09:00:50 via web
わたしはF#において、前方パイプライン演算子 (|>)はいい意味で空気のような存在だと思ってます*6。
(* F# *) (>>) : ('a -> 'b) -> ('b -> 'c) -> ('a -> 'c) (|>) : 'a -> ('a -> 'b) -> 'b
-- Haskell (.) :: (b -> c) -> (a -> b) -> (a -> c) ($) :: (a -> b) -> a -> b (=<<) :: Monad m => (a -> m b) -> m a -> m b (>>=) :: Monad m => m a -> (a -> m b) -> m b (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c) (<=<) :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
なるほど。($)演算子に似ているのは(=<<)の方だったかー。そして、(>>=)はF#の(|>)に似ているという事実。これつまり、モナドって空気だったんだ!(えっまじで?)みたいなアハ体験。そもそも、MonadはApplicative(適用可能)だったやん!ということに気づかされたのでありました。「ジェネリックな関数合成」というよりも「ジェネリックな関数適用」の方がより適切な表現でしたね。まぁイメージとしては大きくははずしていないと思うし、説明するための用語的には「関数合成」でもそんなにわるくはないとは思います。でも、これからは「関数適用」に改めたいと思います。本文中はそんな感じで脳内補完しつつ読みかえていただけると良いかなと思います。
いげ太先生ありがとう!
F#で楽々breakとcontinue。継続モナドまじパネぇっす!
id:einblickerさんが、「F#で継続モナド - einblickerの日記」というステキな記事を書いてくださいました。グッジョブすぎる!
以前、F#で継続渡し形式(CPS)変換を抽象的に考えてみたら、それってつまりHaskellの継続モナドみたいなものでした。ということで継続ワークフロー(簡易版)作った。という記事を書いたのですが、
当時の私には継続モナドはとても難しく、モナドで包む部分とcallCCについて華麗にスルーしていました。
今回、einblickerさんのコードを読んで、継続モナドについて少し理解が深まりました。相変わらずとても難しいんですけど。
で、コードを読んでいて少し気づいたことがあったので、
einblickerさんのコードを踏まえつつ、自分ならこんな風に書くかなーというのを書いてみました。が、間違えていました。
コメントにてeinblickerさんにご指摘いただいたとおりに修正しました。また、YieldとYieldFromの実装を追加しました。
どうもありがとうございます。もう一度見直してみます。
ContMonad.fs
namespace Monad.ContMonad [<AutoOpen>] module ContMonad = type Cont<'r, 'a> = Cont of (('a -> 'r) -> 'r) let runCont (Cont c) = c let callCC f = Cont <| fun k -> runCont (f (fun a -> Cont <| fun _ -> k a)) k let creturn a = Cont <| fun k -> k a type ContBuilder () = member this.Return(a) = creturn a member this.ReturnFrom(a) = a member this.Bind(Cont c, f) = Cont <| fun k -> c (fun a -> runCont (f a) k) member this.Zero() = this.Return() member this.Combine(c1, c2) = this.Bind(c1, fun _ -> c2) member this.For(seq, f) = Seq.fold (fun cc elem -> this.Combine(cc, f elem)) (f <| Seq.head seq) <| Seq.skip 1 seq member this.Delay (f) = f () member this.Yield (a) = creturn a member this.YieldFrom (a) = a let cont = new ContBuilder () type ContBuilder with member this.foreach seq f = cont { do! callCC <| fun break' -> cont { for i in seq do do! callCC <| fun continue' -> cont { do! f i (break'()) (continue'()) } } } |> runCont <| ignore
Sample.fs
namespace ConsoleApplication1 module Sample = open Monad.ContMonad cont.foreach [1..20] (fun i break' continue' -> cont { if i = 18 then do! break' printfn "foo" else if i % 2 = 0 then do! continue' printfn "bar" else printfn "%d" i }) System.Console.WriteLine () |> ignore cont.foreach [1..20] (fun i break' continue' -> cont { if i = 18 then do! break' printfn "foo" else for x in 1..i do printf "%d" x printfn "" }) System.Console.ReadLine () |> ignore
実行結果
1 3 5 7 9 11 13 15 17 1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112 12345678910111213 1234567891011121314 123456789101112131415 12345678910111213141516 1234567891011121314151617
F#で楽々breakとcontinueできちゃってるよ。継続モナドまじパネぇっす!
(よいこは、「C#ならふつうにbreakとcontinueできるじゃん」とかなんとか言わない。)
ちなみに、 break と continue の2つのキーワードは将来利用するために予約されているので、
F#の今後のバージョンでサポートされるかもしれません。
おまけ:モナド則の確認
namespace ContMonad.UT open System module Tests = open NUnit.Framework open FsUnit open Monad.ContMonad [<TestFixture>] type ``ContMonad モナド則`` () = let (>>=) m f = cont {let! x = m return! f x} let return' x = cont { return x } let x = 1 let m = cont { return 3 } let f x = cont { return 4 + x } let g x = cont { return 2 * x } let assertEqual (left, right) = let result = cont {let! a1 = left let! a2 = right return a1 |> should equal a2} |> runCont <| ignore () let (==) left right = assertEqual (left, right) [<Test>] // モナド則1: return x >>= f == f x member test.``モナド則1`` () = return' x >>= f == f x [<Test>] // モナド則2: m >>= return == m member test.``モナド則2`` () = m >>= return' == m [<Test>] // モナド則3: (m >>= f) >>= g == m >>= (\x -> f x >>= g) member test.``モナド則3`` () = (m >>= f) >>= g == (m >>= (fun x -> f x >>= g)) // nunit-gui-runner let main () = NUnit.Gui.AppEntry.Main([|System.Windows.Forms.Application.ExecutablePath|]) |> ignore main ()
Observableコンピューテーション式はモナド則を満たしているか否か。
前回のエントリ「F#でRxる。よく訓練されたF#erはコンピューテーション式をつくる。」で紹介いたしました、
Observableコンピューテーション式について補足します。モナド則を満たしているか否かについてです。
Haskellにおいて、モナドがモナド則を満たしているとき、
1. (return x) >>= f == f x
2. m >>= return == m
3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)
以上の三つの条件に満足しています。
モナドのすべてによると、最初の規則は return が >>=*1 に関して左単位元に なっていることを要請していて、
二番目の規則は return が >>= に関して右単位元になっていることを要請してる。 最後の規則は >>= に関する一種の結合法則とのことです。
これを初めて読んだときはさっぱりわかりませんでした。今も確信を持ってわかったとは言いきれませんが、まぁ、なんとなく雰囲気はつかんでいるつもりです。
Observableのコンピューテーション式では、どうでしょうか。
namespace FSharp.Rx.UT open System module Tests = open System.Reactive open NUnit.Framework open FsUnit open FSharp open FSharp.Rx [<TestFixture>] type ``monad soku `` () = [<Test>] // モナド則1: return x >>= f == f x // return された値を保持するための変数(というか継続)は、なくしてしまうことができますよの規則 // モナドで計算を繋ぐにしろ、もともと繋がっている計算をモナドでくるんでも一緒だね member test.``monad soku1`` () = observable { let! a1 = observable{ let! a = observable {return fun x -> x * 2} let! b = observable {return 3} return a b} let! a2 = observable{ return 3 |> fun x -> x * 2 } return a1 |> should equal a2 } |> Rx.subscribe(fun _ -> ()) |> ignore [<Test>] // モナド則2: m >>= return == m // bindしてreturnしても結局同じことだよねの規則 // あるいは、結局最後の式が return されることになるので、明示的な return は意味ナッシンというお話 member test.``monad soku2`` () = let m1 = observable{ let! a = observable {return "F#"} return a} let m2 = observable{ return "F#" } Reactive.Testing.Extensions.AssertEqual(m1, m2) // モナド則3: m >>= (\x -> f x >>= g) == (m >>= f) >>= g // 多段ネストしたモナドでも(どんなに深くても)、結局のところ一段のモナドと等価ですよの規則 [<Test>] member test.``monad soku3`` () = let m1 = observable{ let! a = observable {return 3} let! b = observable {return 4} let! x = observable {let! d = observable{return a} let! e = observable{return b} return d + e} let! c = observable {return fun x -> x * 2} return c x} let m2 = observable{ return 3 + 4 |> fun x -> x * 2 } Reactive.Testing.Extensions.AssertEqual(m1, m2) // nunit-gui-runner let main () = NUnit.Gui.AppEntry.Main([|System.Windows.Forms.Application.ExecutablePath|]) |> ignore main ()
ごくごく単純な確認ですので、正確な証明とまではいきませんが、
Observableコンピューテーション式が、モナド則を満たしているであろうことをゆるく確認することができます。
てゆうか、Observableコンピューテーション式は、単純にRxのObservableをはめ込んで適用しただけの代物なので、
Rxがそもそもモナド則を満たしているというのが本当のところです。RxのObservableはまさにモナドなのです。
[追記]
@nobuhisa_kさんに、コメントにてナイスつっこみを頂きました!
おっしゃるとおりで、上記のモナド則3の確認は間違えていますね。
モナド則3は、誤解を恐れずイメージしやすいように大雑把に言うと、「(2 * 3) * 4 * 5 == 2 * (3 * 4) * 5」だよねみたいな。
モナドにおいてもこれと同じことが成立していて欲しいと。していなきゃ困ると。
ということで、丸パクリで書き直してみました。
お手軽にお試しできる版
let x = 1 let m = observable { return 3 } let f x = observable { return 4 + x } let g x = observable { return 2 * x } let (>>=) m f = observable {let! x = m return! f x} let return' x = observable { return x } let prove (left,right) = observable {let! x = (left:IObservable<'a>) let! y = (right:IObservable<'a>) return x = y} prove (return' x >>= f, f x) |> Rx.subscribe(fun b -> printfn "モナド則1 : %b" b) |> ignore // true prove (m >>= return', m) |> Rx.subscribe (fun b -> printfn "モナド則2 : %b" b) |> ignore // true prove ((m >>= f) >>= g, m >>= (fun x -> f x >>= g)) |> Rx.subscribe(fun b -> printfn "モナド則3 : %b" b) |> ignore // true
よりテストっぽく
namespace FSharp.Rx.UT open System module Tests = open System.Reactive open NUnit.Framework open FsUnit open FSharp open FSharp.Rx [<TestFixture>] type ``Observable モナド則`` () = let (>>=) m f = observable {let! x = m return! f x} let return' x = observable { return x } let x = 1 let m = observable { return 3 } let f x = observable { return 4 + x } let g x = observable { return 2 * x } let assertEqual (left, right) = Reactive.Testing.Extensions.AssertEqual((left:IObservable<'a>), right) let (==) left right = assertEqual (left, right) [<Test>] // モナド則1: return x >>= f == f x member test.``モナド則1`` () = return' x >>= f == f x [<Test>] // モナド則2: m >>= return == m member test.``モナド則2`` () = m >>= return' == m [<Test>] // モナド則3: (m >>= f) >>= g == m >>= (\x -> f x >>= g) member test.``モナド則3`` () = (m >>= f) >>= g == (m >>= (fun x -> f x >>= g)) // nunit-gui-runner let main () = NUnit.Gui.AppEntry.Main([|System.Windows.Forms.Application.ExecutablePath|]) |> ignore main ()
わかりやすい。これならHaskellな人にも怒られなさそうですw
コンピューテーション式(Computation Expressions)をつくったら、
こんな風にモナド則を満たしているかどうか確認するとよいですね(実際はもっと抽象化した方がいい)。
これでモナド則ももうこわくないでござる。
あわせて読みたい
モナド則を満たすべき理由 - HaHaHa!(old)
http://haskell.g.hatena.ne.jp/nobsun/20080928/p1
これは参考になる
*1:bind