Feb 14 2012

この日付管理、ちょっと信用できなくなってきた

一つ上の人の卒論発表会見に行った． あんな、誰でも自由に入って見聞きできるカンジなんだ． 日付と場所さえ、どこかから聞きつけられれば、部外者 でも行ける．修士論文とかは知らんけど．

自分があの場所に立ってあんなこと発表するなんて 信じられないな．ムリだろうな．研究室次第だろうな とも思った．

Maybeモナドをschemeで．

Monad in Scheme (2) - moratorium のパクリなんだけど、思い出しながらで書いたのであって、丸写しではないという 意味で、自分としては重要なので、

(define (return x)
    (lambda (f . rest) (f x rest)))

(define (fail . _) (return 'Nothing))
(define (fail? x)  (equal? 'Nothing x))

(define zero (return 0))
(define one  (return 1))

(define (succ x) (return (+ x 1)))
(define (pred x) (return (- x 1)))

(define (>>= x ls)
    (if (fail? x) (fail)
        (if (null? (cdr ls)) ((car ls) x)
            (apply ((car ls) x) (cdr ls)) )))

(define (M m)
    (define (f x _) x)
    (m f))

目次．

• 私の持っているモナドに対する知識
• 実装 までのスケッチ
• 遊んでみる

私の持っているモナドに対する知識

Maybeモナドを構成するのは、return と >>= , あと最後に中身を出す為の M. あと失敗を表す為の fail と fail であるかを判定する述語 fail?.

Mというのは、例えば (return 1) は1を何かで包んでいる．中身の1をむき出しに するもの．

GHCiで実験してみると

Prelude> return 1
1

あ、こう表示されるんだ．

Prelude> let a = return 1

<interactive>:20:9:
    Ambiguous type variable `m0' in the constraint:
      (Monad m0) arising from a use of `return'
  Probable fix: add a type signature that fixes these type variable(s)
  In the expression: return 1
  In an equation for `a': a = return 1

単に return 1 では何のモナドなのかわからないので、型を与える． いわゆる文脈ってやつだよね？？

Prelude> let a = return 1 :: Maybe Int
Prelude> a
Just 1

Prelude> let a = return 1 :: [Int]
Prelude> a
[1]

( :: Maybe Int) という修飾子のつもりで、M は定義した．

そして、どのように実行されるべきか．ここからはSchemeのコードで書く． 以下は実際にgoshで実験した結果だけど、はじめに想定していた通りだ．

gosh> (return 1)
#<closure>
gosh> (M (return 1))
1
gosh> (M ( (return 1) >>= (^x (return 2)) ))
2
gosh> (M ( (return 1) >>= (^x (return 2)) >>= (^x (return 3)) ))
3

S式で、律儀に書くのなら、bindは

(>>= (>>= (return 1) (^x (return ...))) >>= (^x (return ...)))

と書くべきだ．つまり

(define (>>= m f) ... )

とされるべきで 実際、 howm wiki - モナド ここでの実装ではそうなってた．

はじめにも挙げた方の Monad in Scheme (2) - moratorium では、

(m >>= f >>= g >>= h ...)

という書き方を想定しており、なんだかとてもかっこいい． かっこよすぎて私はその記事でのモナドの実装をノートに書きまくった．

人間の体は夜ふかしができるようになっていて、つまり、一日の周期が24時間よりも長い ということがよく知られていて、だから後ろへずらすことが容易なのである．逆に 前にずらすことは出来ないけれど．私はこの一週間でズラしまくった結果、昼の12時過ぎに 寝て夜中の1時に起きた．睡眠時間だけは相変わらずである．外もそろそろ白んできて ふと思い出したので、あのモナドの実装を思い出しながら、思い出せない部分は なんとしても自分一人の発想で補ってやろうとして書いたのだった．

(m >>= f >>= g)

までできれば、きっと

(m >>= f >>= g >>= h)

は自然とできているだろう．でも取り敢えずは簡単に

(m >>= f)

から考えるべきだった．反省だ．おかげで時間がかかった．

failは一番最後に実装した．ほんの少しの修正ですんだ．failはこのように動くべき．

gosh> (M ( (return 1) >>= fail >>= (^x (return 3)) ))
Nothing

つまり、failのあとに実行されるものはreturn の結果には影響を与えない． 始めの引数評価の時以外、評価されることもない．

実装 までのスケッチ

私が思い出すために、裏紙に書きまくったラムダ式を写すとともに、精一杯 何を考えてたのかを言葉にした．

(define (return x)

xを包んだものを返す．よくあるのは、ローカル変数として定義してやること．すなわち

(lambda (f) (f x))

このようなラムダ式をreturnは返す．

似たものとして

(define (my-cons x y)
    (lambda (f) (f x y)))

というのがあった．これは定番だろう．my-consに対してmy-car, my-cdr は簡単だ．

cons に対してcar, cdr があるように、きっと return に対しては M であろう． Mはreturn が包んだものをひん剥くから．

(define (M m) ; m <- (return 1)
    (m (lambda (x) x)))

簡単だ．

そしたら、bindさえ書ければ、実質終わり． いきなり何を書いたらいいのか分からないので、こうなるべきだというベータ簡約の様子 を書いた．

((return 1) >>= (^x (return 2)))
 -> (>>= 1 (list (^x (return 2))))
 -> ((^x (return 2)) 1)
 -> (return 2)

この調子に、>>=をもうひとつ並べる

(return 1) >>= (^x (return 2)) >>= (^x (return 3))
 -> (>>= 1 (list (^x (return 2)) >>= (^x (return 3))))
 -> ((return 2) >>= (^x (return 3)))

>>= を中置で記法するために

(return 1) >>= .. が (>>= 1 ..)

のようになって、そして

(>>= 1 ls) は、

(let1 op (car ls)
  (apply (op ls 1) ls))

となってほしい．returnは今まで1引数を取るようなラムダ式を返すことにしてたけど、 ここで (>>= ..)という複数の値を渡すことで>>=を実行させるので、書き換えが必要だ．

(define (return x)
    (lambda (f . rest) (f x rest)))

これで、 ((return 1) >>= (^x ...)) は (>>= 1 ((^x ..))) となった．>>= への第二引数はリストであるのに注意．

(define (>>= x ls)
    (apply
        ((car ls) x)
        (cdr ls)))

これで (>>= 1 ((^x ..))) は (apply ((^x ..) 1) '()) となる． applyへの第二引数は残りの '(>>= (^x ...)) が入る予定だったが>>= 一つだけの 並びだと空になる．このときapplyはエラーを出す．null?で分岐が必要だった．

私としては、思い出すべきことは、これでひと通り全て思い出せた．

(fail) は(return 'Nothing) とするだけだし、 述語 (define fail? (pa$ equal 'Nothing)) を用意してやれば、 >>= の中で、まず (>>= x ls) の x について fail? して #t だったら (fail) を 返してやる．

以上でできたことになる．

遊んでみる

gosh> zero
#<closure (return return)>
gosh> (M zero)
0
gosh> (M one)
1
gosh> succ
#<closure succ>
gosh> pred
#<closure pred>
gosh> (M (one >>= succ))
2
gosh> (M (one >>= succ >>= succ))
3
gosh> (M (one >>= succ >>= fail >>= succ))
Nothing

gosh> (define (find x)
(let1 result (assoc x '((1 . minamike) (3 . okaeri) (4 . tadaima)))
(if result ($ return $ cdr result) (fail)) ))
find
gosh> (M (one >>= find))
minamike
gosh> (M (one >>= succ >>= find))
Nothing
gosh> (M (one >>= succ >>= succ >>= find))
okaeri
gosh> (M (one >>= succ >>= succ >>= pred >>= find))
Nothing

モナドは途中で失敗するっていう事例を見せるくらいでしか 有用性を示せないよね．それでたいていみんなゼロで割るよね．