めざそう言語処理系の沼 〜shift/resetへの旅 〜 その17 shift/resetでつくるMaybeモナド
shift
とreset
が実装できたのでそれらを使ってモナドっぽい機能を実装してみる。
手始めに以前も紹介したこの資料に出てくるMaybe
モナド的なものを試してみたい:
HaskellやOCamlでMaybeモナドといえばJust x
(あるいはSome x
)かNone
の値を取る型とそれを返す関数を繋げていくような演算がポイントとなる。
しかし今回実装しているのはなんちゃってとは言えLispである。Lisperなら黙ってnilを返そう。(そもそも代数的データ型やパターンマッチを実装していないのでSome x
とかできないし・・・)
というわけで演算の結果が何らかの値かnil
であるというような処理を繋げていって、途中の計算結果がnilになった場合はショートサーキットして全体の結果がnilになる、といった処理が書けるようにしたい。Just
やSome
にあたるケースはそのような特定のタグをつけるのではなく、そのままの値を使う。
そのために
- Haskellの
do
にあたるような「ここからはMaybeモナドのコンテキスト内である」と指示するreify
x <- ...
に(おおまかに)対応するような「これはモナディックな値である」と指示するreflect
- 値か
nil
かを返すfind
関数
の三つを定義する。
まずreify
:
(let [reify (macro [expr] (reset expr))] ...)
マクロで式をreset
に包むだけ。reify
を定義しなくてもreset
をそのまま使えば同じことができるが、reset
はモナドを実装するプリミティブとしてとりあえず隠蔽しておく。
次にreflect
:
(let [reflect (fn [m] (shift [k] (if (nil? m) m (k m))))] ...)
shift
で現在の限定継続をとり、reflect
が受け取った値がnil
ならそのまま全体の値をnil
とし、そうでないならそのnil
ではない値を限定継続に渡して評価を続ける。
そしてfind
:
(letrec [find [f xs] (cond [(nil? xs) nil] [(f (car xs)) (car xs)] [true (find f (cdr xs))])] ...)
要素に対する述語関数とリストを受け取り、もし述語を満たす値があればその一つを返し、もし満たすものがないならnil
を返す。find
関数はMaybeモナドの一部ではない。Maybeモナドを使うためにnil
を返し得る関数が必要だったので定義しただけである。
組み合わせて使ってみる:
(reify (let [(a (reflect (find (fn [x] (= x 2)) (list 1 0 3)))) (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))] (list a b)))
この場合、a
がnil
になるので全体の値もnil
になる。さらにb
に束縛される値は評価されずじまいとなる。
上記のコードを全部合わせてインタプリタで走らせられるようにしたプログラムは以下のとおり:
(let [(reify (macro [expr] (reset expr))) (reflect (fn [m] (shift [k] (if (nil? m) m (k m)))))] (letrec [find [f xs] (cond [(nil? xs) nil] [(f (car xs)) (car xs)] [true (find f (cdr xs))])] (reify (let [(a (reflect (find (fn [x] (= x 2)) (list 1 2 3)))) (* ここは変更 *) (b (reflect (find (fn [x] (= x 3)) (list 2 3 1))))] (list a b)))))
a
の式に少しだけ変更を加えていて、そのせいで今回はa
もb
もnil
にならないので、最終的に結果は(2 3)
となる。
というわけでMaybeモナドのように、途中結果がnil
なら全体の結果もnil
になるような処理が簡単に記述できるようになった。
次はsshift
とreset
で非決定性プログラミングができるようなListモナドをつくってみる。