top  Index  Search  Changes  RSS  Login

モナド

訳あって Haskell 試食中. モナドって, こんなイメージでいいんでしょうか?

(参考ページ)


  • 慣れない内容は, 頭がしんどい
  • 慣れない表現も, 頭がしんどい
  • 両方いっぺんだと, もう○×△□…

なので, ひとまず haskell は置いといて, scheme にしてみます.


Intro.

ふつうの「値」を包んで, ふわふわした謎な外見の何か(以下「ふわふわ」) にするラッパー ret (return のつもり)を考えよう.

 (ret 3)  → 値 3 を包んだ「ふわふわ」が得られる

しょうもない例は,

 (define (ret x) (cons '*fuwafuwa* x))

こんな ret 自身は, 「値を食ってふわふわを吐く関数」. この「…」を縮めて「関数~」と呼ぶことにする.

ret を使って, 他にもいろいろな関数~を作ることができる. 例えば…

 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))

次に, 「ふわふわを関数~に食わせる」しくみとして, >>= (bind のつもり)を導入する:

 (>>= ふわふわ 関数~)  → 新しい「ふわふわ」が得られる

またしょうもない例は,

 (define (>>= m f) (f (cdr m)))

一般に, >>= は次の「モナド則」を満たすものとする.

  • (>>= (ret x) f) は (f x) と同じ
  • (>>= m ret) は m と同じ
  • (>>= (>>= m f) g) は (>>= m (lambda (x) (>>= (f x) g))) と同じ

いまの >>= は, さっきの ret とあわせて, 確かにモナド則を満たしている.

 ;; コピペして実行してみよう
 (define (ret x) (cons '*fuwafuwa* x))
 (define (>>= m f) (f (cdr m)))
 
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 
 (>>= (ret 3) inc)  ;; → (*FUWAFUWA* . 4)
 (inc 3)            ;; → (*FUWAFUWA* . 4)
 
 (>>= (inc 7) ret)  ;; → (*FUWAFUWA* . 8)
 (inc 7)            ;; → (*FUWAFUWA* . 8)
 
 (>>= (>>= (ret 3) inc) sqr)                   ;; → (*FUWAFUWA* . 16)
 (>>= (ret 3) (lambda (x) (>>= (inc x) sqr)))  ;; → (*FUWAFUWA* . 16)

これ(Identity モナド)だと「ありがたみ」が見えないけど, 実はいろんなことがこの枠組みにのってしまう. >>= という「つなぎ」に細工すれば, 確かにいろいろできそう.


先へ進む前におさらい:

  • (ret 値) は, その値を包んだ「ふわふわ」
  • (>>= ふわふわ 関数~) も「ふわふわ」. 気分としては, 「ふわふわの中身の値」に関数~を適用してできた新しいふわふわ.
  • 「関数~」とは, 値を食ってふわふわを吐く関数のこと

例: Maybe

「失敗すると値を返さない可能性のある関数」を, モナドで表現できる.

 (define (ret x) (cons '*just* x))  ;; 成功
 (define (fail x) '*nothing*)       ;; 失敗
 (define (>>= m f) (if (eq? m '*nothing*) m (f (cdr m))))
 
 (define (div6 x) (if (= x 0) (fail 'dummy) (ret (/ 6 x)))) ;; 0 だと失敗
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 
 (>>= (>>= (div6 2) inc) sqr)  ;; → (*JUST* . 16)
 (>>= (>>= (div6 0) inc) sqr)  ;; → *NOTHING*

inc や sqr の定義に「場合分け」(もし x が失敗だったら云々)を書かなくて よいのがミソ.


例: エラー処理

Maybe をちょっと改造すれば, エラーの捕捉ができる.

 (define (ret x) (cons '*right* x))         ;; 成功
 (define (throw-error x) (cons '*left* x))  ;; エラー
 (define (>>= m f) (if (eq? (car m) '*left*) m (f (cdr m))))
 (define (catch-error m f) (if (eq? (car m) '*right*) m (f (cdr m))))
 
 (define (div6 x) (if (= x 0) (throw-error 'zero) (ret (/ 6 x)))) ;; 0 だと失敗
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 (define (recov x) (ret (cons 'recovery x)))  ;; エラー時の処理をする関数~
 
 (catch-error (>>= (>>= (div6 2) inc) sqr) recov)  ;; → (*RIGHT* . 16)
 (catch-error (>>= (>>= (div6 0) inc) sqr) recov)  ;; → (*RIGHT* RECOVERY . ZERO)

うれしさも Maybe と同様. inc や sqr に「もし x がエラーなら」なんて場合分けを書かなくてよい.


例: 非決定性

非決定性計算ごっこもモナドで. ここでの「ふわふわ」は「とり得る値のリスト」とする.

 (define (ret x) (list x))
 (define (>>= m f) (apply append (map f m)))
 (define mzero '())
 (define (mplus m n) (append m n))
 
 (define (range u v) (if (> u v) mzero (mplus (ret u) (range (+ u 1) v))))
 
 (define (positive x) (if (> x 0) (ret x) mzero))
 (define (small x) (if (< x 5) (ret x) mzero))
 
 (range -10 10) ;; → (-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 0 1 2 3 4 5 6 7 8 9 10)
 (>>= (range -10 10) positive)  ;; → (1 2 3 4 5 6 7 8 9 10)
 (>>= (>>= (range -10 10) positive) small)  ;; → (1 2 3 4)
 
 ;; もうちょっとだけ凝った例
 (define (kons x) (lambda (y) (ret (cons x y))))
 (define (qons m) (lambda (x) (>>= m (kons x))))
 (define (sum-is x) (lambda (z) (if (= (+ (car z) (cdr z)) x) (ret z) mzero)))
 (>>= (range 0 3) (qons (range 4 6)))
 ;; → ((0 . 4) (0 . 5) (0 . 6) (1 . 4) (1 . 5) … (3 . 4) (3 . 5) (3 . 6))
 (>>= (>>= (range 0 3) (qons (range 4 6))) (sum-is 7))
 ;; → ((1 . 6) (2 . 5) (3 . 4))

例: 状態

ここでの「ふわふわ」は, 「状態を食って, 値と次状態を返す関数」とする. つまり, ふわふわには入口が一つと出口が二つあって, 入口に状態を入れれば, 出口から値と次状態が出てくる.

(>>= m f) の結果もふわふわだから, 状態 s を入れたら値と状態が出ないといけない. 具体的には次のとおり: 状態 s をまずふわふわ m に入れれば, 値 x と次状態 t が出てくる. この値 x と次状態 t を受けて, さらに次の値 y と状態 u とを定めるのが f の仕事. ただし, f はその仕事をすなおに (lambda (x t) …) の格好では表現していない. そうじゃなく, f は関数~ の格好で仕事を表現する. つまり,

  • f は値 x を食ってふわふわ n を吐く
  • そのふわふわ n に状態 t を入れると, 次の値 y と状態 t が出てくる

という二段階手順. すなおな表現に言いかえれば, こんな関数 g だと思えばよい.

(define (g x t) ((f x) t))

f でも g でもやりたい仕事は同じ(→GoogleJ:カリー化). でもあえて関数~ として f で表現することにより, これをモナドの枠組にのせられる.

s→m───t──┐   ふわふわ(>>= m f)に状態sを与えて得られる値yと次状態u
  │      ↓   s, t, u: 状態
  └x→f ⇒ n→y x, y: 値
         ↓   m, n: ふわふわ
         u   f: 関数~

「値と状態」は, 実際には cons でまとめて表現.

 (define (ret x) (lambda (s) (cons x s)))  ;; 状態は変化させない
 (define (>>= m f) (lambda (s) (define r (m s)) ((f (car r)) (cdr r))))
 (define (next! x) (lambda (s) (cons x (+ s 1))))  ;; 状態を更新する関数~
 (define (state x) (lambda (s) (cons s s)))        ;; 状態を読む関数~
 (define (from s m) (m s))  ;; 初期状態 s をふわふわ m に入れる
 
 (define (sqr x) (ret (* x x)))  ;; おなじみの関数~
 
 (from 0 (>>= (>>= (>>= (>>= (ret 'dummy) next!) next!) state) sqr))  ;; → (4 . 2)

set! を使わず, ちゃんと関数型で実現していることにも注目.


例: 入出力

ふつうのHaskellプログラミング を読んだら, 状態モナドの一種と解釈するような絵が載っていた. なるほど. こんな感じ?

  • 言語に最初からそなわった, 組み込みの「状態モナド」
  • 特別なのは, その「状態」とは本当の「我々が住む物理的世界の状態」なこと
 ;; 実装例 I: 理想的な架空の実装. 状態モナドと同じ定義で…
 (define (ret x) (lambda (s) (cons x s)))
 (define (>>= m f) (lambda (s) (define r (m s)) ((f (car r)) (cdr r))))
 
 ;; 以下は現実には書き下せないから, 「つもり」で我慢
 ;; ↓プログラム起動時の世界の状態
 (define (initial-world!?) '*initial-world*)
 ;; ↓世界の状態が s のとき行動 a をしたら, 世界の状態はどうなるか?
 (define (next-world!? a s) (list '*applied* a s))
 ;; ↓世界の状態が s のとき入力を読むと, どんな値が得られて世界はどうなるか?
 (define (read!? s) (cons (read) (next-world!? '*read* s)))
 ;; ↓世界の状態が s のとき x を出力すると, 世界はどうなるか?
 (define (write!? x s) (write x) (next-world!? (list '*write* x) s))
 
 (define (mread) (lambda (s) (read!? s)))                 ;; ふわふわを返す
 (define (mwrite x) (lambda (s) (cons #t (write!? x s)))) ;; ふわふわを返す
 (define (main m) (m (initial-world!?))) ;; プログラムは main の中に入れる約束
 
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 (main (>>= (>>= (>>= (mread) inc) sqr) mwrite))
 3  ;; 3 を入力 → 16 が表示される

もちろん, !? をつけた関数(全世界の状態を計算機上でシミュレート!?)なんて 現実には実装できるわけがない. それでも, プログラマは上のように錯覚していてよい. (錯覚していて困らないような mread, mwrite, main が, 別の方法で提供される)

 ;; 実装例 II: !? を避けた現実的実装. 「ふわふわ」は, 値を返す零引数関数.
 (define (ret x) (lambda () x))            ;; ふわふわを返す
 (define (>>= m f) (lambda () ((f (m)))))  ;; ふわふわを返す
 (define (mread) (lambda () (read)))       ;; ふわふわを返す
 (define (mwrite x) (lambda () (write x))) ;; ふわふわを返す
 (define (main m) (m))
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 (main (>>= (>>= (>>= (mread) inc) sqr) mwrite))
 3  ;; 3 を入力 → 16 が表示される

scheme ではありがたみが見えないけど, haskell では…

  • 「副作用」を解禁
  • 「実行順序の強制指定」を解禁
  • そんなおきて破りを, IO モナドという檻へ明示的に囲い込む (檻の外は潔癖を保つ)
  • しかも, 錯覚解釈なら, 「おきては破っていない」と強弁することだってできる

というわけで, 現実には実装例 II なんだけど, 使う際はそれを I のように気分よく錯覚できることがミソ, …なんだと思う.


例: ログ

ふわふわは「値とログの組」とし, >>= でログもとりまとめ. これにより, 「ログのとりまとめ」を本来の処理から分離できてうれしい.

 (define (ret x) (cons x '()))
 (define (>>= m f) (define r (f (car m))) (cons (car r) (append (cdr r) (cdr m))))
 (define (add-log m message) (cons (car m) (cons message (cdr m))))
 
 (define (inc x) (add-log (ret (+ x 1)) (cons '*inc* x)))
 (define (sqr x) (add-log (ret (* x x)) (cons '*sqr* x)))
 
 (>>= (>>= (ret 3) inc) sqr)  ;; → (16 (*SQR* . 4) (*INC* . 3))

例: 継続 (その一・継続渡し)

継続渡しの解説は,

それをモナドで実現する話.

(ret x) は, 「継続 c をもらって, その継続に値 x を託す」という関数.

 (define (ret x) (lambda (c) (c x)))

…という言い方だとイメージしづらいから,

  • (ret x) で作られる「ふわふわ」には, 差し込み口がある
  • その差し込み口にケーブル(継続 c)をさすと, 値 x が流れ出る

とでも思えば良いかと. (短く「ケーブル」と言ってるけど, その先につながった下流の処理装置まで含めたものが c)

(>>= m f) は, 「『ふわふわ m にケーブルをさして流れ出る値 x』を関数~ f に食わせて得られるふわふわ」. これをすなおに書くと…

 (define (>>= m f) (f (m (lambda (x) x))))  ;; (ア)

ということは… (>>= m f) にケーブル c をさすと, 「m に次のようなケーブル d をさした結果」が出る: d は, 「値 x をもらって, (f x) というふわふわを作って, そいつにケーブル c をさす」.

 (define (>>= m f) (lambda (c) (define (d x) ((f x) c)) (m d)))  ;; (イ)

あるいは, 直接書くと

 (define (>>= m f) (lambda (c) (m (lambda (x) ((f x) c)))))  ;; (ウ)

見かけた資料は, みんな(ウ)を使っている.

※ なぜ(ア)を使わないんでしょうか? scheme では, (ア)だとその場で評価されてしまうのが嫌? でも haskell なら放っといても遅延評価なんちゃうん? 「継続渡し」なんだから, 継続を組みたてていく(ウ)の書き方が素直ってこと?

後の都合から, (ア)でなく(ウ)の方を使う.

例 (1): 1 を足して自乗

 (define (ret x) (lambda (c) (c x)))
 (define (>>= m f) (lambda (c) (m (lambda (x) ((f x) c)))))
 
 (define (inc x) (ret (+ x 1)))
 (define (sqr x) (ret (* x x)))
 (define (id x) x)
 
 (define m (>>= (>>= (ret 3) inc) sqr))  ;; m はふわふわ. ケーブルをさすと値が…
 (m id)  ;; → 16

例 (2): 階乗

 (define (ret x) (lambda (c) (c x)))
 (define (>>= m f) (lambda (c) (m (lambda (x) ((f x) c)))))
 
 (define (fact n) (if (< n 2) (ret 1) (>>= (fact (- n 1)) (mul n))))
 (define (mul n) (lambda (x) (ret (* x n))))
 (define (id x) x)
 
 (define m (fact 5))  ;; m はふわふわ. ケーブルをさすと値が…
 (m id)  ;; → 120

例: 継続 (その二・call/cc)

call/cc 自体の解説は,

それをモナドで実現する話.

下のように ccc (call-with-current-continuation = call/cc のつもり) を定義すると, おもしろいことができる.

 (define (ccc f) (lambda (k) ((f (lambda (x) (lambda (c) (k x)))) k)))

「何ができるか」を先に例で見て, そのあと ccc の解読をしましょう.

例: 大域脱出

 ;; ret と >>= は「継続渡し」のときと同じ.
 (define (ret x) (lambda (c) (c x)))
 (define (>>= m f) (lambda (c) (m (lambda (x) ((f x) c)))))
 (define (ccc f) (lambda (k) ((f (lambda (x) (lambda (c) (k x)))) k)))
 
 (define (err x) (ret (/ x 0)))  ;; エラーになるはず!
 (define (id x) x)
 
 ;; n はふわふわ. ケーブルをさすと値が…
 (define n (ccc (lambda (q) (>>= (q 3) err))))  ;; (エ)
 (n id)  ;; → 3
 
 ;; 一方, ふつうに err を使ったら, もちろん…
 (define e (>>= (ret 3) err))
 (e id)  ;; → エラー

(エ) の方では err が実行されていないことに注目. (>>= m f) は m の中身の値を f へ渡すはずだったのに, なぜこんなことが?

>>= の定義は変えていないんだから, トリックは (q 3) の方にあるはず. 実は, (q 3) が「邪道なふわふわ」なことがタネ.

  • (ret 3) で作られるふつうのふわふわは, 「継続 c をもらって, その継続 c に値 3 を託す」
  • この (q 3) は, 「継続 c を受けとるけど, それは捨てて, ccc 時点での継続 k の方へ値 3 を託す」

どちらも外見はふわふわ(継続を渡すと値が得られる)なものの, 後者の内部メカニズムは, これまでの想定とは違う. ケーブル c をさせばスイッチは入るんだけど, さしたケーブル c には値が流れず, 裏につながった別のケーブル k の方へ流れ出てしまう.

タネを端的に見せましょう. これなら確かに, err は実行されない.

 (define (>>= m f) (lambda (c) (m (lambda (x) ((f x) c)))))  ;; (ウ再)
 ;; n はふわふわ. ケーブルをさすと値が…
 (define n (>>= (lambda (c) 3) err))  ;; (オ)
 (n id)  ;; → 3

この (lambda (c) 3) が, 邪道なふわふわの例. どんな継続 c をもらっても無視して 3.

※ >>= の定義が(ア)でなく(ウ)なのは, いまのトリックをできるようにという意図

というわけで, タネはわかった. あとは, こんな邪道なふわふわを組み立ててくれるしくみ ccc を どう作ればよいか, 考えていく.

(オ)には生で「3」が書かれているけど, これでは裏ケーブルにつながらない. 継続 k が裏ケーブルとして指定されたら, ここは当然 (k 3) でないといけない.

 (>>= (lambda (c) 3) err)  →  (>>= (lambda (c) (k 3)) err)

こうすれば, 一般の継続 k で (n k) がちゃんと動作する.

 (define n (lambda (k) ((>>= (lambda (c) (k 3)) err) k)))  ;; (カ)
 (n id)  ;; → 3
 (n (lambda (x) (+ x 4)))  ;; → 7

念のため翻訳: 「ふわふわ n にケーブル k をさしたら, 値が得られる. どんな値かというと, ふわふわ (>>= (lambda (c) (k 3)) err) にケーブル k を さして得られる値.」 … 今回は邪道なふわふわ(すでに裏口としてこっそり k がささってる)だから 表口に何をさしても同じだけど, 邪道でないときも想定して, 指定された k をちゃんとさしておく.

さて, 我々の目標は, ccc を作ることだった.

 (define n (ccc (lambda (q) (>>= (q 3) err))))  ;; (エ再)

 (define n (lambda (k) ((>>= (lambda (c) (k 3)) err) k)))  ;; (カ再)

になってほしいのだから, ccc のすべき仕事は,

  • (lambda (q) (>>= (q 3) err)) をもらって…
  • (lambda (k) ((>>= (lambda (c) (k 3)) err) k)) を返すこと.

言い直せば,

 (define (f q) (>>= (q 3) err))

のときに, f から

 (lambda (k) ((>>= (lambda (c) (k 3)) err) k))  ;; (キ)

を作ること.

見比べたら, (q 3) が (lambda (c) (k 3)) になればよいとわかる. つまり, 「(q x) が (lambda (c) (k x)) になれば」,

 (lambda (k) ((f q) k))

が(キ)と同じになる. 「…」は要するに「q が (lambda (x) (lambda (c) (k x)))」 ということだから, 結局

 (lambda (k) ((f (lambda (x) (lambda (c) (k x)))) k))

が(キ)と同じ.

こうして, 最初に出した定義が得られた.

 (define (ccc f) (lambda (k) ((f (lambda (x) (lambda (c) (k x)))) k)))

もう一度おさらい. (ccc f) は, ふわふわ. だから, (ccc f) にケーブル k をさすと, 値が得られる. 具体的には以下のとおり:

  • まず, 値 x を食って「邪道なふわふわ (lambda (c) (k x))」を返す関数~ を用意する. 直接さされたケーブル c を無視して, 元ケーブル k の方に値 x を流すのが, 邪道たるゆえん.
  • この関数~ をもらって, f はふわふわを作る. f の中で今の関数~ を使えば, 邪道なふわふわ (使用地点から元ケーブル k へショートカット)ができる. 使わなければ, ふつうのふわふわもできる.
  • 何にせよ, 「『f の作るふわふわ』へケーブル k をさして得られる値」が, 「(ccc f) にケーブル k をさして得られる値」.

感想

inc, sqr の定義や使い方 (>>= (>>= (ret 3) inc) sqr) はそのままに, これだけいろんなことができるのは, なかなかおもしろい.

SICP で言うと, 「俺 eval と俺 apply」を書いて いろんな「違う言語」を作る話に相当するんでしょうね. でも, それだと自由度ありすぎて呆然なので,

  • 筋の良い枠を設けて, 頭を整理する
  • さらに, その枠にはまったものを汎用的に扱う道具をそろえる

が, とりあえずのミソ?

…で, こんなイメージで合ってるんでしょうか? > Haskeller


コメント

  • 2004-11-30 (火) 21:17:33 名無しさん : Re: モナドって?経由でMonads in Schemeを発見. 上の「例: 状態」と同じ話っぽい.
  • 2005-02-11 (金) 17:26:36 cut-sea : いいですね。個人的にこういう感覚や気持ちを伝える説明って好き。モナド分かんない、でも分かりたいなんで公開してくれて感謝感謝!
  • 2005-02-11 (金) 21:14:45 名無しさん : どうもどうも. いや, 問題はこれが合ってるのかどうかで… ^^; わかってる人の査読がほしいところです.
  • 2005-02-11 (金) 22:39:47 cut-sea : 本質的な所じゃないんでごめんよぉですが maybe の例の tri は rec (逆数) とかを使った方がナイスかも。0除算で *nothing* や error を吐くと。
  • 2005-02-12 (土) 00:35:19 名無しさん : いただき! thx
  • 2005-02-12 (土) 02:23:24 名無しさん : 継続渡しの >>= の定義(ア)がいけない理由。m の実行中に外へ脱出した場合、f は実行されないはずなのに、(ア)だと f が必ず実行されてしまう
  • 2005-02-12 (土) 16:13:12 名無しさん : ありがとうございます. ええと, scheme の話か haskell の話か, どっちなんでしょう? > いけない理由
  • 2005-02-12 (土) 17:29:09 名無しさん : 両方。
  • 2005-02-12 (土) 17:31:32 名無しさん : 「モナドの全て」のContinuatinの所に載っているcallCCを実装し、それを脱出に使おうとすると、この問題が起こる
  • 2005-02-22 (火) 23:50:42 名無しさん : なるほど. thx > この問題が起こる. call/cc も書き足してみましたけど, あってんのかなあ?
  • 2005-07-25 (月) 20:29:02 Anonymous : おたまじゃくしは小枝についたモナドを食べて成長します
  • 2006-01-19 (木) 23:45:56 Anonymous : IO モナドについては, Haskellの入出力がわかりやすそう
  • 2006-06-07 : IO モナドをぜんぶ書き直した
  • Haskell で, ポイントフリースタイルの方が「.」だらけとはこれいかに? (わかって言ってる(つもり)です)
(Please LogIn to post comments.)

Last modified:2008/03/09 15:59:32
Keyword(s):
References:[不完全性定理] [不完全性定理.改] [なんでも]